Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Foundations of Computational Mathematics
Erschienen in: Foundations of Computational Mathematics 2/2013

01.04.2013

Robust Certified Numerical Homotopy Tracking

verfasst von: Carlos Beltrán, Anton Leykin

Erschienen in: Foundations of Computational Mathematics | Ausgabe 2/2013

Einloggen

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

search-config
loading …

Abstract

We describe, for the first time, a completely rigorous homotopy (path-following) algorithm (in the Turing machine model) to find approximate zeros of systems of polynomial equations. If the coordinates of the input systems and the initial zero are rational our algorithm involves only rational computations, and if the homotopy is well posed an approximate zero with integer coordinates of the target system is obtained. The total bit complexity is linear in the length of the path in the condition metric, and polynomial in the logarithm of the maximum of the condition number along the path, and in the size of the input.
Vorheriger Artikel Classifying Clustering Schemes

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
Fußnoten
1
This property inspired its definition, see [33].
 
2
If \(R\geq\sqrt{2}\) then values t i as described in Algorithm 1 exist. They also exist for smaller values of R>1 like R=1.0003 but taking \(R\geq\sqrt {2}\) will make our formulas look prettier. This assumption does not affect much to the running time of the algorithm. We will only use R 2 in the algorithm. Hence, we take \(R\in\sqrt{{\mathbb{Q}}}\).
 
3
Note the slight abuse of notation: we just use ζ i the zero of \(g_{i}=f_{s_{i}}\), so we should actually denote it by \(\zeta_{s_{i}}\).
 
4
Recall that \(d_{\mathrm{R}}(x,y)=\arccos\frac{\langle x,y\rangle}{\| x\|\|y\|}\) is the usual distance from x to y as projective points in ℙ(ℂ n+1).
 
5
By a.o. we mean an operation of the form +,−,×,/, or a comparison <,≤ or an assignment of a value to a variable, or computation of the integer part of a number.
 
6
Exact linear algebra is a large research field, see http://​linalg.​org/​people.​html for a list of people working on the subject, as well as software and research articles.
 
