A Gröbner free alternative for polynomial system solving (Q5938584): Difference between revisions

Let \(f_1,\dots, f_n\), \(g\in \mathbb{Q}[x_1,\dots, x_n]\) such that \(f_1=\cdots= f_n= 0\), \(g\neq 0\) has only finitely many solutions over \(\mathbb{C}\). The aim is to compute a representation of the solution set in the form \[ q(T)=0, \qquad \left\{ \begin{matrix} x_1= v_1(T)\\ \vdots\\ x_n= v_n(T) \end{matrix}\right., \tag{1} \] where \(q\) is a univariate polynomial over \(\mathbb{Q}\) and \(v_i\), \(1\leq i\leq n\), are univariate rational functions over \(\mathbb{Q}\). The algorithm presented is incremental in \(n\) such that the \(i\)th step solves \(f_1=\cdots= f_i= 0\) for \(x_{n-i+1},\dots, x_n\). For each \(i\), the algorithm uses Newton-Hensel lifting of \(x_{n-i}\) followed by intersection with the solution set of \(f_{i+1}=0\). Representation (1) is related to one first used by Kronecker at the end of the 19th century, which has been widely used to obtain complexity results in the zero-dimensional case. In practice, the representation is normally computed from a Gröbner basis. Kronecker's approach was rediscovered in 1995 and improved by \textit{M. Giusti, J. Heintz, J. E. Morais} and \textit{L. M. Pardo}, C. R. Acad. Sci., Paris, Sér. I 325, 1223-1228 (1997; Zbl 0893.68144)]. The present algorithm avoids the use of straight-line programs and needs only polynomials in at most two variables; geometrically it computes the intersection of two curves. Kronecker's representation of geometric resolutions leads to lower total degree complexity in the positive-dimensional case. The use of a global Newton iterator avoids the computation of geometric resolutions of intermediate varieties. Kronecker's simple technique to intersect a variety by a hypersurface avoids primitive element computations in two variables. The cost of integer manipulation is minimized by extensive use of modular arithmetic. The main complexity result is contained in the following theorem, in which \[ M(n)= O(n\log^2(n) \log\log(n)) \] and \(\Omega<4\): Let \(\mathbb{K}\) be a field of characteristic zero, and let \(f_1,\dots, f_n\), \(g\in \mathbb{K}[x_1,\dots, x_n]\) be polynomials of degree at most \(d\) given by a straight-line program of size at most \(L\), such that \(f_1,\dots, f_n\) defines a reduced regular sequence in the open subset \(\{g\neq 0\}\). The geometric resolution of the variety \({\mathcal V}(f_1,\dots, f_n)\setminus{\mathcal V}(g)\) can be computed with \(O(n(nL+ n^\Omega) (M(d\delta))^2)\) arithmetic operations in \(\mathbb{K}\), where \(\delta= \max(\deg({\mathcal V}_1),\dots, \deg({\mathcal V}_{n-1}))\). There is a probabilistic algorithm performing this computation. Its probability of returning correct results relies on choices of elements of \(\mathbb{K}\). Choices for which the result is not correct are enclosed in strict algebraic subsets. The algorithm presented does not greatly improve the worst-case complexity for dense polynomials. It works best when the complexity of evaluation of the input polynomials is small or the hypersurface \(g=0\) contains several components of each \({\mathcal V}_i\), i.e. \(\delta\ll d^n\). If \(\mathbb{K}= \mathbb{Q}\) then the bit-complexity for computation modulo a ``lucky prime'' is \[ O((nL+ n^\Omega) M(\deg(q)) M(\eta)), \] where \(\eta\) is the bit-size of the integers in the polynomials involved. This modular solution is then lifted to give a resolution in \(\mathbb{Q}\). The algorithm has been implemented in Magma as a package called Kronecker. Roughly speaking, its performance is between that of Gröbner basis computations using grevlex and lex orderings. The theory and algorithms are presented in detail, and precise running time comparisons are given for polynomial systems with a range of numbers of variables and heights (coefficient sizes).