Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
HTML articles powered by AMS MathViewer

by Pierre Lairez HTML | PDF
J. Amer. Math. Soc. 33 (2020), 487-526 Request permission

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
Similar Articles
Additional Information
  • Pierre Lairez
  • Affiliation: Inria Saclay Île-de-France, 91120 Palaiseau, France
  • MR Author ID: 993465
  • 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
  • © Copyright 2019 American Mathematical Society
  • 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
  • MathSciNet review: 4073867