Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems
HTML articles powered by AMS MathViewer
- by Pierre Lairez
- J. Amer. Math. Soc. 33 (2020), 487-526
- DOI: https://doi.org/10.1090/jams/938
- Published electronically: December 24, 2019
- HTML | PDF | 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
- Diego Armentano, Carlos Beltrán, Peter Bürgisser, Felipe Cucker, and Michael Shub, Condition length and complexity for the solution of polynomial systems, Found. Comput. Math. 16 (2016), no. 6, 1401–1422. MR 3579713, DOI 10.1007/s10208-016-9309-9
- Diego Armentano, Carlos Beltrán, Peter Bürgisser, Felipe Cucker, and Michael Shub, A stable, polynomial-time algorithm for the eigenpair problem, J. Eur. Math. Soc. (JEMS) 20 (2018), no. 6, 1375–1437. MR 3801817, DOI 10.4171/JEMS/789
- Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Numerically solving polynomial systems with Bertini, Software, Environments, and Tools, vol. 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3155500, DOI 10.1137/1.9781611972702
- Walter Baur and Volker Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), no. 3, 317–330. MR 693063, DOI 10.1016/0304-3975(83)90110-X
- Carlos Beltrán, A continuation method to solve polynomial systems and its complexity, Numer. Math. 117 (2011), no. 1, 89–113. MR 2754220, DOI 10.1007/s00211-010-0334-3
- Carlos Beltrán and Luis Miguel Pardo, On Smale’s 17th problem: a probabilistic positive solution, Found. Comput. Math. 8 (2008), no. 1, 1–43. MR 2403529, DOI 10.1007/s10208-005-0211-0
- C. Beltrán and L. M. Pardo, Efficient polynomial system-solving by numerical methods, J. Fixed Point Theory Appl. 6 (2009), no. 1, 63–85. MR 2558484, DOI 10.1007/s11784-009-0113-x
- Carlos Beltrán and Luis Miguel Pardo, Smale’s 17th problem: average polynomial time to compute affine and projective solutions, J. Amer. Math. Soc. 22 (2009), no. 2, 363–385. MR 2476778, DOI 10.1090/S0894-0347-08-00630-9
- Carlos Beltrán and Luis Miguel Pardo, Fast linear homotopy to find approximate zeros of polynomial systems, Found. Comput. Math. 11 (2011), no. 1, 95–129. MR 2754191, DOI 10.1007/s10208-010-9078-9
- Carlos Beltrán and Michael Shub, Complexity of Bezout’s theorem. VII. Distance estimates in the condition metric, Found. Comput. Math. 9 (2009), no. 2, 179–195. MR 2496559, DOI 10.1007/s10208-007-9018-5
- Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21 (1989), no. 1, 1–46. MR 974426, DOI 10.1090/S0273-0979-1989-15750-9
- Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf, Bruno Salvy, and Éric Schost, Algorithmes Efficaces En Calcul Formel. Frédéric Chyzak (self-pub.), 1 edition, 2017.
- Paul Breiding and Nick Vannieuwenhoven, The condition number of join decompositions, SIAM J. Matrix Anal. Appl. 39 (2018), no. 1, 287–309. MR 3765907, DOI 10.1137/17M1142880
- Irénée Briquel, Felipe Cucker, Javier Peña, and Vera Roshchina, Fast computation of zeros of polynomial systems with bounded degree under finite-precision, Math. Comp. 83 (2014), no. 287, 1279–1317. MR 3167459, DOI 10.1090/S0025-5718-2013-02765-2
- Peter Bürgisser and Felipe Cucker, On a problem posed by Steve Smale, Ann. of Math. (2) 174 (2011), no. 3, 1785–1836. MR 2846491, DOI 10.4007/annals.2011.174.3.8
- Peter Bürgisser and Felipe Cucker, Condition, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 349, Springer, Heidelberg, 2013. The geometry of numerical algorithms. MR 3098452, DOI 10.1007/978-3-642-38896-5
- Peter Bürgisser and Antonio Lerario, Probabilistic Schubert calculus.
- Jean-Pierre Dedieu, Gregorio Malajovich, and Michael Shub, Adaptive step-size selection for homotopy methods to solve polynomial equations, IMA J. Numer. Anal. 33 (2013), no. 1, 1–29. MR 3020948, DOI 10.1093/imanum/drs007
- Jean-Pierre Dedieu, Points fixes, zéros et la méthode de Newton, Mathématiques & Applications (Berlin) [Mathematics & Applications], vol. 54, Springer, Berlin, 2006 (French). With a preface by Steve Smale. MR 2510891
- James W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), no. 182, 449–480. MR 929546, DOI 10.1090/S0025-5718-1988-0929546-7
- Alan Stuart Edelman, Eigenvalues and condition numbers of random matrices, ProQuest LLC, Ann Arbor, MI, 1989. Thesis (Ph.D.)–Massachusetts Institute of Technology. MR 2941174
- Herbert Federer, Curvature measures, Trans. Amer. Math. Soc. 93 (1959), 418–491. MR 110078, DOI 10.1090/S0002-9947-1959-0110078-1
- Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
- Jonathan D. Hauenstein and Alan C. Liddell Jr., Certified predictor-corrector tracking for Newton homotopies, J. Symbolic Comput. 74 (2016), 239–254. MR 3424041, DOI 10.1016/j.jsc.2015.07.001
- Jonathan D. Hauenstein and Frank Sottile, Algorithm 921: alphaCertified: certifying solutions to polynomial systems, ACM Trans. Math. Software 38 (2012), no. 4, Art. 28, 20. MR 2972672, DOI 10.1145/2331130.2331136
- Christopher J. Hillar and Lek-Heng Lim, Most tensor problems are NP-hard, J. ACM 60 (2013), no. 6, Art. 45, 39. MR 3144915, DOI 10.1145/2512329
- Alston S. Householder, Unitary triangularization of a nonsymmetric matrix, J. Assoc. Comput. Mach. 5 (1958), 339–342. MR 111128, DOI 10.1145/320941.320947
- Ralph Howard, The kinematic formula in Riemannian homogeneous spaces, Mem. Amer. Math. Soc. 106 (1993), no. 509, vi+69. MR 1169230, DOI 10.1090/memo/0509
- William Kahan, Accurate eigenvalues of a symmetric tri-diagonal matrix, Stanford University, 1966.
- Pierre Lairez, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Found. Comput. Math. 17 (2017), no. 5, 1265–1292. MR 3709332, DOI 10.1007/s10208-016-9319-7
- Gregorio Malajovich, On generalized Newton algorithms: quadratic convergence, path-following and error analysis, Theoret. Comput. Sci. 133 (1994), no. 1, 65–84. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294426, DOI 10.1016/0304-3975(94)00065-4
- Gregorio Malajovich, Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric, Found. Comput. Math. 19 (2019), no. 1, 1–53. MR 3913871, DOI 10.1007/s10208-018-9375-2
- J. Renegar, On the efficiency of Newton’s method in approximating all zeros of a system of complex polynomials, Math. Oper. Res. 12 (1987), no. 1, 121–148. MR 882846, DOI 10.1287/moor.12.1.121
- James Renegar, On the worst-case arithmetic complexity of approximating zeros of systems of polynomials, SIAM J. Comput. 18 (1989), no. 2, 350–370. MR 986672, DOI 10.1137/0218024
- Michael Shub, On the distance to the zero set of a homogeneous polynomial, J. Complexity 5 (1989), no. 3, 303–305. MR 1018021, DOI 10.1016/0885-064X(89)90027-7
- Michael Shub, Some remarks on Bezout’s theorem and complexity theory, From Topology to Computation: Proceedings of the Smalefest (Berkeley, CA, 1990) Springer, New York, 1993, pp. 443–455. MR 1246139
- Michael Shub, Complexity of Bezout’s theorem. VI. Geodesics in the condition (number) metric, Found. Comput. Math. 9 (2009), no. 2, 171–178. MR 2496558, DOI 10.1007/s10208-007-9017-6
- Michael Shub and Steve Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Amer. Math. Soc. 6 (1993), no. 2, 459–501. MR 1175980, DOI 10.1090/S0894-0347-1993-1175980-4
- M. Shub and S. Smale, Complexity of Bezout’s theorem. II. Volumes and probabilities, Computational algebraic geometry (Nice, 1992) Progr. Math., vol. 109, Birkhäuser Boston, Boston, MA, 1993, pp. 267–285. MR 1230872, DOI 10.1007/978-1-4612-2752-6_{1}9
- Michael Shub and Steve Smale, Complexity of Bezout’s theorem. III. Condition number and packing, J. Complexity 9 (1993), no. 1, 4–14. Festschrift for Joseph F. Traub, Part I. MR 1213484, DOI 10.1006/jcom.1993.1002
- M. Shub and S. Smale, Complexity of Bezout’s theorem. V. Polynomial time, Theoret. Comput. Sci. 133 (1994), no. 1, 141–164. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). MR 1294430, DOI 10.1016/0304-3975(94)90122-8
- Michael Shub and Steve Smale, Complexity of Bezout’s theorem. IV. Probability of success; extensions, SIAM J. Numer. Anal. 33 (1996), no. 1, 128–148. MR 1377247, DOI 10.1137/0733008
- Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87–121. MR 799791, DOI 10.1090/S0273-0979-1985-15391-1
- Steve Smale, Newton’s method estimates from data at one point, The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985) Springer, New York, 1986, pp. 185–196. MR 870648
- Steve Smale, Mathematical problems for the next century, Math. Intelligencer 20 (1998), no. 2, 7–15. MR 1631413, DOI 10.1007/BF03025291
Bibliographic 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