nach oben

Foundations of Computational Mathematics

Erschienen in:

18.05.2016

A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time

verfasst von: Pierre Lairez

Erschienen in: Foundations of Computational Mathematics | Ausgabe 5/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum–Shub–Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.

Vorheriger Artikel Bivariate Factorization Using a Critical Fiber

Nächster Artikel Computing Mixed Volume and All Mixed Cells in Quermassintegral Time

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

See, e.g., [18] or [19]; unfortunately the Gaussian distribution that they assume does not fit the situation here.

I thank one of the referees for having communicated this method to me.

Michael Shub. Complexity of Bezout’s theorem. VI. Geodesics in the condition (number) metric. In: Found. Comput. Math. 9.2 (2009), pp. 171–178. doi:10.1007/s10208-007-9017-6.

Michael Shub and Steve Smale. Complexity of Bézout’s theorem. I. Geometric aspects. In: J. Amer. Math. Soc. 6.2 (1993), pp. 459–501. doi:10.2307/2152805.

Michael Shub and Steve Smale. Complexity of Bezout’s theorem. II. Volumes and probabilities. In: Computational algebraic geometry (Nice, 1992). Vol. 109. Progr. Math. Birkhäuser Boston, Boston, MA, 1993, pp. 267–285.

Michael Shub and Steve Smale. Complexity of Bezout’s theorem. IV. Probability of success; extensions. In: SIAM J. Numer. Anal. 33.1 (1996), pp. 128–148. doi:10.1137/0733008.

Michael Shub and Steve Smale. Complexity of Bezout’s theorem. V. Polynomial time. In: Theoret. Comput. Sci. 133.1 (1994). Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993), pp. 141–164. doi:10.1016/0304-3975(94)90122-8.

Steve Smale. Newton’s method estimates from data at one point. In: The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985). Springer, New York, 1986, pp. 185–196. doi:10.1007/978-1-4612-4984-9_13.

Steve Smale. Mathematical problems for the next century. In: The Mathematical Intelligencer 20.2 (1998), pp. 7–15. doi:10.1007/BF03025291.

Lenore Blum, Michael Shub, and Steve Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. In: Bull. Amer. Math. Soc. N.S. 21.1 (1989), pp. 1–46. doi:10.1090/S0273-0979-1989-15750-9.

Carlos Beltrán and Luis Miguel Pardo. Fast linear homotopy to find approximate zeros of polynomial systems. In: Found. Comput. Math. 11.1 (2011), pp. 95–129. doi:10.1007/s10208-010-9078-9.

10.

Peter Bürgisser and Felipe Cucker. On a problem posed by Steve Smale. In: Ann. of Math. (2) 174.3 (2011), pp. 1785–1836. doi:10.4007/annals.2011.174.3.8.

11.

Peter Bürgisser and Felipe Cucker. Condition. The geometry of numerical algorithms. Vol. 349. Grundlehren der Mathematischen Wissenschaften. Springer Berlin Heidelberg, 2013. doi:10.1007/978-3-642-38896-5.

12.

Carlos Beltrán and Luis Miguel Pardo. Smale’s 17th problem: average polynomial time to compute affine and projective solutions. In: J. Amer. Math. Soc. 22.2 (2009), pp. 363–385. doi:10.1090/S0894-0347-08-00630-9.

13.

Daniel Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. ACM, New York, 2001, 296–305 (electronic). doi:10.1145/380752.380813.

14.

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. In: Math. Comp. 83.287 (2014), pp. 1279–1317. doi:10.1090/S0025-5718-2013-02765-2.

15.

Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and real computation. Springer-Verlag, New York, 1998. doi:10.1007/978-1-4612-0701-6.

16.

Michael Shub. Some remarks on Bezout’s theorem and complexity theory. In: From Topology to Computation: Proceedings of the Smalefest. Springer, New York, 1993. Chap. 40, pp. 443–455. doi:10.1007/978-1-4612-2740-3_40.

17.

Masaaki Sibuya. A method for generating uniformly distributed points on N-dimensional spheres. In: Ann. Inst. Statist. Math. 14 (1962), pp. 81–85. doi:10.1007/BF02868626.

18.

Diego Armentano, Carlos Beltrán, Peter Bürgisser, Felipe Cucker, and Michael Shub. A stable, polynomial-time algorithm for the eigenpair problem. 2015. arXiv:1505.03290.

19.

Diego Armentano and Felipe Cucker. A randomized homotopy for the Hermitian eigenpair problem. In: Found. Comput. Math. 15.1 (2015), pp. 281–312. doi:10.1007/s10208-014-9217-9.

20.

William Kahan. Accurate eigenvalues of a symmetric tri-diagonal matrix. Tech. rep. CS41. Stanford University, 1966.

21.

Walter Baur and Volker Strassen. The complexity of partial derivatives. In: Theoretical Computer Science 22.3 (1983), pp. 317 –330. doi:10.1016/0304-3975(83)90110-X.

22.

Diego Armentano, Carlos Beltrán, Peter Bürgisser, Felipe Cucker, and Michael Shub. Condition length and complexity for the solution of polynomial systems. In: Found. Comput. Math. (2016). doi:10.1007/s10208-016-9309-9.

23.

Carlos Beltrán. A continuation method to solve polynomial systems and its complexity. In: Numer. Math. 117.1 (2011), pp. 89–113. doi:10.1007/s00211-010-0334-3.

Titel: A Deterministic Algorithm to Compute Approximate Roots of Polynomial Systems in Polynomial Average Time
verfasst von: Pierre Lairez
Publikationsdatum: 18.05.2016
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 5/2017
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-016-9319-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 5/2017

A Bousfield–Kan Algorithm for Computing the Effective Homotopy of a Space

Rigorous Computer-Assisted Application of KAM Theory: A Modern Approach

Mathematics of the Genome

Bivariate Factorization Using a Critical Fiber

Computing Mixed Volume and All Mixed Cells in Quermassintegral Time

Premium Partner