How well-conditioned can the eigenvector problem be?
HTML articles powered by AMS MathViewer
- by Carlos Beltrán, Laurent Bétermin, Peter Grabner and Stefan Steinerberger HTML | PDF
- Math. Comp. 91 (2022), 1237-1245 Request permission
Abstract:
The condition number for eigenvector computations is a well-studied quantity. But how small can it possibly be? Specifically, what matrices are perfectly conditioned with respect to eigenvector computations? In this note we answer this question for $n \times n$ matrices, giving a solution that is exact to first-order as $n \rightarrow \infty$.References
- R. Alam and S. Bora, On sensitivity of eigenvalues and eigendecompositions of matrices, Linear Algebra Appl. 396 (2005), 273–301. MR 2112210, DOI 10.1016/j.laa.2004.10.013
- Diego Armentano, Carlos Beltrán, Peter Bürgisser, Felipe Cucker, and Michael Shub, A stable, polynomial-time algorithm for the eigenpair problem, J. Eur. Math. Soc. (JEMS) 20 (2018), no. 6, 1375–1437. MR 3801817, DOI 10.4171/JEMS/789
- Jess Banks, Jorge Garza-Vargas, Archit Kulkarni, and Nikhil Srivastava, Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, CA, [2020] ©2020, pp. 529–540. MR 4232064, DOI 10.1109/FOCS46700.2020.00056
- 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, DOI 10.1007/978-3-642-38896-5
- James Weldon Demmel, On condition numbers and the distance to the nearest ill-posed problem, Numer. Math. 51 (1987), no. 3, 251–289. MR 895087, DOI 10.1007/BF01400115
- James W. Demmel, The probability that a numerical analysis problem is difficult, Math. Comp. 50 (1988), no. 182, 449–480. MR 929546, DOI 10.1090/S0025-5718-1988-0929546-7
- L. Fejes, Über einen geometrischen Satz, Math. Z. 46 (1940), 83–85 (German). MR 1587, DOI 10.1007/BF01181430
- L. Fejes, Über die dichteste Kugellagerung, Math. Z. 48 (1943), 676–684 (German). MR 9129, DOI 10.1007/BF01180035
- Peter D. Lax and Ralph S. Phillips, The asymptotic distribution of lattice points in Euclidean and non-Euclidean spaces, J. Functional Analysis 46 (1982), no. 3, 280–350. MR 661875, DOI 10.1016/0022-1236(82)90050-7
- A. M. Turing, Rounding-off errors in matrix processes, Quart. J. Mech. Appl. Math. 1 (1948), 287–308. MR 28100, DOI 10.1093/qjmam/1.1.287
- Charles Van Loan, On estimating the condition of eigenvalues and eigenvectors, Linear Algebra Appl. 88/89 (1987), 715–732. MR 882468, DOI 10.1016/0024-3795(87)90131-5
- John von Neumann and H. H. Goldstine, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021–1099. MR 24235, DOI 10.1090/S0002-9904-1947-08909-6
- J. H. Wilkinson, Note on matrices with a very ill-conditioned eigenproblem, Numer. Math. 19 (1972), 176–178. MR 311092, DOI 10.1007/BF01402528
Additional Information
- Carlos Beltrán
- Affiliation: Facultad de Ciencias, Universidad of Cantabria, 39005 Santander, Spain
- MR Author ID: 764504
- ORCID: 0000-0002-0689-8232
- Email: beltranc@unican.es
- Laurent Bétermin
- Affiliation: Institut Camille Jordan, Université Claude Bernard Lyon 1, 69622 Villeurbanne, France
- ORCID: 0000-0003-4070-3344
- Email: betermin@math.univ-lyon1.fr
- Peter Grabner
- Affiliation: Institute of Analysis and Number Theory, Graz University of Technology, Kopernikusgasse 24, 8010 Graz, Austria
- MR Author ID: 293266
- ORCID: 0000-0002-0012-2302
- Email: peter.grabner@tugraz.at
- Stefan Steinerberger
- Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98195
- MR Author ID: 869041
- ORCID: 0000-0002-7745-4217
- Email: steiner@uw.edu
- Received by editor(s): June 7, 2021
- Received by editor(s) in revised form: September 14, 2021
- Published electronically: December 7, 2021
- Additional Notes: The first author was supported by grant PID2020-113887GB-I00 funded by MCIN/ AEI /10.13039/501100011033; and by Banco de Santander and Universidad de Cantabria, through grant 21.SI01.64658. The second author was supported by the Austrian Science Fund (FWF) and the German Research Foundation (DFG) through the joint project FR 4083/3-1/I 4354 during his stay at the University of Vienna. The third author was supported by the Austrian Science Fund FWF project F5503 (part of the Special Research Program (SFB) “Quasi-Monte Carlo Methods: Theory and Applications”). The fourth author was partially supported by the NSF (DMS-2123224) and the Alfred P. Sloan Foundation (FG-2021-14114)
- © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 91 (2022), 1237-1245
- MSC (2020): Primary 65F15; Secondary 31C20
- DOI: https://doi.org/10.1090/mcom/3706
- MathSciNet review: 4405494