nach oben

Foundations of Computational Mathematics

Erschienen in:

01.04.2014

Complexity of Path-Following Methods for the Eigenvalue Problem

verfasst von: Diego Armentano

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

A unitarily invariant projective framework is introduced to analyze the complexity of path-following methods for the eigenvalue problem. A condition number, and its relation to the distance to ill-posedness, is given. A Newton map appropriate for this context is defined, and a version of Smale’s \(\gamma \)-theorem is proven. The main result of this paper bounds the complexity of path-following methods in terms of the length of the path in the condition metric.

Nächster Artikel Adaptive Wavelet Methods for Linear and Nonlinear Least-Squares Problems

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

Nur mit Berechtigung zugänglich

If \(A\in \mathbb {P}(\mathbb {C}^{n\times n})\setminus \Sigma \), then \(A\) has \(n\) distinct eigenvalues; thus, the cardinal number of \(\pi ^{-1}(A)\) coincides with \(\deg _{(n^2-1,0)}(\mathcal {V})\). In Proposition 2.14 we give an independent proof of this fact, which we consider interesting per se.

D. Armentano: Ph.D. Thesis. Universidad de la República, Uruguay, and Université Paul Sabatier, France (2013).

D. Armentano and M. Shub: Smale’s fundamental theorem of algebra reconsidered. Found Comput Math vol. 14, no. 1, (2014), 85–114.

S. Batterson and J. Smillie: Rayleigh quotient iteration fails for nonsymmetric matrices, Appl Math Lett, 2 (1989) 19–20.

S. Batterson and J. Smillie: Rayleigh quotient iteration for nonsymmetric matrices, Math Comp 191 (1990) 169–178.

C. Beltrán: A continuation method to solve polynomial systems, and its complexity, Numerische Mathematik 117, no. 1 (2011), 89113.

C. Beltrán, J.P. Dedieu, G. Malajovich and M. Shub: Convexity properties of the condition number. SIAM J Matrix Anal Appl 31 No 3, pp 1491–1506 (2010).

C. Beltrán, J.P. Dedieu, G. Malajovich and M. Shub: Convexity properties of the condition number II. SIAM J Matrix Anal Appl 33(3) pp 905–939 (2012).

C. Beltrán and L. M. Pardo: Smale’s 17th problem: average polynomial time to compute affine and projective solutions, J Am Math Soc 22 (2009), no. 2, 363–385. MR 2476778 (2009m:90147).

C. Beltrán and M.Shub: The complexity and geometry of numerically solving polynomial systems. Recent advances in real complexity and computation. Contemp Math 2013; Volume: 604.

10.

C. Beltrán and M.Shub: Complexity of Bézout’s theorem VII: Distances estimates in the condition metric. Found Comput Math, 9 (2009) 179–195.

11.

L. Blum, F. Cucker, M. Shub and S. Smale: Complexity and real computation. Springer, New York, 1998.

12.

I. Briquel, F. Cucker, J. Peña, and V. Roshchina: Fast Computation of Zeros of Polynomial Systems with Bounded Degree under Variable-precision. Math Comput. doi:10.1090/S0025-5718-2013-02765-2

13.

P. Bürguisser and F. Cucker: On a problem posed by Steve Smale. Ann Math, 174(3): 1785–1836 (2011).

14.

C. D’Andrea, T. Krick and M. Sombra: Heights of varieties in multiprojective spaces and arithmetic Nullstellensätze. Annales Scientifiques de l’ENS, 4, 549–627, (2013).

15.

M.T. Chu: A simple application of the homotopy method to symmetric eigenvalue problems. Linear Algebra Appl, 59 (1984), pp. 8590.

16.

J.P. Dedieu: Points Fixes, Zéros et la Méthode de Newton. Mathématiques & Applications SMAI-Springer, Berlin, 54, 2006.

17.

