Solving degenerate sparse polynomial systems faster
From MaRDI portal
computational complexityalgorithmtoric geometrysystem of polynomial equationsresultantChow formsparse systemgeneralized characteristic polynomialdegenerate polynomial system solvingtwisted Chow form
Complexity and performance of numerical algorithms (65Y20) Numerical computation of solutions to systems of equations (65H10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Real polynomials: location of zeros (26C10)
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
- 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?)
- 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.
- 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 GEOMETRY OF TORIC VARIETIES
- The complexity of elementary algebra and geometry
- The complexity of the word problems for commutative semigroups and polynomial ideals
- The number of roots of a system of equations
- Toric intersection theory for affine root counting
- Toroidal embeddings. I
Cited in
(35)- Toric Newton method for polynomial homotopies
- Quasi-subfield polynomials and the elliptic curve discrete logarithm problem
- Solving determinantal systems using homotopy techniques
- Degeneracy loci and polynomial equation solving
- A systematic framework for solving geometric constraints analytically
- Numerical homotopies to compute generic points on positive dimensional algebraic sets
- Toric eigenvalue methods for solving sparse polynomial systems
- A note on Diem's proof
- Deformation techniques for sparse systems
- Sparse resultant under vanishing coefficients
- Finding sparse solutions of systems of polynomial equations via group-sparsity optimization
- Sparse resultant of composed polynomials. I: Mixed-unmixed case.
- Sparse resultant of composed polynomials. II: Unmixed-mixed case.
- A perturbed differential resultant based implicitization algorithm for linear DPPEs
- Toric intersection theory for affine root counting
- scientific article; zbMATH DE number 1736029 (Why is no real title available?)
- Rational univariate reduction via toric resultants
- Segre-driven radicality testing
- Cayley-Dixon projection operator for multi-univariate composed polynomials
- Macaulay style formulas for sparse resultants
- Resultants of partially composed polynomials
- Dense resultant of composed polynomials: mixed-mixed case
- Some speed-ups and speed limits for real algebraic geometry
- Computing the torsion points of a variety defined by lacunary polynomials
- Numerical root finding via Cox rings
- Persistent components in Canny's generalized characteristic polynomial
- Solving decomposable sparse systems
- Generalised characteristic polynomials
- Towards signature-based gröbner basis algorithms for computing the nondegenerate locus of a polynomial system
- Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy
- On the complexity of Chow and Hurwitz forms
- On solving univariate sparse polynomials in logarithmic time
- Explicit formulas for the multivariate resultant.
- Uncomputably large integral points on algebraic plane curves?
- New results on quasi-subfield 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)
