Stability of the Lanczos algorithm on matrices with regular spectral distributions

DOI10.1016/J.LAA.2023.11.006arXiv2302.14842OpenAlexW4388686898MaRDI QIDQ6185983FDOQ6185983

Authors: Tyler Chen, Thomas Trogdon 

Publication date: 9 January 2024

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

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.

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

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

zbMATH Keywords

random matrixLanczosfinite precision arithmetic

Mathematics Subject Classification ID

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

Cites Work

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

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)