Skip to Main content Skip to Navigation
New interface
Conference papers

Faster change of order algorithm for Gröbner bases under shape and stability assumptions

Abstract : Solving zero-dimensional polynomial systems using Gr\"obner bases is usuallydone by, first, computing a Gröbner basis for the degree reverse lexicographicorder, and next computing the lexicographic Gröbner basis with a change oforder algorithm. Currently, the change of order now takes a significant partof the whole solving time for many generic instances.Like the fastest known change of order algorithms, this work focuses on thesituation where the ideal defined by the system satisfies natural propertieswhich can be recovered in generic coordinates. First, the ideal has a\emph{shape} lexicographic Gröbner basis. Second, the set of leading terms withrespect to the degree reverse lexicographic order has a \emph{stability}property; in particular, the multiplication matrix can be read on the inputGröbner basis.The current fastest algorithms rely on the sparsity of this matrix. Actually,this sparsity is a consequence of an algebraic structure, which can beexploited to represent the matrix concisely as a univariate polynomial matrix.We show that the Hermite normal form of that matrix yields the soughtlexicographic Gröbner basis, under assumptions which cover the shape positioncase. Under some mild assumption implying \(n \le t\), the arithmeticcomplexity of our algorithm is $O\tilde{~}(t^{\omega-1}D)$, where $n$ is thenumber of variables, $t$ is a sparsity indicator of the aforementioned matrix,$D$ is the degree of the zero-dimensional ideal under consideration, and$\omega$ is the exponent of matrix multiplication. This improves upon bothstate-of-the-art complexity bounds $O\tilde{~}(tD^2)$ and$O\tilde{~}(D^\omega)$, since $\omega < 3$ and \(t\le D\). Practicalexperiments, based on the libraries msolve and PML, confirm the highpractical benefit.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03580736
Contributor : Vincent Neiger Connect in order to contact the contributor
Submitted on : Monday, May 16, 2022 - 12:08:08 AM
Last modification on : Friday, September 16, 2022 - 3:56:31 PM

File

fast-change-of-order.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Jérémy Berthomieu, Vincent Neiger, Mohab Safey El Din. Faster change of order algorithm for Gröbner bases under shape and stability assumptions. 2022 International Symposium on Symbolic and Algebraic Computation, Jul 2022, Lille, France. ⟨10.1145/3476446.3535484⟩. ⟨hal-03580736v2⟩

Share

Metrics

Record views

101

Files downloads

67