Deformation techniques for sparse systems

DOI10.1007/s10208-008-9024-2zbMath1167.14039arXivmath/0608714OpenAlexW2060414131MaRDI QIDQ1029552

Pablo Solernó, Ariel Waissbein, Guillermo Matera, Gabriela Jeronimo

Publication date: 13 July 2009

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Computational aspects of algebraic curves (14Q05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Formal power series rings (13F25)

Related Items

A package for computations with sparse resultants, Symbolic computation in hyperbolic programming, Real root finding for low rank linear matrices, Solving rank-constrained semidefinite programs in exact arithmetic, Sparse resultants and straight-line programs, Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization, The Canny-Emiris conjecture for the sparse resultant, Computing isolated roots of sparse polynomial systems in affine space, A concise proof of the Kronecker polynomial system solver from scratch, A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, Solving determinantal systems using homotopy techniques, On the bit complexity of polynomial system solving, A Robust Numerical Path Tracking Algorithm for Polynomial Homotopy Continuation, Homotopy techniques for solving sparse column support determinantal polynomial systems, Elimination for generic sparse polynomial systems, The method of Gauss-Newton to compute power series solutions of polynomial homotopies, Tropical algebraic geometry in Maple: a preprocessing algorithm for finding common factors for multivariate polynomials with approximate coefficients, On sign conditions over real multivariate polynomials, Computing All Space Curve Solutions of Polynomial Systems by Polyhedral Methods, Exact Algorithms for Linear Matrix Inequalities, The persistent homology of dual digital image constructions, A Poisson formula for the sparse resultant, Computing critical points for invariant algebraic systems, Locating the closest singularity in a polynomial homotopy

Uses Software

• Kronecker

Cites Work

• 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
• Polynomial equation solving by lifting procedures for ramified fibers
• High probability analysis of the condition number of sparse polynomial systems
• Deformation techniques to solve generalised Pham systems
• Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers
• Bernstein's theorem in affine space
• The complexity of partial derivatives
• The number of roots of a system of equations
• Newton polytopes and the Bezout theorem
• Newton polyhedra and the genus of complete intersections
• Product formulas for resultants and Chow forms
• Lower bounds for diophantine approximations
• Straight-line programs in geometric elimination theory
• The hardness of polynomial equation solving
• Computing parametric geometric resolutions
• Diophantine geometry and toric varieties.
• Solving degenerate sparse polynomial systems faster
• Quadratic Newton iteration for systems with multiplicity
• The computational complexity of the Chow form
• Bounds of traces in complete intersections and degrees in the Nullstellensatz
• 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.
• Polynomial evaluation and interpolation on special sets of points
• A concise proof of the Kronecker polynomial system solver from scratch
• Counting affine roots of polynomial systems via pointed Newton polytopes
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• The BKK root count in $\mathbf {C}^n$
• A Product-Decomposition Bound for Bezout Numbers
• A Polyhedral Method for Solving Sparse Polynomial Systems
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• A Gröbner free alternative for polynomial system solving
• Finding mixed cells in the mixed volume computation