nach oben

Foundations of Computational Mathematics

Erschienen in:

01.02.2015

A Randomized Homotopy for the Hermitian Eigenpair Problem

verfasst von: Diego Armentano, Felipe Cucker

Erschienen in: Foundations of Computational Mathematics | Ausgabe 1/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We describe and analyze a randomized homotopy algorithm for the Hermitian eigenvalue problem. Given an \(n\times n\) Hermitian matrix \(A\), the algorithm returns, almost surely, a pair \((\lambda ,v)\) which approximates, in a very strong sense, an eigenpair of \(A\). We prove that the expected cost of this algorithm, where the expectation is both over the random choices of the algorithm and a probability distribution on the input matrix \(A\), is \(\mathcal{{O}}(n^6)\), that is, cubic on the input size. Our result relies on a cost assumption for some pseudorandom number generators whose rationale is argued by us.

Vorheriger Artikel A Complexity Theory of Constructible Functions and Sheaves

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

D. Armentano. Stochastic perturbations and smooth condition numbers. J. Complexity, 26(2):161–171, 2010.

D. Armentano. Complexity of Path-Following Methods for the Eigenvalue Problem. Found. Comput. Math., 14(2):185–236, 2014.

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

C. Beltrán and L.M. Pardo. Fast linear homotopy to find approximate zeros of polynomial systems. Found. Comput. Math., 11(1):95–129, 2011.

I. Briquel, F. Cucker, J. Peña, and V. Roshchina. Fast computation of zeros of polynomial systems with bounded degree under finite-precision. To appear in Math. of Computation, 2013.

W. Bruns and U. Vetter. Determinantal rings, volume 1327 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1988.

P. Bürgisser and F. Cucker. On a problem posed by Steve Smale. Annals of Mathematics, 174:1785–1836, 2011.

P. Bürgisser and F. Cucker. Condition, volume 349 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 2013.

K.P. Choi. On the medians of gamma distributions and an equation of Ramanujan. Proc. Amer. Math. Soc., 121(1):245–251, 1994.

10.

P. Deift. Some open problems in random matrix theory and the theory of integrable systems. In Integrable systems and random matrices, volume 458 of Contemp. Math., pages 419–430. Amer. Math. Soc., Providence, RI, 2008.

11.

J.W. Demmel. Applied Numerical Linear Algebra. SIAM, 1997.

12.

L. Devroye. Nonuniform random variate generation. Springer-Verlag, New York, 1986.

13.

Alan Edelman and N. Raj Rao. Random matrix theory. Acta Numer., 14:233–297, 2005.

14.

W. Hrmann, J. Leydold, and G. Derflinger. Automatic nonuniform random variate generation. Springer-Verlag, New York, 2004.

15.

T.-Y. Li and T. Sauer. Homotopy method for generalized eigenvalue problems \(Ax=\lambda Bx\). Linear Algebra Appl., 91:65–74, 1987.

16.

X.H. Li and G. Menon. Numerical solution of Dyson Brownian motion and a sampling scheme for invariant matrix ensembles. J. Stat. Phys., 153(5):801–812, 2013.

17.

M.L. Mehta. Random matrices, volume 142 of Pure and Applied Mathematics (Amsterdam). Elsevier/Academic Press, Amsterdam, third edition, 2004.

18.

S. Olver and A. Townsend. Fast inverse transform sampling in one and two dimensions. Available at http://arxiv.org/pdf/1307.1223.pdf, 2013

19.

B.N. Parlett. The symmetric eigenvalue problem, volume 20 of Classics in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Corrected reprint of the 1980 original.

20.

C.W. Pfrang, P. Deift, and G. Menon. How long does it take to compute the eigenvalues of a random symmetric matrix? Available at http://arxiv.org/pdf/1203.4635.pdf, 2013

21.

M. Shub. Complexity of Bézout’s Theorem VI geodesics in the condition (number) metric. Found. Comput. Math., 9:171–178, 2009.

22.

M. Shub and S. Smale. Complexity of Bézout’s Theorem I: geometric aspects. Journal of the Amer. Math. Soc., 6:459–501, 1993.

23.

S. Smale. Newton’s method estimates from data at one point. In R. Ewing, K. Gross, and C. Martin, editors, The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics. Springer-Verlag, 1986.

24.

S. Smale. Mathematical problems for the next century. In V. Arnold, M. Atiyah, P. Lax, and B. Mazur, editors, Mathematics: Frontiers and Perspectives, pages 271–294. AMS, 2000.

Titel: A Randomized Homotopy for the Hermitian Eigenpair Problem
verfasst von: Diego Armentano
Felipe Cucker
Publikationsdatum: 01.02.2015
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 1/2015
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-014-9217-9

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 1/2015

Overdetermined Systems of Sparse Polynomial Equations

Foreword

Probabilistic Analysis of the Grassmann Condition Number

A -Conjecture for Newton Polygons

Effect of Islands in Diffusive Properties of the Standard Map for Large Parameter Values

A Complexity Theory of Constructible Functions and Sheaves

Premium Partner