A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time

DOI10.1007/S10208-016-9319-7zbMath1458.65058arXiv1507.05485OpenAlexW3099047857MaRDI QIDQ1683739

Pierre Lairez

Publication date: 1 December 2017

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

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

zbMATH Keywords

homotopy continuationpolynomial systemcomplexity analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items (16)

Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers ⋮ Condition numbers for the cube. I: Univariate polynomials and hypersurfaces ⋮ Algebraic compressed sensing ⋮ Rigid continuation paths II. structured polynomial systems ⋮ Estimation under group actions: recovering orbits from invariants ⋮ The average condition number of most tensor rank decomposition problems is infinite ⋮ Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric ⋮ Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions ⋮ A sequence of polynomials with optimal condition number ⋮ Mixed precision path tracking for polynomial homotopy continuation ⋮ Condition length and complexity for the solution of polynomial systems ⋮ Grid methods in computational real algebraic (and semialgebraic) geometry ⋮ Computing the homology of semialgebraic sets. I: Lax formulas ⋮ Smale 17th Problem: Advances and Open Directions ⋮ Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems ⋮ Smoothed analysis for the condition number of structured real polynomial systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Condition length and complexity for the solution of polynomial systems
• A continuation method to solve polynomial systems and its complexity
• Fast linear homotopy to find approximate zeros of polynomial systems
• On a problem posed by Steve Smale
• Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
• A method for generating uniformly distributed points on \(N\)-dimensional spheres
• The complexity of partial derivatives
• Mathematical problems for the next century
• A stable, polynomial-time algorithm for the eigenpair problem
• A randomized homotopy for the Hermitian eigenpair problem
• Condition
• Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
• Complexity of Bezout's Theorem I: Geometric Aspects
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• 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
• Smoothed analysis of algorithms
• Fast computation of zeros of polynomial systems with bounded degree under finite-precision

This page was built for publication: A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time