Fast computation of zeros of polynomial systems with bounded degree under finite-precision

Briquel, Irénée; Cucker, Felipe; Peña, Javier; Roshchina, Vera

doi:10.1090/S0025-5718-2013-02765-2

Fast computation of zeros of polynomial systems with bounded degree under finite-precision
HTML articles powered by AMS MathViewer

by Irénée Briquel, Felipe Cucker, Javier Peña and Vera Roshchina;

Math. Comp. 83 (2014), 1279-1317

DOI: https://doi.org/10.1090/S0025-5718-2013-02765-2

Published electronically: September 10, 2013

PDF | Request permission

Abstract:

A solution for Smale’s 17th problem, for the case of systems with bounded degree was recently given. This solution, an algorithm computing approximate zeros of complex polynomial systems in average polynomial time, assumed infinite precision. In this paper we describe a finite-precision version of this algorithm. Our main result shows that this version works within the same time bounds and requires a precision which, on the average, amounts to a polynomial amount of bits in the mantissa of the intervening floating-point numbers.

References

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 and Anton Leykin, Certified numerical homotopy tracking, Exp. Math. 21 (2012), no. 1, 69–83. MR 2904909, DOI 10.1080/10586458.2011.606184
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
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
Åke Björck, Numerical methods for least squares problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1386889, DOI 10.1137/1.9781611971484
Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636, DOI 10.1007/978-1-4612-0701-6
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
Felipe Cucker, Teresa Krick, Gregorio Malajovich, and Mario Wschebor, A numerical algorithm for zero counting. I. Complexity and accuracy, J. Complexity 24 (2008), no. 5-6, 582–605. MR 2467589, DOI 10.1016/j.jco.2008.03.001
Felipe Cucker and Steve Smale, Complexity estimates depending on condition and round-off error, J. ACM 46 (1999), no. 1, 113–184. MR 1692497, DOI 10.1145/300515.300519
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629
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, 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, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 271–294. MR 1754783