Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems

Complexity and performance of numerical algorithms (65Y20) Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20)

Cites Work

Curvature Measures
Unitary Triangularization of a Nonsymmetric Matrix
Condition
Numerically solving polynomial systems with Bertini
Title not available (Why is that?)
The kinematic formula in Riemannian homogeneous spaces
On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
Most Tensor Problems Are NP-Hard
The complexity of partial derivatives
Title not available (Why is that?)
Fixed points, zeros and Newton's method
Mathematical problems for the next century
Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
On a problem posed by Steve Smale
On Smale's 17th problem: a probabilistic positive solution
Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
The Probability That a Numerical Analysis Problem is Difficult
Modern computer algebra
Complexity of Bezout's theorem. V: Polynomial time
Complexity of Bezout's theorem. III: Condition number and packing
Algorithm 921
Complexity of Bezout's Theorem I: Geometric Aspects
Fast linear homotopy to find approximate zeros of polynomial systems
On the efficiency of algorithms of analysis
On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
Adaptive step-size selection for homotopy methods to solve polynomial equations
Fast computation of zeros of polynomial systems with bounded degree under finite-precision
A continuation method to solve polynomial systems and its complexity
Efficient polynomial system-solving by numerical methods
A stable, polynomial-time algorithm for the eigenpair problem
A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
Title not available (Why is that?)
Condition length and complexity for the solution of polynomial systems
Certified predictor-corrector tracking for Newton homotopies
On the distance to the zero set of a homogeneous polynomial
On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
The Condition Number of Join Decompositions
Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric

Cited In (8)

Smale 17th Problem: Advances and Open Directions
Smoothed analysis for the condition number of structured real polynomial systems
On Smale's 17th problem: a probabilistic positive solution
Condition numbers for the cube. I: Univariate polynomials and hypersurfaces
Algebraic compressed sensing
Functional norms, condition numbers and numerical algorithms in algebraic geometry
Random Points on an Algebraic Manifold
Rigid continuation paths II. structured polynomial systems

Uses Software

Bertini
alphaCertified

This page was built for publication: Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5220197)