Randomized algorithms in numerical linear algebra for scientific computing
Abstract
Randomized numerical linear algebra (RNLA) has fundamentally changed the landscape of scientific computing over the last twenty to thirty years. While early breakthroughs focused primarily on low-rank approximation and least-squares problems, randomized techniques are now used to solve a broad range of linear algebra problems, supporting applications spanning data science, optimization, and computational engineering. This paper surveys some of the main ideas of RNLA, focusing on methods that are effective in practice and on simple theoretical bounds that can be used to understand them. We highlight the core benefits of randomization: improved scalability, algorithmic simplicity, and---contrary to what the name may suggest---remarkable reliability and numerical stability. Topics include sketching, low-rank approximation, least squares, orthogonalization and approximate orthogonalization, randomized Krylov subspace methods, preconditioning, trace and spectral density estimation, row and column selection algorithms, posterior error estimation, randomized regularization, and tensor-structured randomness.
Related
- Improved algorithms for computing the matrix logarithm based on the double-exponential formula
- Volume of quasi-homogeneous sublevel sets: Two linear algebra deterministic algorithms with convergence rates
- Mixed-Precision Computing for Scientific Discovery: Formats, Co-Design, and Responsible Approximation
- Orthograph related to mutual (strong) numerical radius orthogonality on operator algebra
- Support in the domain of numerical algorithms in the education of future secondary school mathematics teachers
BibTeX
@misc{epperly2026randomized,
title = {{Randomized algorithms in numerical linear algebra for scientific computing}},
author = {Ethan N. W. Epperly and Daniel Kressner and Yuji Nakatsukasa},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38157},
eprint = {2610.38157},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38157},
}
RIS
TY - UNPB
TI - Randomized algorithms in numerical linear algebra for scientific computing
AU - Ethan N. W. Epperly
AU - Daniel Kressner
AU - Yuji Nakatsukasa
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38157
UR - https://arxiv.org/abs/2610.38157
AB - Randomized numerical linear algebra (RNLA) has fundamentally changed the landscape of scientific computing over the last twenty to thirty years. While early breakthroughs focused primarily on low-rank approximation and least-squares problems, randomized techniques are now used to solve a broad range of linear algebra problems, supporting applications spanning data science, optimization, and computational engineering. This paper surveys some of the main ideas of RNLA, focusing on methods that are effective in practice and on simple theoretical bounds that can be used to understand them. We highlight the core benefits of randomization: improved scalability, algorithmic simplicity, and---contrary to what the name may suggest---remarkable reliability and numerical stability. Topics include sketching, low-rank approximation, least squares, orthogonalization and approximate orthogonalization, randomized Krylov subspace methods, preconditioning, trace and spectral density estimation, row and column selection algorithms, posterior error estimation, randomized regularization, and tensor-structured randomness.
ER -