Elimination for generic sparse polynomial systems
From MaRDI portal
computational complexitysparse polynomial systemsprobabilistic symbolic algorithmprojection of algebraic varieties
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 16651 (Why is no real title available?)
- scientific article; zbMATH DE number 1206418 (Why is no real title available?)
- scientific article; zbMATH DE number 481965 (Why is no real title available?)
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 2051430 (Why is no real title available?)
- scientific article; zbMATH DE number 3895043 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- scientific article; zbMATH DE number 3068536 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 1736029 (Why is no real title available?)
- 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
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)
