Stability of the Lanczos algorithm on matrices with regular spectral distributions

DOI10.1016/J.LAA.2023.11.006MaRDI QIDQ6185983zbMATH OpenOpenAlexFDO

Authors Tyler Chen, Thomas Trogdon

Publication date 9 January 2024

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.14842

zbMATH Keywords

finite precision arithmeticLanczosrandom matrix

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Roundoff error (65G50)

Abstract: We study the stability of the Lanczos algorithm run on problems whose eigenvector empirical spectral distribution is near to a reference measure with well-behaved orthogonal polynomials. We give a backwards stability result which can be upgraded to a forward stability result when the reference measure has a density supported on a single interval with square root behavior at the endpoints. Our analysis implies the Lanczos algorithm run on many large random matrix models is fact forward stable, and hence nearly deterministic, even when computations are carried out in finite precision arithmetic. Since the Lanczos algorithm is not forward stable in general, this provides yet another example of the fact that random matrices are far from ``any old matrix, and care must be taken when using them to test numerical algorithms.

Review text

The authors consider the problem of stability of the Lanczos algorithm, being specifically run, on problems whose eigenvector empirical spectral distribution is close to a reference measure with well-behaved orthogonal polynomials. A backward stability result is presented. This can be upgraded to a forward stability result when the reference measure has a density supported on a single interval with square root behavior at the endpoints. An inference that could be drawn, in particular, is that the Lanczos algorithm run on many large random matrix models, even when computations are carried out in finite precision arithmetic, is actually forward stable, and therefore is nearly deterministic. Since, in general, the Lanczos algorithm is not forward stable, the investigation carried here, implies that care must be taken when using them to test numerical algorithms.

Recommendations

• scientific article; zbMATH DE number 1131718
• The Lanczos Algorithm Under Few Iterations: Concentration and Location of the Output
• Probabilistic Bounds on the Extremal Eigenvalues and Condition Number by the Lanczos Algorithm
• Stability of the Lanczos method for matrix function approximation
• On Stabilization and Convergence of Clustered Ritz Values in the Lanczos Method

Cites work

• A Dynamical Approach to Random Matrix Theory
• Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem
• Accuracy of the Lanczos process for the eigenproblem and solution of equations
• An augmented stability result for the Lanczos Hermitian matrix tridiagonalization process
• Anisotropic local laws for random matrices
• Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
• Carleson curves, Muckenhoupt weights, and Toeplitz operators
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• Eigenvalue distributions of large Hermitian matrices; Wigner's semi- circle law and a theorem of Kac, Murdock, and Szegö
• Error Analysis of the Lanczos Algorithm for Tridiagonalizing a Symmetric Matrix
• Error bounds in the simple Lanczos procedure for computing functions of symmetric matrices and eigenvalues
• Fast computation of Gauss quadrature nodes and weights on the whole real line
• scientific article; zbMATH DE number 1049350 (Why is no real title available?)
• scientific article; zbMATH DE number 1049353 (Why is no real title available?)
• scientific article; zbMATH DE number 1996432 (Why is no real title available?)
• scientific article; zbMATH DE number 2107939 (Why is no real title available?)
• scientific article; zbMATH DE number 3301601 (Why is no real title available?)
• scientific article; zbMATH DE number 3341573 (Why is no real title available?)
• Matrix models for beta ensembles
• Methods of conjugate gradients for solving linear systems
• No eigenvalues outside the support of the limiting spectral distribution of large-dimensional sample covariance matrices
• Numerical solution of Riemann-Hilbert problems: random matrix theory and orthogonal polynomials
• On Generating Orthogonal Polynomials
• On sensitivity of Gauss-Christoffel quadrature
• On the condition of orthogonal polynomials via modified moments
• Orthogonal polynomials and random matrices: a Riemann-Hilbert approach.
• Practical use of the symmetric Lanczos process with re-orthogonalization
• Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
• Random matrix theory
• Some History of the Conjugate Gradient and Lanczos Algorithms: 1948–1976
• Spectra of Jacobi operators via connection coefficient matrices
• Stability of the Lanczos method for matrix function approximation
• The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic
• The isomonodromy approach to matrix models in 2D quantum gravity
• The Lanczos and conjugate gradient algorithms in finite precision arithmetic
• The Riemann--Hilbert approach to strong asymptotics for orthogonal polynomials on [-1,1]
• The simple Lanczos procedure: Estimates of the error of the Gauss quadrature formula and their applications

This page was built for publication: Stability of the Lanczos algorithm on matrices with regular spectral distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185983)