Elimination for generic sparse polynomial systems

DOI10.1007/S00454-014-9571-ZzbMATH Open1310.68261arXiv1303.0266OpenAlexW2963839416MaRDI QIDQ2249474FDOQ2249474

María Isabel Herrero, Gabriela Jeronimo, Juan Sabia

Publication date: 1 July 2014

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We present a new probabilistic symbolic algorithm that, given a variety defined in an n-dimensional affine space by a generic sparse system with fixed supports, computes the Zariski closure of its projection to an l-dimensional coordinate affine space with l < n. The complexity of the algorithm depends polynomially on combinatorial invariants associated to the supports.

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

Recommendations

• scientific article; zbMATH DE number 806917
• Deformation techniques for sparse systems
• Affine solution sets of sparse polynomial systems
• Computing isolated roots of sparse polynomial systems in affine space
• Sparse Gröbner bases: the unmixed case

zbMATH Keywords

computational complexitysparse polynomial systemsprobabilistic symbolic algorithmprojection of algebraic varieties

Mathematics Subject Classification ID

Numerical linear algebra (65F99) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in general fields (irreducibility, etc.) (12E05) Solving polynomial systems; resultants (13P15) Computational aspects of higher-dimensional varieties (14Q15)

Cites Work

• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing parametric geometric resolutions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Gröbner free alternative for polynomial system solving
• On computing the determinant in small parallel time using a small number of processors
• On the Newton polytope of the resultant
• Newton polyhedra and toroidal varieties
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• On The Complexity of Computing Mixed Volumes
• A Polyhedral Method for Solving Sparse Polynomial Systems
• The number of roots of a system of equations
• Newton polytopes and the Bezout theorem
• Modern computer algebra
• Definability and fast quantifier elimination in algebraically closed fields
• Polyhedral Methods for Space Curves Exploiting Symmetry Applied to the Cyclic n-roots Problem
• Computing Puiseux series for algebraic surfaces
• Explicit formulas for the multivariate resultant.
• Macaulay style formulas for sparse resultants
• A subdivision-based algorithm for the sparse resultant
• A geometric index reduction method for implicit systems of differential algebraic equations
• Deformation techniques for sparse systems
• How to count efficiently all affine roots of a polynomial system
• A convex geometric approach to counting the roots of a polynomial system
• Mixed volume computation for semi-mixed systems
• Finding all isolated zeros of polynomial systems in \(\mathbb{C}^n\) via stable mixed volumes
• The computational complexity of the Chow form
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Mixed-volume computation by dynamic lifting applied to polynomial system solving
• Affine solution sets of sparse polynomial systems
• Counting affine roots of polynomial systems via pointed Newton polytopes
• Computing isolated roots of sparse polynomial systems in affine space
• Title not available (Why is that?)
• The BKK root count in $\mathbf {C}^n$
• Finding mixed cells in the mixed volume computation
• Bernstein's theorem in affine space
• Dynamic enumeration of all mixed cells
• Title not available (Why is that?)
• An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
• Polyhedral Methods in Numerical Algebraic Geometry
• Computing multihomogeneous resultants using straight-line programs
• Title not available (Why is that?)
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• How to compute the Chow form of an unmixed polynomial ideal in single exponential time
• Mixed volume techniques for embeddings of Laman graphs

Cited In (9)

• Solving determinantal systems using homotopy techniques
• An elimination method for polynomial systems
• Title not available (Why is that?)
• Computing critical points for invariant algebraic systems
• A new sparse Gaussian elimination algorithm and the Niederreiter linear system for trinomials over \(\mathbb F_2\)
• Computing All Space Curve Solutions of Polynomial Systems by Polyhedral Methods
• Overdetermined systems of sparse polynomial equations
• Global residues for sparse polynomial systems
• Homotopy techniques for solving sparse column support determinantal polynomial systems

Uses Software

• DEMiCs
• Kronecker

This page was built for publication: Elimination for generic sparse polynomial systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249474)