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

International audienceSolving 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