A sequence of polynomials with optimal condition number
Authors:
Carlos Beltrán, Ujué Etayo, Jordi Marzo and Joaquim Ortega-Cerdà
Journal:
J. Amer. Math. Soc. 34 (2021), 219-244
MSC (2010):
Primary 65Y20
DOI:
https://doi.org/10.1090/jams/956
Published electronically:
December 8, 2020
MathSciNet review:
4188817
Full-text PDF
View in AMS MathViewer
Abstract | References | Similar Articles | Additional Information
Abstract: We find an explicit sequence of univariate polynomials of arbitrary degree with optimal condition number. This solves a problem posed by Michael Shub and Stephen Smale in 1993.
- Carlos Beltrán, A facility location formulation for stable polynomials and elliptic Fekete points, Found. Comput. Math. 15 (2015), no. 1, 125–157. MR 3303693, DOI 10.1007/s10208-014-9213-0
- Carlos Beltrán and Ujué Etayo, The diamond ensemble: a constructive set of spherical points with small logarithmic energy, J. Complexity 59 (2020), 101471, 22. MR 4099902, DOI 10.1016/j.jco.2020.101471
- 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
- Laurent Bétermin and Etienne Sandier, Renormalized energy and asymptotic expansion of optimal logarithmic energy on the sphere, Constr. Approx. 47 (2018), no. 1, 39–74. MR 3742809, DOI 10.1007/s00365-016-9357-z
- 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
- J. S. Brauchart, Optimal logarithmic energy points on the unit sphere, Math. Comp. 77 (2008), no. 263, 1599–1613. MR 2398782, DOI 10.1090/S0025-5718-08-02085-1
- J. S. Brauchart, D. P. Hardin, and E. B. Saff, The next-order term for optimal Riesz and logarithmic energy asymptotics on the sphere, Recent advances in orthogonal polynomials, special functions, and their applications, Contemp. Math., vol. 578, Amer. Math. Soc., Providence, RI, 2012, pp. 31–61. MR 2964138, DOI 10.1090/conm/578/11483
- 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
- A. Dubickas, On the maximal product of distances between points on a sphere, Liet. Mat. Rink. 36 (1996), no. 3, 303–312 (English, with English and Lithuanian summaries); English transl., Lithuanian Math. J. 36 (1996), no. 3, 241–248 (1997). MR 1455810, DOI 10.1007/BF02986850
- I. S. Gradshteyn and I. M. Ryzhik, Table of integrals, series, and products, 8th ed., Elsevier/Academic Press, Amsterdam, 2015. Translated from the Russian; Translation edited and with a preface by Daniel Zwillinger and Victor Moll; Revised from the seventh edition [MR2360010]. MR 3307944
- 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
- Y. I. Lyubarskiĭ and M. Sodin, Analogues of sine type for convex domains, Preprint no. 17, Inst. Low Temperature Phys. Eng., Ukrainian Acad. Sci., Kharkov (Russian). 1 (1986).
- Yuriĭ I. Lyubarskiĭ and Kristian Seip, Sampling and interpolation of entire functions and exponential systems in convex domains, Ark. Mat. 32 (1994), no. 1, 157–193. MR 1277924, DOI 10.1007/BF02559527
- E. A. Rakhmanov, E. B. Saff, and Y. M. Zhou, Minimal discrete energy on the sphere, Math. Res. Lett. 1 (1994), no. 6, 647–662. MR 1306011, DOI 10.4310/MRL.1994.v1.n6.a3
- Etienne Sandier and Sylvia Serfaty, From the Ginzburg-Landau model to vortex lattice problems, Comm. Math. Phys. 313 (2012), no. 3, 635–743. MR 2945619, DOI 10.1007/s00220-012-1508-x
- 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
- Steve Smale, Mathematical problems for the next century, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 271–294. MR 1754783
- Stefan, Steinerberger. On the logarithmic energy of points on $\mathbb {S}^2$, arXiv:2001.04630
- Gerold Wagner, On the product of distances to a point set on a sphere, J. Austral. Math. Soc. Ser. A 47 (1989), no. 3, 466–482. MR 1018975
Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 65Y20
Retrieve articles in all journals with MSC (2010): 65Y20
Additional Information
Carlos Beltrán
Affiliation:
Departamento de Matematicas Estadistica y Computacion, University of Cantabria, 39005 Santander, Spain
MR Author ID:
764504
ORCID:
0000-0002-0689-8232
Email:
carlos.beltran@unican.es
Ujué Etayo
Affiliation:
Institut für Analyse und Zahlentheorie, Technische Universität Graz , Kopernikusgasse 24/II 8010 Graz, Austria
ORCID:
0000-0002-7310-2978
Email:
etayo@math.tugraz.at
Jordi Marzo
Affiliation:
Departament de Matemàtiques i Informàtica, Universitat de Barcelona, Gran Via 585, 08007 Barcelona, Spain
MR Author ID:
822776
Joaquim Ortega-Cerdà
Affiliation:
Departament de Matemàtiques i Informàtica, Universitat de Barcelona, Gran Via 585, 08007 Barcelona, Spain
ORCID:
0000-0002-6616-4257
Received by editor(s):
March 5, 2019
Received by editor(s) in revised form:
March 19, 2020, and March 30, 2020
Published electronically:
December 8, 2020
Additional Notes:
The first and second authors were partially supported by Ministerio de Economía y Competitividad, Gobierno de España, through grants MTM2017-83816-P and MTM2017-90682-REDT, and by the Banco de Santander and Universidad de Cantabria grant 21.SI01.64658.
The second author was also supported by the Austrian Science Fund FWF project F5503 (part of the Special Research Program (SFB) Quasi-Monte Carlo Methods: Theory and Applications).
The third and fourth authors have been partially supported by grant MTM2017-83499-P by the Ministerio de Economía y Competitividad, Gobierno de España and by the Generalitat de Catalunya (project 2017 SGR 358).
Article copyright:
© Copyright 2020
American Mathematical Society
