New interface

# 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.
Document type :
Conference papers
Domain :

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)

### 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⟩

Record views