Fast linear homotopy to find approximate zeros of polynomial systems

DOI10.1007/s10208-010-9078-9zbMath1232.65075OpenAlexW2061860086MaRDI QIDQ626447

Luis Miguel Pardo, Carlos Beltran

Publication date: 18 February 2011

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

Full work available at URL: https://doi.org/10.1007/s10208-010-9078-9

zbMATH Keywords

systems of polynomial equationshomotopy methodapproximate zeroaverage complexity

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Complexity and performance of numerical algorithms (65Y20) Numerical computation of roots of polynomial equations (65H04) Solving polynomial systems; resultants (13P15)

Related Items

Certified Numerical Homotopy Tracking, On the computation of rational points of a hypersurface over a finite field, The Legacy of Turing in Numerical Analysis, Functional norms, condition numbers and numerical algorithms in algebraic geometry, On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant, On the geometry and topology of the solution variety for polynomial system solving, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Smale's fundamental theorem of algebra reconsidered, A continuation method to solve polynomial systems and its complexity, Rigid continuation paths II. structured polynomial systems, Spherical Radon transform and the average of the condition number on certain Schubert subvarieties of a Grassmannian, Geometry of polynomials and root-finding via path-lifting, Efficient approximation of the solution of certain nonlinear reaction-diffusion equations with small absorption, The average condition number of most tensor rank decomposition problems is infinite, Robust certified numerical homotopy tracking, An arithmetic Poisson formula for the multi-variate resultant, Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric, On a problem posed by Steve Smale, A sequence of polynomials with optimal condition number, Minimizing the discrete logarithmic energy on the sphere: The role of random polynomials, The unavoidable condition\dots A report on the book. Book review of: P. Bürgisser and F. Cucker, Condition. The geometry of numerical algorithms, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, Condition length and complexity for the solution of polynomial systems, Stochastic perturbations and smooth condition numbers, Probabilistic analyses of condition numbers, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, A note on the finite variance of the averaging function for polynomial system solving, Smale 17th Problem: Advances and Open Directions, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, The Polynomial Eigenvalue Problem is Well Conditioned for Random Inputs, A randomized homotopy for the Hermitian eigenpair problem

Uses Software

• HOM4PS
• PHCpack
• Bertini
• NAG4M2
• NumericalAlgebraicGeometry

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A continuation method to solve polynomial systems and its complexity
• On Smale's 17th problem: a probabilistic positive solution
• On the probability distribution of data at points in real complete intersection varieties
• HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method
• Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
• Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• The complexity of partial derivatives
• Complexity of Bezout's theorem. V: Polynomial time
• The hardness of polynomial equation solving
• A note on the finite variance of the averaging function for polynomial system solving
• Numerical algebraic geometry
• Bertini_real: Software for One- and Two-Dimensional Real Algebraic Sets
• Certified Numerical Homotopy Tracking
• Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
• Eigenvalues and Condition Numbers of Random Matrices
• Complexity of Bezout's Theorem I: Geometric Aspects
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Algorithm 795
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Adaptive step-size selection for homotopy methods to solve polynomial equations
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Tails of Condition Number Distributions
• Condition Numbers of Gaussian Random Matrices