Literatur
1.
D.J. Bates, C. Peterson, A.J. Sommese, C.W. Wampler, Numerical computation of the genus of an irreducible curve within an algebraic set, J. Pure Appl. Algebra 215(8), 1844–1851 (2011). MathSciNetMATHCrossRef
2.
3.
4.
C. Beltrán, A continuation method to solve polynomial systems, and its complexity, Numer. Math. 117(1), 89–113 (2011). MathSciNetMATHCrossRef
5.
6.
C. Beltrán, L.M. Pardo, On Smale’s 17th problem: a probabilistic positive solution, Found. Comput. Math. 8(1), 1–43 (2008). MathSciNetMATHCrossRef
7.
C. Beltrán, L.M. Pardo, Smale’s 17th problem: average polynomial time to compute affine and projective solutions, J. Am. Math. Soc. 22, 363–385 (2009). MATHCrossRef
8.
C. Beltrán, L.M. Pardo, Fast linear homotopy to find approximate zeros of polynomial systems, Found. Comput. Math. 11(1), 95–129 (2011). MathSciNetMATHCrossRef
9.
S. Billey, R. Vakil, Intersections of Schubert varieties and other permutation array schemes, in Algorithms in Algebraic Geometry, ed. by A. Dickenstein, F.O. Schreyer, A.J. Sommese. The IMA Vol. Math. Appl., vol. 146 (Springer, New York, 2008), pp. 21–54. CrossRef
10.
L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers; NP completeness, recursive functions and universal machines, Bull. Am. Math. Soc. 21, 1–46 (1989). MathSciNetMATHCrossRef
11.
L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation (Springer, New York, 1998). CrossRef
12.
P. Bürguisser, F. Cucker, On a problem posed by Steve Smale, Ann. Math. 174, 1785–1836 (2011). CrossRef
13.
D. Castro, K. Hägele, J.E. Morais, L.M. Pardo, Kronecker’s and Newton’s approaches to solving: a first comparison, J. Complex. 17(1), 212–303 (2001). MATHCrossRef
14.
D. Castro, J.L. Montaña, L.M. Pardo, J. San Martín, The distribution of condition numbers of rational data of bounded bit length, Found. Comput. Math. 2(1), 1–52 (2002). MathSciNetMATH
15.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms (MIT Press, Cambridge, 1990). MATH
16.
J.-P. Dedieu, G. Malajovich, M. Shub, Adaptative step size selection for homotopy methods to solve polynomial equations, IMA J. Numer. Anal. (2010). doi:10.​1093/​imanum/​drs007.
17.
18.
19.
20.
21.
M.H. Kim, Computational complexity of the Euler type algorithms for the roots of complex polynomials. Ph.D. Thesis, The City University of New York, 1985.
22.
23.
A. Leykin, Numerical algebraic geometry for Macaulay2, J. Softw. Algebr. Geom. 3, 5–10 (2011). MathSciNet
24.
A. Leykin, F. Sottile, Galois groups of Schubert problems via homotopy computation, Math. Comput. 78(267), 1749–1765 (2009). MathSciNetMATHCrossRef
25.
G. Malajovich, On the complexity of path-following Newton algorithms for solving systems of polynomial equations with integer coefficients. Ph.D. Thesis, Univ. California, Berkley, 1993.
26.
G. Malajovich, On generalized Newton algorithms: quadratic convergence, path-following and error analysis, Theor. Comput. Sci. 133, 65–84 (1994). MathSciNetMATHCrossRef
27.
28.
29.
C.H. Papadimitriou, Computational Complexity (Addison-Wesley, Reading, 1994). MATH
30.
M. Shub, Some remarks on Bezout’s theorem and complexity theory, in From Topology to Computation: Proceedings of the Smalefest, ed. by M.W. Hirsch, J.E. Marsden, M. Shub (Springer, New York, 1993), pp. 443–455. CrossRef
31.
M. Shub, Complexity of Bézout’s theorem. VI: Geodesics in the condition (number) metric, Found. Comput. Math. 9(2), 171–178 (2009). MathSciNetMATHCrossRef
32.
M. Shub, S. Smale, Complexity of Bézout’s theorem. II. Volumes and probabilities, in Computational Algebraic Geometry, ed. by Fr. Eyssette, A. Galligo. Progr. Math., vol. 109 (Birkhäuser, Boston, 1993), pp. 267–285. CrossRef
33.
M. Shub, S. Smale, Complexity of Bézout’s theorem. I. Geometric aspects, J. Am. Math. Soc. 6(2), 459–501 (1993). MathSciNetMATH
34.
M. Shub, S. Smale, Complexity of Bezout’s theorem. V. Polynomial time, in Selected Papers of the Workshop on Continuous Algorithms and Complexity, Barcelona, 1993. Theoret. Comput. Sci., vol. 133 (1994), pp. 141–164.
35.
36.
S. Smale, Newton’s method estimates from data at one point, in The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics (Springer, New York, 1986), pp. 185–196. CrossRef
37.
J. van der Hoeven, Reliable homotopy continuation. Technical Report, HAL 00589948 (2011).
38.
Metadaten
Titel
Robust Certified Numerical Homotopy Tracking
verfasst von
Carlos Beltrán
Anton Leykin
Publikationsdatum
01.04.2013
Verlag
Springer-Verlag
Erschienen in
Foundations of Computational Mathematics / Ausgabe 2/2013
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-013-9143-2

Weitere Artikel der Ausgabe 2/2013

Foundations of Computational Mathematics 2/2013 Zur Ausgabe

OriginalPaper

Backward Error Analysis and the Substitution Law for Lie Group Integrators

OriginalPaper

Classifying Clustering Schemes

OriginalPaper

ENO Reconstruction and ENO Interpolation Are Stable

OriginalPaper

Convergence of Lowest Order Semi-Lagrangian Schemes

Premium Partner

    Bildnachweise