Solving degenerate sparse polynomial systems faster

DOI10.1006/jsco.1998.0271zbMath0943.65060arXivmath/9809071OpenAlexW2140863255MaRDI QIDQ1808666

J. Maurice Rojas

Publication date: 21 August 2000

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9809071

zbMATH Keywords

algorithmcomputational complexitytoric geometryChow formresultantsparse systemsystem of polynomial equationsgeneralized characteristic polynomialdegenerate polynomial system solvingtwisted Chow form

Mathematics Subject Classification ID

Related Items (24)

A Note on Diem’s Proof ⋮ Numerical root finding via Cox rings ⋮ Quasi-subfield polynomials and the elliptic curve discrete logarithm problem ⋮ Segre-driven radicality testing ⋮ Sparse resultant under vanishing coefficients ⋮ Dense resultant of composed polynomials: mixed-mixed case ⋮ Resultants of partially composed polynomials ⋮ Uncomputably large integral points on algebraic plane curves? ⋮ New results on quasi-subfield polynomials ⋮ A systematic framework for solving geometric constraints analytically ⋮ On solving univariate sparse polynomials in logarithmic time ⋮ Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy ⋮ Macaulay style formulas for sparse resultants ⋮ Explicit formulas for the multivariate resultant. ⋮ A perturbed differential resultant based implicitization algorithm for linear DPPEs ⋮ Rational univariate reduction via toric resultants ⋮ Cayley-Dixon projection operator for multi-univariate composed polynomials ⋮ Deformation techniques for sparse systems ⋮ Toric Newton method for polynomial homotopies ⋮ Toric intersection theory for affine root counting ⋮ 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.

Cites Work

• Bernstein's theorem in affine space
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• Toroidal embeddings. I
• Matrix multiplication via arithmetic progressions
• Generalised characteristic polynomials
• Solvability by radicals is in polynomial time
• The complexity of elementary algebra and geometry
• Newton polyhedra and toroidal varieties
• Chow polytopes and general resultants
• Bézout number calculations for multi-homogeneous polynomial systems
• The number of roots of a system of equations
• Toric intersection theory for affine root counting
• Geometric algorithms and combinatorial optimization.
• On the Newton polytope of the resultant
• Product formulas for resultants and Chow forms
• Computing the Ehrhart polynomial of a convex lattice polytope
• Combining binary search and Newton's method to compute real roots for a class of real functions
• A convex geometric approach to counting the roots of a polynomial system
• Output-sensitive results on convex hulls, extreme points, and related problems
• Efficient theoretic and practical algorithms for linear matroid intersection problems
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Effective Noether irreducibility forms and applications
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Counting affine roots of polynomial systems via pointed Newton polytopes
• Introduction to Toric Varieties. (AM-131)
• On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
• THE GEOMETRY OF TORIC VARIETIES
• On The Complexity of Computing Mixed Volumes
• Asymptotic acceleration of solving multivariate polynomial systems of equations
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Solving degenerate sparse polynomial systems faster