Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

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


Author: Pierre Lairez
Journal: J. Amer. Math. Soc. 33 (2020), 487-526
MSC (2010): Primary 68Q25; Secondary 65H10, 65H20, 65Y20
DOI: https://doi.org/10.1090/jams/938
Published electronically: December 24, 2019
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: How many operations do we need on average to compute an approximate root of a random Gaussian polynomial system? Beyond Smale's 17th problem that asked whether a polynomial bound is possible, we prove a quasi-optimal bound $ \text {(input size)}^{1+o(1)}$. This improves upon the previously known $ \text {(input size)}^{\frac 32 +o(1)}$ bound.

The new algorithm relies on numerical continuation along rigid continuation paths. The central idea is to consider rigid motions of the equations rather than line segments in the linear space of all polynomial systems. This leads to a better average condition number and allows for bigger steps. We show that on average, we can compute one approximate root of a random Gaussian polynomial system of $ n$ equations of degree at most $ D$ in $ n+1$ homogeneous variables with  $ O(n^4 D^2)$ continuation steps. This is a decisive improvement over previous bounds that prove no better than  $ \sqrt {2}^{\min (n, D)}$ continuation steps on average.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 68Q25, 65H10, 65H20, 65Y20

Retrieve articles in all journals with MSC (2010): 68Q25, 65H10, 65H20, 65Y20


Additional Information

Pierre Lairez
Affiliation: Inria Saclay Île-de-France, 91120 Palaiseau, France

DOI: https://doi.org/10.1090/jams/938
Received by editor(s): November 9, 2017
Received by editor(s) in revised form: February 20, 2019, May 2, 2019, and September 9, 2019
Published electronically: December 24, 2019
Article copyright: © Copyright 2019 American Mathematical Society