Fast and accurate randomized algorithms for linear systems and eigenvalue problems

DOI10.1137/23m1565413zbMATH Open1545.65142MaRDI QIDQ6561643

Joel A. Tropp, Yuji Nakatsukasa

Publication date: 25 June 2024

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

zbMATH Keywords

sketchinglinear systemeigenvalue problemprojection methodrandomized algorithmPetrov-Galerkin methodnumerical linear algebraRayleigh-Ritzsubspace embedding

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Iterative numerical methods for linear systems (65F10) Orthogonalization in numerical linear algebra (65F25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• On the generation of Krylov subspace bases
• Faster least squares approximation
• A fast randomized algorithm for the approximation of matrices
• Analysis of the symmetric Lanczos algorithm with reorthogonalization methods
• The Tchebychev iteration for nonsymmetric linear systems
• The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
• Randomized linear algebra for model reduction. II: Minimal residual methods and dictionary-based approximation
• Randomized block Krylov methods for approximating extreme eigenvalues
• Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
• Condition numbers and equilibration of matrices
• Matrix algorithms. Vol. 2: Eigensystems
• Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method
• A Krylov--Schur algorithm for large eigenproblems
• An algorithm for the generalized eigenvalue problem for nonsquare matrix pencils by minimal perturbation approach
• Finite Elements and Fast Iterative Solvers
• Trace optimization and eigenproblems in dimension reduction methods
• Computational Advertising: Techniques for Targeting Relevant Ads
• Solving the Trust-Region Subproblem By a Generalized Eigenvalue Problem
• Numerical Methods for Large Eigenvalue Problems
• A fast randomized algorithm for overdetermined linear least-squares regression
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• Minimizing Communication in Numerical Linear Algebra
• An Algorithm for the Principal Component Analysis of Large Data Sets
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Low-Rank Approximation and Regression in Input Sparsity Time
• The Lanczos Algorithm With Partial Reorthogonalization
• Algorithm 873
• A Randomized Algorithm for Principal Component Analysis
• Conjugate Gradient-Like Algorithms for Solving Nonsymmetric Linear Systems
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Solution of Sparse Indefinite Systems of Linear Equations
• Spectra of Nearly Hermitian Matrices
• The Condition of Polynomials in Power Form
• From Potential Theory to Matrix Iterations in Six Steps
• Trust Region Methods
• Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Accuracy and Stability of Numerical Algorithms
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• A Jacobi–Davidson Iteration Method for Linear Eigenvalue Problems
• Sharp error bounds for Ritz vectors and approximate singular vectors
• Scalable Semidefinite Programming
• IFISS: A Computational Laboratory for Investigating Incompressible Flow Problems
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
• The Generalized Eigenvalue Problem for Nonsquare Pencils Using a Minimal Perturbation Approach
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• The Condition of Orthogonal Polynomials
• Randomized Gram--Schmidt Process with Application to GMRES
• Randomized numerical linear algebra: Foundations and algorithms
• A generalization of Saad's theorem on Rayleigh-Ritz approximations
• IFISS3D: a computational laboratory for investigating finite element approximation in three dimensions

Related Items (4)

Polynomial preconditioning for the action of the matrix square root and inverse square root ⋮ A robust randomized indicator method for accurate symmetric eigenvalue detection ⋮ The sparse-grid-based adaptive spectral Koopman method ⋮ Krylov subspace recycling with randomized sketching for matrix functions

This page was built for publication: Fast and accurate randomized algorithms for linear systems and eigenvalue problems