Rigid continuation paths II. structured polynomial systems
From MaRDI portal
Abstract: This work studies the average complexity of solving structured polynomial systems that are characterized by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most {delta} in n variables with only poly(n, {delta}) L operations with high probability. This exceeds the expectations implicit in Smale's 17th problem.
Recommendations
- Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
- A continuation method to solve polynomial systems and its complexity
- A special homotopy continuation method for a class of polynomial systems
- Polynomial Systems, Homotopy Continuation, and Applications
- Continuity loci for polynomial systems
- scientific article; zbMATH DE number 1192222
- Topics in polynomial dynamical systems: existence, examples, rigidity
- scientific article; zbMATH DE number 4001948
- The structure of continuous rigid functions of two variables
- On continuation via polynomials
Cites work
- scientific article; zbMATH DE number 421657 (Why is no real title available?)
- scientific article; zbMATH DE number 4214184 (Why is no real title available?)
- scientific article; zbMATH DE number 3744549 (Why is no real title available?)
- scientific article; zbMATH DE number 3779725 (Why is no real title available?)
- scientific article; zbMATH DE number 3634395 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1069617 (Why is no real title available?)
- scientific article; zbMATH DE number 3992817 (Why is no real title available?)
- A Global Lojasiewicz Inequality for Algebraic Varieties
- A Gröbner free alternative for polynomial system solving
- A continuation method to solve polynomial systems and its complexity
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- A robust numerical path tracking algorithm for polynomial homotopy continuation
- Algorithm 921: alphaCertified: certifying solutions to polynomial systems
- Bayesian data analysis.
- Certified numerical homotopy tracking
- Certified predictor-corrector tracking for Newton homotopies
- Characterizing Valiant's algebraic complexity classes
- Completeness and reduction in algebraic complexity theory
- Complexity of Bezout's Theorem I: Geometric Aspects
- Complexity of Bezout's theorem. III: Condition number and packing
- Complexity of Bezout's theorem. V: Polynomial time
- Complexity of Bezout's theorem. VI: Geodesics in the condition (number) metric
- Complexity of Bezout's theorem. VII: Distance estimates in the condition metric
- Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
- Concentration inequalities. A nonasymptotic theory of independence
- Condition length and complexity for the solution of polynomial systems
- Condition of intersecting a projective variety with a varying linear subspace
- Condition. The geometry of numerical algorithms
- Curvature Measures
- Fast linear homotopy to find approximate zeros of polynomial systems
- Fixed points, zeros and Newton's method
- Mathematical problems for the next century
- Mixed precision path tracking for polynomial homotopy continuation
- Multihomogeneous Newton methods
- On Smale's 17th problem: a probabilistic positive solution
- On a problem posed by Steve Smale
- On condition numbers and the distance to the nearest ill-posed problem
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- On the worst-case arithmetic complexity of approximating zeros of polynomials
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
- Robust certified numerical homotopy tracking
- Smale's 17th problem: average polynomial time to compute affine and projective solutions
- The complexity of partial derivatives
- The kinematic formula in Riemannian homogeneous spaces
- Univariate polynomials, nearly optimal algorithms for factorization and rootfinding
- Verified error bounds for multiple roots of systems of nonlinear equations
Cited in
(3)
This page was built for publication: Rigid continuation paths II. structured polynomial systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103341)
