Numerical Linear Algebra Software in the AI Era: Present and Future

This page accompanies our poster at the Sky Computing Lab End-of-Project meeting at UC Berkeley on October 21, 2026. It holds the poster as a PDF, links to our projects and to an introduction to randomized numerical linear algebra (RandNLA), and the full list of sources behind the poster's numbered markers.

The poster

Project links

Randomized Numerical Linear AlgebraA Perspective on the Field With an Eye to Software

The RandNLA book

Murray et al., 2023

The monograph behind RandBLAS and RandLAPACK [3].

arXivPDF

Video

Is the Future of Linear Algebra.. Random?

An introduction to RandNLA by the Mutual Information channel; from 22:30 it benchmarks our CQRRPT [2].

Watch on YouTubeJump to 22:30

Sources

Numbers match the markers on the poster; highlighted entries are our own work.

1. Our work M. Melnichenko, R. J. Murray, W. Killian, J. Demmel, M. W. Mahoney, P. Luszczek, M. Gates. Anatomy of High-Performance Column-Pivoted QR Decomposition (BQRRP), arXiv:2507.00976, 2025. The poster's chart plots our raw data from the paper's benchmark campaign: a dual AMD EPYC 9734 (Zen4c) at n = 64,000 (best of three runs per block size; the paper reports best of five) and an NVIDIA H100 at n = 32,768 (block sizes 32 to 2048, one run each); in that sweep BQRRP reaches 55 percent of cuSOLVER's unpivoted QR rate on the H100 at block size 2048, still rising; the paper's abstract reports about 65 percent at its own settings.
2. Our work M. Melnichenko, O. Balabanov, R. J. Murray, J. Demmel, M. W. Mahoney, P. Luszczek. CholeskyQR with Randomization and Pivoting for Tall Matrices (CQRRPT), arXiv:2311.08316, 2023. Cited for the CQRRPT row of the methods table.
3. Our work R. Murray et al. Randomized Numerical Linear Algebra: A Perspective on the Field With an Eye to Software, arXiv:2302.11474, 2023. The monograph behind RandBLAS and RandLAPACK.
4. GPU MODE fast-QR competition, 2026: round 2 (leaderboard 774, the poster's table) and round 1 (773). Submissions were run unmodified through the organizers' own checkers on a B200. The speedups on the poster divide the leaderboard time of a plain torch.geqrf entry (130.4 ms, cuSOLVER one matrix at a time) by each top-5 kernel's leaderboard time (1.22 to 1.50 ms).
5. Our work funNyström++: accelerated estimation of spectral sums tr f(A) of large positive semidefinite matrices, implemented in RandLAPACK. The paper is approaching arXiv submission.
6. J. K. Salmon, M. A. Moraes, R. O. Dror, D. E. Shaw. Parallel random numbers: as easy as 1, 2, 3, SC 2011 (the Random123 library). RandBLAS draws every random number from a Random123 counter-based generator, Philox by default with Threefry supported, so a draw is addressable by key and counter and does not depend on the thread count.
7. Our work O. Balabanov, M. Melnichenko, M. W. Mahoney. Stable Matrix-Free Q-less QR via Preconditioning and Randomization, arXiv:2610.16101, October 2026. The Q-less QR implementation on the poster: randomized preconditioning makes a single Cholesky QR pass numerically safe for any numerically full-rank operator, with a componentwise stability analysis that also covers Cholesky QR2 and shifted Cholesky QR3; implemented in RandLAPACK.
8. N. J. Higham. Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002. All 28 chapters are formalized in VSCL within an audited scope.
9. R. J. LeVeque. Finite Volume Methods for Hyperbolic Problems, Cambridge University Press, 2002. Chapters 1 to 3 are formalized.
10. R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge University Press, 2018. Chapters 1 and 2 are formalized; Chapter 3 is in progress.
11. P. Drineas, M. W. Mahoney. RandNLA: Randomized Numerical Linear Algebra, Communications of the ACM 59(6), 2016. The RandNLA case study in VSCL: sampling, matrix concentration, low-rank approximation, least-squares sketching, randomized preconditioning.
12. J. Nocedal, S. J. Wright. Numerical Optimization, 2nd ed., Springer, 2006. Formalization in progress.
13. R. Bhatia. Matrix Analysis, Graduate Texts in Mathematics 169, Springer, 1997. Formalization in progress (started October 2026).
14. A. Greenbaum. Iterative Methods for Solving Linear Systems, SIAM, 1997. Next in the queue.
15. Y. Saad. Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003. Next in the queue.
16. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004. Next in the queue.
17. The mathlib Community. The Lean mathematical library, CPP 2020; the library today is mathlib4. Counts use one theorem/lemma-line regex at commit 021ce68 (2026-10-07). Under a strict rule (finite-precision and approximation results only) Mathlib has 13 lines on numerical analysis, a floating-point model and the trapezoidal rule, and none on numerical linear algebra. Under the broad rule of the printed poster's comparison, which also counts exact-arithmetic matrix algorithms, it has 104 lines on numerical linear algebra (Gram-Schmidt, LDL, row echelon form, Hessenberg matrices and reduction by transvections) and 117 on numerical analysis; none concern rounding error, stability or conditioning. VSCL builds on Mathlib; the poster's VSCL theorem counts use the same regex and rules on VSCL's main branch at commit e821e55 (2026-10-09).
18. N. Halko, P. G. Martinsson, J. A. Tropp. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Review 53(2), 2011. The randomized SVD, the QB factorization and randomized range finders.
19. Y. Chen, E. N. Epperly, J. A. Tropp, R. J. Webber. Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations, Communications on Pure and Applied Mathematics 78(5), 2025; arXiv:2207.06503. RPCholesky; the poster's 1700x tile is from our June 2025 RandLAPACK report: RPCholesky in RandLAPACK against scikit-learn's kernel PCA [25] on the codrna dataset at 100,000 points on an Apple M2 Max (RBF kernel, bandwidth 3, eigenvector identities verified to 1e-8; RandLAPACK with p = 4 against scikit-learn with p = 2, as in the source slide).
20. P. G. Martinsson, G. Quintana-Ortí, N. Heavner, R. van de Geijn. Householder QR factorization with randomization for column pivoting (HQRRP), SIAM Journal on Scientific Computing 39(2), 2017.
21. T. Fukaya, R. Kannan, Y. Nakatsukasa, Y. Yamamoto, Y. Yanagisawa. Shifted Cholesky QR for computing the QR factorization of ill-conditioned matrices, SIAM Journal on Scientific Computing 42(1), 2020. Shifted CholeskyQR3 (sCholQR3).
22. M. Díaz, E. N. Epperly, Z. Frangella, J. A. Tropp, R. J. Webber. Robust, randomized preconditioning for kernel ridge regression, arXiv:2304.12465, 2023. KRILL.
23. H. Avron, P. Maymounkov, S. Toledo. Blendenpik: supercharging LAPACK's least-squares solver, SIAM Journal on Scientific Computing 32(3), 2010.
24. C. C. Paige, M. A. Saunders. LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Transactions on Mathematical Software 8(1), 1982.
25. F. Pedregosa et al. Scikit-learn: machine learning in Python, Journal of Machine Learning Research 12, 2011. The kernel PCA baseline of the 1700x tile.
26. L. de Moura, S. Ullrich. The Lean 4 theorem prover and programming language, Automated Deduction, CADE 28, Lecture Notes in Computer Science, Springer, 2021, pp. 625-635.
27. M. Gates, P. Luszczek, A. Abdelfattah, J. Kurzak, J. Dongarra, K. Arturov, C. Cecka, C. Freitag. C++ API for BLAS and LAPACK, SLATE Working Note 2, Innovative Computing Laboratory, University of Tennessee; the libraries: BLAS++ and LAPACK++.
28. Z. Frangella, J. A. Tropp, M. Udell. Randomized Nyström preconditioning, SIAM Journal on Matrix Analysis and Applications 44(2), 2023; arXiv:2110.02820. RandLAPACK's REVD2 follows its Algorithm E.2 (adaptive randomized Nyström approximation), with the error estimate of Algorithm E.1.
29. X. Zhang, Q. Wang, Y. Zhang. Model-driven level 3 BLAS performance optimization on Loongson 3A processor, ICPADS 2012; the library: OpenBLAS.
30. Intel. Intel oneAPI Math Kernel Library (oneMKL), developer reference.
31. Apple. Accelerate framework, developer documentation (BLAS and LAPACK interfaces).
32. AMD. AMD Optimizing CPU Libraries (AOCL), user guide; AOCL-BLAS is built on BLIS and AOCL-LAPACK on libflame.
33. J. A. Tropp, R. J. Webber. Randomized algorithms for low-rank matrix approximation: design, analysis, and applications, arXiv:2306.12418, 2023. The randomized SVD and randomized block Krylov iteration (RBKI).
34. T. Chen. The Lanczos algorithm for matrix functions: a handbook for scientists, arXiv:2410.11090, 2024. Lanczos-FA and Lanczos-QF; block Lanczos-FA in funNyström++.

Behind the AI tasks column

Examples of AI systems that rely on each method family's computation; none of them runs RandLAPACK's own code.

• LLM compression (low-rank approximation): PiSSA, GaLore 2; both run randomized SVD in practice.
• Kernel PCA, clustering (symmetric eigen, PSD): scikit-learn's randomized kernel PCA [25].
• Structured pruning (QR with pivoting): pruning by interpolative decomposition, Chee et al.
• Distributed optimizers (tall and Q-less QR): Dion, whose reference implementation defaults to a randomized Cholesky QR.
• Kernel ridge regression (least squares, regression): KRILL [22].
• GP likelihoods, Hessians (matrix functions, traces): stochastic Lanczos quadrature in GPyTorch; Hessian spectra of neural networks in PyHessian.

Related: the companion page for our Math & AI Summer in Seattle poster.

Presented by Maksim Melnichenko. PIs: Michael W. Mahoney, Riley Murray and Kimon Fountoulakis. The work spans UC Berkeley, the International Computer Science Institute, Sandia National Laboratories, the University of Tennessee, Knoxville, and the University of Waterloo. Page maintained by Maksim Melnichenko.