Fast and accurate randomized algorithms for linear systems and eigenvalue problems

DOI10.1137/23M1565413zbMATH Open1545.65142MaRDI QIDQ6561643FDOQ6561643

Authors: Yuji Nakatsukasa, Joel A. Tropp 

Publication date: 25 June 2024

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

zbMATH Keywords

randomized algorithmsketchingeigenvalue problemlinear systemprojection methodPetrov-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

• Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method
• Title not available (Why is that?)
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Trace optimization and eigenproblems in dimension reduction methods.
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Low-Rank Approximation and Regression in Input Sparsity Time
• Faster least squares approximation
• Matrix algorithms. Vol. 2: Eigensystems
• Numerical methods for large eigenvalue problems
• Title not available (Why is that?)
• Trust Region Methods
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• A Jacobi–Davidson Iteration Method for Linear Eigenvalue Problems
• A generalization of Saad's theorem on Rayleigh-Ritz approximations
• Title not available (Why is that?)
• Accuracy and Stability of Numerical Algorithms
• The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
• Solution of Sparse Indefinite Systems of Linear Equations
• IFISS: A Computational Laboratory for Investigating Incompressible Flow Problems
• Condition numbers and equilibration of matrices
• Improved analysis of the subsampled randomized Hadamard transform
• Minimizing communication in numerical linear algebra
• From Potential Theory to Matrix Iterations in Six Steps
• Finite elements and fast iterative solvers. With applications in incompressible fluid dynamics
• An algorithm for the principal component analysis of large data sets
• A Krylov--Schur algorithm for large eigenproblems
• The Lanczos Algorithm With Partial Reorthogonalization
• A randomized algorithm for principal component analysis
• The Condition of Polynomials in Power Form
• Krylov subspace methods. Principles and analysis.
• Analysis of the symmetric Lanczos algorithm with reorthogonalization methods
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Spectra of Nearly Hermitian Matrices
• The Generalized Eigenvalue Problem for Nonsquare Pencils Using a Minimal Perturbation Approach
• The Tchebychev iteration for nonsymmetric linear systems
• A fast randomized algorithm for overdetermined linear least-squares regression
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• Randomized numerical linear algebra: Foundations and algorithms
• A fast randomized algorithm for the approximation of matrices
• Algorithm 873
• On the generation of Krylov subspace bases
• The Condition of Orthogonal Polynomials
• Randomized block Krylov methods for approximating extreme eigenvalues
• Conjugate Gradient-Like Algorithms for Solving Nonsymmetric Linear Systems
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Solving the Trust-Region Subproblem By a Generalized Eigenvalue Problem
• Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
• Sketching as a tool for numerical linear algebra
• An algorithm for the generalized eigenvalue problem for nonsquare matrix pencils by minimal perturbation approach
• Randomized linear algebra for model reduction. II: Minimal residual methods and dictionary-based approximation
• Randomized linear algebra for model reduction. I. Galerkin methods and error estimation
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Randomized Gram--Schmidt Process with Application to GMRES
• Sharp error bounds for Ritz vectors and approximate singular vectors
• Scalable Semidefinite Programming
• Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities
• IFISS3D: a computational laboratory for investigating finite element approximation in three dimensions

Cited In (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

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