Deformation techniques for sparse systems
From MaRDI portal
Publication:1029552
DOI10.1007/S10208-008-9024-2zbMATH Open1167.14039arXivmath/0608714OpenAlexW2060414131MaRDI QIDQ1029552FDOQ1029552
Authors: Gabriela Jeronimo, Guillermo Matera, Pablo Solernó, Ariel Waissbein 
Publication date: 13 July 2009
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
Abstract: We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is quadratic in the size of the combinatorial structure of the input system. This size is mainly represented by the mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration.
Full work available at URL: https://arxiv.org/abs/math/0608714
Recommendations
Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Formal power series rings (13F25) Computational aspects of algebraic curves (14Q05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)
Cites Work
- A concise proof of the Kronecker polynomial system solver from scratch
- Title not available (Why is that?)
- Title not available (Why is that?)
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- The complexity of partial derivatives
- Polynomial evaluation and interpolation on special sets of points
- Title not available (Why is that?)
- Title not available (Why is that?)
- Straight-line programs in geometric elimination theory
- The hardness of polynomial equation solving
- Computing parametric geometric resolutions
- Quadratic Newton iteration for systems with multiplicity
- 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
- Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
- Newton polyhedra and the genus of complete intersections
- Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Polyhedral Method for Solving Sparse Polynomial Systems
- The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
- The number of roots of a system of equations
- Newton polytopes and the Bezout theorem
- Title not available (Why is that?)
- Modern computer algebra
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Deformation techniques to solve generalised Pham systems
- Title not available (Why is that?)
- Lower bounds for diophantine approximations
- 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
- Deformation techniques for efficient polynomial equation solving.
- Counting affine roots of polynomial systems via pointed Newton polytopes
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Product formulas for resultants and Chow forms
- A Product-Decomposition Bound for Bezout Numbers
- Bounds of traces in complete intersections and degrees in the Nullstellensatz
- Polynomial equation solving by lifting procedures for ramified fibers
- High probability analysis of the condition number of sparse polynomial systems
- Solving degenerate sparse polynomial systems faster
- Diophantine geometry and toric varieties.
Cited In (26)
- A package for computations with sparse resultants
- Solving determinantal systems using homotopy techniques
- Symbolic computation in hyperbolic programming
- A concise proof of the Kronecker polynomial system solver from scratch
- Computing isolated roots of sparse polynomial systems in affine space
- Locating the closest singularity in a polynomial homotopy
- On the bit complexity of polynomial system solving
- Tropical algebraic geometry in Maple: a preprocessing algorithm for finding common factors for multivariate polynomials with approximate coefficients
- The method of Gauss-Newton to compute power series solutions of polynomial homotopies
- Solving rank-constrained semidefinite programs in exact arithmetic
- A Poisson formula for the sparse resultant
- Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
- Computing critical points for invariant algebraic systems
- Computing all space curve solutions of polynomial systems by polyhedral methods
- A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
- On sign conditions over real multivariate polynomials
- Elimination for generic sparse polynomial systems
- Exact algorithms for linear matrix inequalities
- The Canny-Emiris conjecture for the sparse resultant
- Solving decomposable sparse systems
- Sparse resultants and straight-line programs
- A robust numerical path tracking algorithm for polynomial homotopy continuation
- Deformation techniques to solve generalised Pham systems
- Real root finding for low rank linear matrices
- The persistent homology of dual digital image constructions
- Homotopy techniques for solving sparse column support determinantal polynomial systems
Uses Software
This page was built for publication: Deformation techniques for sparse systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1029552)
