Solving degenerate sparse polynomial systems faster
From MaRDI portal
algorithmChow formcomputational complexitydegenerate polynomial system solvinggeneralized characteristic polynomialresultantsparse systemsystem of polynomial equationstoric geometrytwisted Chow form
Real polynomials: location of zeros (26C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20)
Abstract: 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.
Recommendations
- A generalized Euclidean algorithm for computing triangular representations of algebraic varieties
- Generalised characteristic polynomials
- Bounds on numers of vectors of multiplicities for polynomials which are easy to compute
- scientific article; zbMATH DE number 1008376
- scientific article; zbMATH DE number 1961537
- Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic
- Finding irreducible components of some real transcendental varieties
- A deterministic polynomial-time algorithm for the first Bertini theorem. II
- scientific article; zbMATH DE number 16644
- scientific article; zbMATH DE number 806911
Cites work
- A convex geometric approach to counting the roots of a polynomial system
- Asymptotic acceleration of solving multivariate polynomial systems of equations
- Bernstein's theorem in affine space
- Bézout number calculations for multi-homogeneous polynomial systems
- Chow polytopes and general resultants
- Combining binary search and Newton's method to compute real roots for a class of real functions
- Computing the Ehrhart polynomial of a convex lattice polytope
- Counting affine roots of polynomial systems via pointed Newton polytopes
- Effective Noether irreducibility forms and applications
- Efficient incremental algorithms for the sparse resultant and the mixed volume
- Efficient theoretic and practical algorithms for linear matroid intersection problems
- Generalised characteristic polynomials
- Geometric algorithms and combinatorial optimization.
- scientific article; zbMATH DE number 981224 (Why is no real title available?)
- scientific article; zbMATH DE number 1800029 (Why is no real title available?)
- scientific article; zbMATH DE number 3838204 (Why is no real title available?)
- scientific article; zbMATH DE number 3859276 (Why is no real title available?)
- scientific article; zbMATH DE number 3919830 (Why is no real title available?)
- scientific article; zbMATH DE number 49991 (Why is no real title available?)
- scientific article; zbMATH DE number 192855 (Why is no real title available?)
- scientific article; zbMATH DE number 1253983 (Why is no real title available?)
- scientific article; zbMATH DE number 1254255 (Why is no real title available?)
- scientific article; zbMATH DE number 1273644 (Why is no real title available?)
- scientific article; zbMATH DE number 1305087 (Why is no real title available?)
- scientific article; zbMATH DE number 503395 (Why is no real title available?)
- scientific article; zbMATH DE number 575960 (Why is no real title available?)
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- scientific article; zbMATH DE number 708653 (Why is no real title available?)
- scientific article; zbMATH DE number 1057749 (Why is no real title available?)
- scientific article; zbMATH DE number 1104295 (Why is no real title available?)
- scientific article; zbMATH DE number 3895043 (Why is no real title available?)
- scientific article; zbMATH DE number 960150 (Why is no real title available?)
- scientific article; zbMATH DE number 967398 (Why is no real title available?)
- scientific article; zbMATH DE number 3055967 (Why is no real title available?)
- Introduction to Toric Varieties. (AM-131)
- Matrix multiplication via arithmetic progressions
- Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
- Newton polyhedra and toroidal varieties
- On The Complexity of Computing Mixed Volumes
- On the Newton polytope of the resultant
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- Output-sensitive results on convex hulls, extreme points, and related problems
- Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
- Product formulas for resultants and Chow forms
- Solvability by radicals is in polynomial time
- The complexity of elementary algebra and geometry
- The complexity of the word problems for commutative semigroups and polynomial ideals
- THE GEOMETRY OF TORIC VARIETIES
- The number of roots of a system of equations
- Toric intersection theory for affine root counting
- Toroidal embeddings. I
Cited in
(36)- Cayley-Dixon projection operator for multi-univariate composed polynomials
- Deformation techniques for sparse systems
- Toric intersection theory for affine root counting
- Sparse resultant under vanishing coefficients
- Dense resultant of composed polynomials: mixed-mixed case
- Toric Newton method for polynomial homotopies
- Some speed-ups and speed limits for real algebraic geometry
- Numerical homotopies to compute generic points on positive dimensional algebraic sets
- Sparse resultant of composed polynomials. I: Mixed-unmixed case.
- Sparse resultant of composed polynomials. II: Unmixed-mixed case.
- On solving univariate sparse polynomials in logarithmic time
- Uncomputably large integral points on algebraic plane curves?
- New results on quasi-subfield polynomials
- Solving decomposable sparse systems
- Numerical root finding via Cox rings
- Quasi-subfield polynomials and the elliptic curve discrete logarithm problem
- Solving determinantal systems using homotopy techniques
- A perturbed differential resultant based implicitization algorithm for linear DPPEs
- Degeneracy loci and polynomial equation solving
- Finding sparse solutions of systems of polynomial equations via group-sparsity optimization
- Resultants of partially composed polynomials
- Rational univariate reduction via toric resultants
- Macaulay style formulas for sparse resultants
- Computing the torsion points of a variety defined by lacunary polynomials
- A note on Diem's proof
- scientific article; zbMATH DE number 1736029 (Why is no real title available?)
- scientific article; zbMATH DE number 1008376 (Why is no real title available?)
- Toric eigenvalue methods for solving sparse polynomial systems
- A systematic framework for solving geometric constraints analytically
- Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy
- Explicit formulas for the multivariate resultant.
- Towards signature-based gröbner basis algorithms for computing the nondegenerate locus of a polynomial system
- Segre-driven radicality testing
- On the complexity of Chow and Hurwitz forms
- Persistent components in Canny's generalized characteristic polynomial
- Generalised characteristic polynomials
This page was built for publication: Solving degenerate sparse polynomial systems faster
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1808666)
