ID: math/9809071

Solving Degenerate Sparse Polynomial Systems Faster

September 14, 1998

View on ArXiv

Similar papers 2

Solving determinantal systems using homotopy techniques

February 28, 2018

87% Match
Jonathan D. PolSys Hauenstein, Mohab Safey El PolSys Din, ... , Vu Thi Xuan PolSys, CS
Symbolic Computation

Let $\K$ be a field of characteristic zero and $\Kbar$ be an algebraic closure of $\K$. Consider a sequence of polynomials$G=(g\_1,\dots,g\_s)$ in $\K[X\_1,\dots,X\_n]$, a polynomial matrix $\F=[f\_{i,j}] \in \K[X\_1,\dots,X\_n]^{p \times q}$, with $p \leq q$,and the algebraic set $V\_p(F, G)$ of points in $\KKbar$ at which all polynomials in $\G$ and all $p$-minors of $\F$vanish. Such polynomial systems appear naturally in e.g. polynomial optimization, computational geometry...

Find SimilarView on arXiv

Factoring sparse polynomials fast

December 28, 2023

87% Match
Alexander Demin, der Hoeven Joris van
Symbolic Computation
Commutative Algebra

Consider a sparse polynomial in several variables given explicitly as a sum of non-zero terms with coefficients in an effective field. In this paper, we present several algorithms for factoring such polynomials and related tasks (such as gcd computation, square-free factorization, content-free factorization, and root extraction). Our methods are all based on sparse interpolation, but follow two main lines of attack: iteration on the number of variables and more direct reducti...

Find SimilarView on arXiv

Decomposing Solution Sets of Polynomial Systems: A New Parallel Monodromy Breakup Algorithm

September 21, 2005

87% Match
Anton Leykin, Jan Verschelde
Distributed, Parallel, and C...
Numerical Analysis
Algebraic Geometry

We consider the numerical irreducible decomposition of a positive dimensional solution set of a polynomial system into irreducible factors. Path tracking techniques computing loops around singularities connect points on the same irreducible components. The computation of a linear trace for each factor certifies the decomposition. This factorization method exhibits a good practical performance on solution sets of relative high degrees. Using the same concepts of monodromy an...

Find SimilarView on arXiv

On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection

April 29, 2016

87% Match
Cornelius Brand, Michael Sagraloff
Symbolic Computation
Computational Complexity

Given a zero-dimensional polynomial system consisting of n integer polynomials in n variables, we propose a certified and complete method to compute all complex solutions of the system as well as a corresponding separating linear form l with coefficients of small bit size. For computing l, we need to project the solutions into one dimension along O(n) distinct directions but no further algebraic manipulations. The solutions are then directly reconstructed from the considered ...

Find SimilarView on arXiv

A Generic Position Based Method for Real Root Isolation of Zero-Dimensional Polynomial Systems

December 2, 2013

87% Match
Jin-San Cheng, Kai Jin
Symbolic Computation

We improve the local generic position method for isolating the real roots of a zero-dimensional bivariate polynomial system with two polynomials and extend the method to general zero-dimensional polynomial systems. The method mainly involves resultant computation and real root isolation of univariate polynomial equations. The roots of the system have a linear univariate representation. The complexity of the method is $\tilde{O}_B(N^{10})$ for the bivariate case, where $N=\max...

Find SimilarView on arXiv

Fast Computation of Zeros of Polynomial Systems with Bounded Degree under Finite-precision

May 4, 2012

87% Match
Irenee Briquel, Felipe Cucker, ... , Roshchina Vera
Numerical Analysis

A solution for Smale's 17th problem, for the case of systems with bounded degree was recently given. This solution, an algorithm computing approximate zeros of complex polynomial systems in average polynomial time, assumed infinite precision. In this paper we describe a finite-precision version of this algorithm. Our main result shows that this version works within the same time bounds and requires a precision which, on the average, amounts to a polynomial amount of bits in t...

Find SimilarView on arXiv

Toric Intersection Theory for Affine Root Counting

June 27, 1996

86% Match
J. Maurice Rojas
Algebraic Geometry

Given any polynomial system with fixed monomial term structure, we give explicit formulae for the generic number of roots with specified coordinate vanishing restrictions. For the case of affine space minus an arbitrary union of coordinate hyperplanes, these formulae are also the tightest possible upper bounds on the number of isolated roots. We also characterize, in terms of sparse resultants, precisely when these upper bounds are attained. Finally, we reformulate and extend...

Find SimilarView on arXiv

Solving Polynomial Systems via a Stabilized Representation of Quotient Algebras

November 13, 2017

86% Match
Simon AROMATH Telen, Bernard AROMATH Mourrain, Barel Marc Van
Algebraic Geometry

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. We propose a general algebraic framework to find the solutions and to compute the structure of the quotient ring R/I from the null space of a Macaulay-type matrix. The affine dense, affine sparse, homogeneous and multi-homogeneous cases are treated. In the presented framework, the concept of a border basis is gene...

Find SimilarView on arXiv

The complexity and geometry of numerically solving polynomial systems

November 7, 2012

86% Match
Carlos Beltran, Michael Shub
Numerical Analysis

These pages contain a short overview on the state of the art of efficient numerical analysis methods that solve systems of multivariate polynomial equations. We focus on the work of Steve Smale who initiated this research framework, and on the collaboration between Stephen Smale and Michael Shub, which set the foundations of this approach to polynomial system--solving, culminating in the more recent advances of Carlos Beltran, Luis Miguel Pardo, Peter Buergisser and Felipe Cu...

Find SimilarView on arXiv

Real Solution Isolation with Multiplicity of Zero-Dimensional Triangular Systems

June 17, 2009

86% Match
Zhihai Zhang, Tian Fang, Bican Xia
Symbolic Computation
Mathematical Software

Existing algorithms for isolating real solutions of zero-dimensional polynomial systems do not compute the multiplicities of the solutions. In this paper, we define in a natural way the multiplicity of solutions of zero-dimensional triangular polynomial systems and prove that our definition is equivalent to the classical definition of local (intersection) multiplicity. Then we present an effective and complete algorithm for isolating real solutions with multiplicities of zero...

Find SimilarView on arXiv