Condition length and complexity for the solution of polynomial systems

DOI10.1007/s10208-016-9309-9zbMath1358.65031arXiv1507.03896OpenAlexW2242581263WikidataQ57733073 ScholiaQ57733073MaRDI QIDQ506608

Felipe Cucker, Peter Bürgisser, Diego Armentano, Michael Shub, Carlos Beltran

Publication date: 1 February 2017

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

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

zbMATH Keywords

algorithmcondition numberpolynomial systemsapproximate zerocomplexity estimateshomotopy methodsSmale's 17th problem

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)

Related Items

Functional norms, condition numbers and numerical algorithms in algebraic geometry, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Rigid continuation paths II. structured polynomial systems, Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric, Smale 17th Problem: Advances and Open Directions, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A continuation method to solve polynomial systems and its complexity
• Fast linear homotopy to find approximate zeros of polynomial systems
• Stochastic perturbations and smooth condition numbers
• Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
• Complexity of Bezout's theorem. V: Polynomial time
• A stable, polynomial-time algorithm for the eigenpair problem
• A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
• On the geometry and topology of the solution variety for polynomial system solving
• Robust certified numerical homotopy tracking
• Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
• Complexity of Bezout's Theorem I: Geometric Aspects
• On the Medians of Gamma Distributions and an Equation of Ramanujan
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Adaptive step-size selection for homotopy methods to solve polynomial equations
• The complexity and geometry of numerically solving polynomial systems.