Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
From MaRDI portal
Publication:5220197
DOI10.1090/jams/938OpenAlexW2982575816MaRDI QIDQ5220197
Publication date: 11 March 2020
Published in: Journal of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.03420
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
Random Points on an Algebraic Manifold ⋮ Functional norms, condition numbers and numerical algorithms in algebraic geometry ⋮ Condition numbers for the cube. I: Univariate polynomials and hypersurfaces ⋮ Algebraic compressed sensing ⋮ Rigid continuation paths II. structured polynomial systems ⋮ Smale 17th Problem: Advances and Open Directions
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Condition length and complexity for the solution of polynomial systems
- On the distance to the zero set of a homogeneous polynomial
- 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
- Fixed points, zeros and Newton's method
- Certified predictor-corrector tracking for Newton homotopies
- On Smale's 17th problem: a probabilistic positive solution
- 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 complexity of partial derivatives
- On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
- Complexity of Bezout's theorem. V: Polynomial time
- Mathematical problems for the next century
- A stable, polynomial-time algorithm for the eigenpair problem
- A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time
- Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
- Complexity of Bezout's theorem. III: Condition number and packing
- Efficient polynomial system-solving by numerical methods
- Condition
- Algorithm 921
- Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
- Curvature Measures
- On the efficiency of algorithms of analysis
- The Probability That a Numerical Analysis Problem is Difficult
- On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials
- Complexity of Bezout's Theorem I: Geometric Aspects
- The kinematic formula in Riemannian homogeneous spaces
- The Condition Number of Join Decompositions
- On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
- 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
- Most Tensor Problems Are NP-Hard
- Fast computation of zeros of polynomial systems with bounded degree under finite-precision
- Unitary Triangularization of a Nonsymmetric Matrix