J-P. Dedieu, G. Malajovich and M. Shub: Adaptative step size selection for homotopy methods to solve polynomial equations. IMA J Numer Anal 33, No. 1, 1–29 (2013).

18.

J.P. Dedieu and M. Shub: Multihomogeneous Newton Methods. Math Comput vol. 69, no. 231, (1999), 1071–1098.

19.

P. Deift: Some open problems in random matrix theory and the theory of integrable systems. Contemp Math, 458 (2008), 419–430.

20.

J. Demmel: The Probability that a numerical analysis problem is difficult. Math Comput vol. 50, (1988), 449–480.

21.

W. Fulton: Intersection Theory. Springer, Berlin, 1984.

22.

G. Golub and C. van Loan: Matrix Computations, third edition, The Johns Hopkins University Press, Baltimore 1996.

23.

T.Y. Li: Numerical solution of multivariate polynomial systems by homotopy continuation methods. Acta Numer, 6, Cambridge University Press, Cambridge, (1997), 399436.

24.

T.Y. Li, and T. Sauer: Homotopy method for generalized eigenvalue problems Ax=Bx. Linear Algebra Appl 91 (1987), 6574.

25.

T.Y. Li, T. Sauer, and J. Yorke: Numerical solution of a class of deficient polynomial systems. SIAM J Numer Anal 24 (1987), no. 2, 435451.

26.

S. H. Lui, H. B. Keller, and T. W. C. Kwok: Homotopy method for the large, sparse, real nonsymmetric eigenvalue problem, SIAM J Matrix Anal Appl 18(2), volume 18, 312333, 1997.

27.

D. Mumford: Algebraic Geometry I Complex Projective Varieties. Springer, Berlin, 1976.

28.

V.Y. Pan: Optimal and nearly optimal algorithms for approximating polynomial zeros, Comput Math Appl, vol 31, (1996), 97–138.

29.

C. W. Pfrang, P. Deift, G. Menon: How long does it take to compute the eigenvalues of a random symmetric matrix? http://arxiv.org/abs/1203.4635. Accessed 5 May 2013.

30.

J. Renegar: On the worst-case arithmetic complexity of approximating zeros of polynomials. J Complex 3 (1987), no. 2, 90113.

31.

M. Shub: Complexity of Bezout’s theorem. VI. Geodesics in the Condition (Number) Metric. Found Comput Math 9, (2009), 171–178.

32.

M. Shub and S. Smale: Complexity of Bezout’s theorem. I. Geometrical Aspects. J Am Math Soc vol. 6, no. 1, (1993), 459–501.

33.

M. Shub and S. Smale: Complexity of Bezout’s theorem. IV. Probability of success; extensions. SIAM J Numer Anal 33, no. 1, (1996),128–148.

34.

M. Shub and S. Smale: Complexity of Bezout’s theorem. V. Polynomial time. Theoret Comput Sci 133, no. 1, (1994),141–164.

35.

G.W. Stewart: Matrix Algorithms: Eigensystems, SIAM, 2001.

36.

G.W. Stewart and J. Sun : Matrix perturbation theory. Academic Press, New York 1990.

37.

L.N. Trefethen and D. Bau: Numerical linear algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. xii+361.

38.

D. S. Watkins: The Matrix Eigenvalue Problem. GR and Krylov Subspaces Methods. SIAM, 2007.

39.

J.H. Wilkinson: The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965.

40.

J.H. Wilkinson: Note on matrices with a very ill-conditioned eigenproblem. Numer Math, vol 19, (1972), 176–178.

Titel: Complexity of Path-Following Methods for the Eigenvalue Problem
verfasst von: Diego Armentano
Publikationsdatum: 01.04.2014
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 2/2014
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-013-9185-5

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 2/2014

Efficient Recognition of Totally Nonnegative Matrix Cells

Geometric Generalisations of shake and rattle

On the Distribution of Atkin and Elkies Primes

Adaptive Wavelet Methods for Linear and Nonlinear Least-Squares Problems

Parabolic Molecules