Elimination for generic sparse polynomial systems

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

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

Cited In (10)

• Solving determinantal systems using homotopy techniques
• Deformation techniques for sparse systems
• An elimination method for polynomial systems
• Title not available (Why is that?)
• Computing critical points for invariant algebraic systems
• Computing all space curve solutions of polynomial systems by polyhedral methods
• A new sparse Gaussian elimination algorithm and the Niederreiter linear system for trinomials over \(\mathbb F_2\)
• 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)