Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: Irénée Briquel, Felipe Cucker, Javier Peña and Vera Roshchina
Journal: Math. Comp. 83 (2014), 1279-1317
MSC (2010): Primary 65G50, 65H10, 65Y20
DOI: https://doi.org/10.1090/S0025-5718-2013-02765-2
Published electronically: September 10, 2013
MathSciNet review: 3167459
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Walter Baur and Volker Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), no. 3, 317-330. MR 693063 (84c:68027), https://doi.org/10.1016/0304-3975(83)90110-X
  • [2] Carlos Beltrán and Anton Leykin, Certified numerical homotopy tracking, Exp. Math. 21 (2012), no. 1, 69-83. MR 2904909, https://doi.org/10.1080/10586458.2011.606184
  • [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 (2009h:65082), https://doi.org/10.1007/s10208-005-0211-0
  • [4] 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 (2009m:90147), https://doi.org/10.1090/S0894-0347-08-00630-9
  • [5] 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 (2011m:65111), https://doi.org/10.1007/s10208-010-9078-9
  • [6] A. Björck, Numerical methods for least squares problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1386889 (97g:65004)
  • [7] 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 (99a:68070)
  • [8] 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, https://doi.org/10.4007/annals.2011.174.3.8
  • [9] 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 (2010d:68063), https://doi.org/10.1016/j.jco.2008.03.001
  • [10] Felipe Cucker and Steve Smale, Complexity estimates depending on condition and round-off error, J. ACM 46 (1999), no. 1, 113-184. MR 1692497 (2000f:68040), https://doi.org/10.1145/300515.300519
  • [11] 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 (97g:65006)
  • [12] Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629 (97a:65047)
  • [13] 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 (95a:14002)
  • [14] 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 (2010f:65103), https://doi.org/10.1007/s10208-007-9017-6
  • [15] 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 (93k:65045), https://doi.org/10.2307/2152805
  • [16] 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 (94m:68086)
  • [17] 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 (94g:65152), https://doi.org/10.1006/jcom.1993.1002
  • [18] 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 (96d:65091), https://doi.org/10.1016/0304-3975(94)90122-8
  • [19] 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 (97k:65310), https://doi.org/10.1137/0733008
  • [20] Steve Smale, Newton's method estimates from data at one point, computational mathematics (Laramie, Wyo., 1985) Springer, New York, 1986, pp. 185-196. MR 870648 (88e:65076)
  • [21] Steve Smale, Mathematical problems for the next century, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 271-294. MR 1754783 (2001i:00003)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65G50, 65H10, 65Y20

Retrieve articles in all journals with MSC (2010): 65G50, 65H10, 65Y20


Additional Information

Irénée Briquel
Affiliation: Department of Mathematics, City University of Hong Kong, Hong Kong
Email: irenee.briquel@gmail.com

Felipe Cucker
Affiliation: Department of Mathematics, City University of Hong Kong, Hong Kong
Email: macucker@cityu.edu.hk

Javier Peña
Affiliation: Carnegie Mellon University, Tepper School of Business, Pennsylvania
Email: jfp@andrew.cmu.edu

Vera Roshchina
Affiliation: Collaborative Research Network, University of Ballarat, Australia
Email: vroshchina@ballarat.edu.au

DOI: https://doi.org/10.1090/S0025-5718-2013-02765-2
Keywords: Smale's 17th problem, finite-precision, polynomial systems
Received by editor(s): October 13, 2011
Received by editor(s) in revised form: May 7, 2012, and October 11, 2012
Published electronically: September 10, 2013
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society