Solving Degenerate Sparse Polynomial Systems Faster

Given a zero-dimensional ideal I in K[x1,...,xn] of degree D, the transformation of the ordering of its Groebner basis from DRL to LEX is a key step in polynomial system solving and turns out to be the bottleneck of the whole solving process. Thus it is of crucial importance to design efficient algorithms to perform the change of ordering. The main contributions of this paper are several efficient methods for the change of ordering which take advantage of the sparsity of mu...

Multi-homogeneous polynomial systems arise in many applications. We provide bit complexity estimates for solving them which, up to a few extra other factors, are quadratic in the number of solutions and linear in the height of the input system under some genericity assumptions. The assumptions essentially imply that the Jacobian matrix of the system under study has maximal rank at the solution set and that this solution set if finite. The algorithm is probabilistic and a prob...

We introduce the concept of monodromy coordinates for representing solutions to large polynomial systems. Representing solutions this way provides a time-memory trade-off in a monodromy solving algorithm. We describe an algorithm, which interpolates the usual monodromy solving algorithm, for computing such a representation and analyze its space and time complexity.

The complexity of computing the solutions of a system of multivariate polynomial equations by means of Groebner bases computations is upper bounded by a function of the solving degree. In this paper, we discuss how to rigorously estimate the solving degree of a system, focusing on systems arising within public-key cryptography. In particular, we show that it is upper bounded by, and often equal to, the Castelnuovo-Mumford regularity of the ideal generated by the homogenizatio...

In this paper we report on an application of computer algebra in which mathematical puzzles are generated of a type that had been widely used in mathematics contests by a large number of participants worldwide. The algorithmic aspect of our work provides a method to compute rational solutions of single polynomial equations that are typically large with $10^2 \ldots 10^5$ terms and that are heavily underdetermined. This functionality was obtained by adding modules for a new ...

For several computational procedures such as finding radicals and Noether normalizations, it is important to choose as sparse as possible a system of parameters in a polynomial ideal or modulo a polynomial ideal. We describe new strategies for these tasks, thus providing solutions to problems (1) and (2) posed in [Eisenbud-Huneke-Vasconcelos 1992].

We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is quadratic in the size of the combinatorial structure of the input system. This size is mainly represented by the mixed volume of Newton polytopes of the input polynomials an...

In this article we present a parallel modular algorithm to compute all solutions with multiplicities of a given zero-dimensional polynomial system of equations over the rationals. In fact, we compute a triangular decomposition using M\"oller's algorithm (cf. [M\"o93]) of the corresponding ideal in the polynomial ring over the rationals using modular methods, and then apply a solver for univariate polynomials.

Let $F(x, y) \in \mathbb{C}[x,y]$ be a polynomial of degree $d$ and let $G(x,y) \in \mathbb{C}[x,y]$ be a polynomial with $t$ monomials. We want to estimate the maximal multiplicity of a solution of the system $F(x,y) = G(x,y) = 0$. Our main result is that the multiplicity of any isolated solution $(a,b) \in \mathbb{C}^2$ with nonzero coordinates is no greater than $\frac{5}{2}d^2t^2$. We ask whether this intersection multiplicity can be polynomially bounded in the number of ...

We obtain upper bounds for the multiplicity of an isolated solution of a system of equations $f_1=...= f_M =0$ in $M$ variables, where the set of polynomials $(f_1,..., f_M)$ is a tuple of general position in a subvariety of a given codimension which does not exceed $M$, in the space of tuples of polynomials. It is proved that for $M\to\infty$ that multiplicity grows not faster than $\sqrt{M}\exp[\omega\sqrt{M}]$, where $\omega>0$ is a certain constant.