ID: math/9809071

Solving Degenerate Sparse Polynomial Systems Faster

September 14, 1998

View on ArXiv
J. Maurice Rojas
Mathematics
Computer Science
Algebraic Geometry
Computational Complexity
Numerical Analysis
Numerical Analysis

Consider a system F of n polynomial equations in n unknowns, over an algebraically closed field of arbitrary characteristic. We present a fast method to find a point in every irreducible component of the zero set Z of F. Our techniques allow us to sharpen and lower prior complexity bounds for this problem by fully taking into account the monomial term structure. As a corollary of our development we also obtain new explicit formulae for the exact number of isolated roots of F and the intersection multiplicity of the positive-dimensional part of Z. Finally, we present a combinatorial construction of non-degenerate polynomial systems, with specified monomial term structure and maximally many isolated roots, which may be of independent interest.

Similar papers 1

Affine solution sets of sparse polynomial systems

October 13, 2011

89% Match
Maria Isabel Herrero, Gabriela Jeronimo, Juan Sabia
Algebraic Geometry
Data Structures and Algorith...
Symbolic Computation
Commutative Algebra

This paper focuses on the equidimensional decomposition of affine varieties defined by sparse polynomial systems. For generic systems with fixed supports, we give combinatorial conditions for the existence of positive dimensional components which characterize the equidimensional decomposition of the associated affine variety. This result is applied to design an equidimensional decomposition algorithm for generic sparse systems. For arbitrary sparse systems of n polynomials in...

Find SimilarView on arXiv

Root Isolation of Zero-dimensional Polynomial Systems with Linear Univariate Representation

February 23, 2011

88% Match
Jin-San Cheng, Xiao-Shan Gao, Leilei Guo
Symbolic Computation

In this paper, a linear univariate representation for the roots of a zero-dimensional polynomial equation system is presented, where the roots of the equation system are represented as linear combinations of roots of several univariate polynomial equations. The main advantage of this representation is that the precision of the roots can be easily controlled. In fact, based on the linear univariate representation, we can give the exact precisions needed for roots of the univar...

Find SimilarView on arXiv

Overdetermined systems of sparse polynomial equations

July 22, 2013

88% Match
Francesco Amoroso, Louis Leroux, Martin Sombra
Algebraic Geometry
Commutative Algebra
Number Theory

We show that, for a system of univariate polynomials given in sparse encoding, we can compute a single polynomial defining the same zero set, in time quasi-linear in the logarithm of the degree. In particular, it is possible to determine whether such a system of polynomials does have a zero in time quasi-linear in the logarithm of the degree. The underlying algorithm relies on a result of Bombieri and Zannier on multiplicatively dependent points in subvarieties of an algebrai...

Find SimilarView on arXiv

Toric Generalized Characteristic Polynomials

February 8, 1997

88% Match
J. Maurice Rojas
Algebraic Geometry
Data Structures and Algorith...

We illustrate an efficient new method for handling polynomial systems with degenerate solution sets. In particular, a corollary of our techniques is a new algorithm to find an isolated point in every excess component of the zero set (over an algebraically closed field) of any $n$ by $n$ system of polynomial equations. Since we use the sparse resultant, we thus obtain complexity bounds (for converting any input polynomial system into a multilinear factorization problem) which ...

Find SimilarView on arXiv

Polar Varieties and Efficient Real Elimination

May 4, 2000

88% Match
B. Bank, M. Giusti, ... , Mbakop G. M.
Algebraic Geometry

Let $S_0$ be a smooth and compact real variety given by a reduced regular sequence of polynomials $f_1, ..., f_p$. This paper is devoted to the algorithmic problem of finding {\em efficiently} a representative point for each connected component of $S_0$ . For this purpose we exhibit explicit polynomial equations that describe the generic polar varieties of $S_0$. This leads to a procedure which solves our algorithmic problem in time that is polynomial in the (extrinsic) descr...

Find SimilarView on arXiv

Homotopy techniques for solving sparse column support determinantal polynomial systems

September 2, 2020

88% Match
George SCG Labahn, Mohab Safey El PolSys Din, ... , Vu Thi Xuan PolSys, SCG
Symbolic Computation

Let $\mathbf{K}$ be a field of characteristic zero with $\overline{\mathbf{K}}$ its algebraic closure. Given a sequence of polynomials $\mathbf{g} = (g_1, \ldots, g_s) \in \mathbf{K}[x_1, \ldots , x_n]^s$ and a polynomial matrix $\mathbf{F} = [f_{i,j}] \in \mathbf{K}[x_1, \ldots, x_n]^{p \times q}$, with $p \leq q$, we are interested in determining the isolated points of $V_p(\mathbf{F},\mathbf{g})$, the algebraic set of points in $\overline{\mathbf{K}}$ at which all polynomi...

Find SimilarView on arXiv

Truncated Normal Forms for Solving Polynomial Systems: Generalized and Efficient Algorithms

March 21, 2018

87% Match
Bernard AROMATH Mourrain, Simon Telen, Barel Marc Van
Algebraic Geometry
Symbolic Computation
Numerical Analysis

We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal I in a ring R of polynomials over C. Normal form algorithms provide an algebraic approach to solve this problem. The framework presented in Telen et al. (2018) uses truncated normal forms (TNFs) to compute the algebra structure of R/I and the solutions of I. This framework allows for the use of much more general bases than the standard monomials for ...

Find SimilarView on arXiv

Polynomial Systems Solving by Fast Linear Algebra

April 22, 2013

87% Match
Jean-Charles INRIA Paris-Rocquencourt, LIP6 Faugère, Pierrick INRIA Nancy - Grand Est / LORIA Gaudry, ... , Renault Guénaël INRIA Paris-Rocquencourt, LIP6
Symbolic Computation

Polynomial system solving is a classical problem in mathematics with a wide range of applications. This makes its complexity a fundamental problem in computer science. Depending on the context, solving has different meanings. In order to stick to the most general case, we consider a representation of the solutions from which one can easily recover the exact solutions or a certified approximation of them. Under generic assumption, such a representation is given by the lexicogr...

Find SimilarView on arXiv

Polar Varieties, Real Equation Solving and Data-Structures: The hypersurface case

September 6, 1996

87% Match
B. Bank, M. Giusti, ... , Mbakop G. M.
Algebraic Geometry

In this paper we apply for the first time a new method for multivariate equation solving which was developed in \cite{gh1}, \cite{gh2}, \cite{gh3} for complex root determination to the {\em real} case. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm of \cite{gh1}, \cite{gh2}, \cite{gh3} yields a new method for symbolically solving zero-dimensional poly...

Find SimilarView on arXiv

On the multiplicity of isolated roots of sparse polynomial systems

September 19, 2017

87% Match
María Isabel Herrero, Gabriela Jeronimo, Juan Sabia
Algebraic Geometry
Commutative Algebra

We give formulas for the multiplicity of any affine isolated zero of a generic polynomial system of n equations in n unknowns with prescribed sets of monomials. First, we consider sets of supports such that the origin is an isolated root of the corresponding generic system and prove formulas for its multiplicity. Then, we apply these formulas to solve the problem in the general case, by showing that the multiplicity of an arbitrary affine isolated zero of a generic system wit...

Find SimilarView on arXiv