6 papers
Attention Mechanisms Through the Lens of Numerical Methods: Approximation Methods and Alternative Formulations
Michel Fabrice Serret, Alice Cortinovis, Yijun Dong +10
The attention mechanism is the computational core of modern Transformer architectures, but its quadratic complexity in the input sequence length is the bottleneck for large-scale i…
Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
Noah Amsel, Yves Baumann, Paul Beckman +36
This document presents a series of open questions arising in matrix computations, i.e., the numerical solution of linear algebra problems. It is a result of working groups at the w…
Efficient error estimators for Generalized Nyström
Lorenzo Lazzarino, Katherine J. Pearce, Nathaniel Pritchard
Randomized algorithms in numerical linear algebra have proven to be effective in ameliorating issues of scalability when working with large matrices, efficiently producing accurate…
Randomized Algorithms for Low-Rank Matrix and Tensor Decompositions
Katherine J. Pearce, Per-Gunnar Martinsson
This paper surveys randomized algorithms in numerical linear algebra for low-rank decompositions of matrices and tensors. The survey begins with a review of classical matrix algori…
Randomized Block Low-Rank Matrix Compression by Tagging
Katherine J. Pearce, Anna Yesypenko, James Levitt +1
In this work, we present randomized compression algorithms for flat rank-structured matrices with shared bases, termed uniform Block Low-Rank (BLR) matrices. Our main contribution…
Robust Blockwise Random Pivoting: Fast and Accurate Adaptive Interpolative Decomposition
Yijun Dong, Chao Chen, Per-Gunnar Martinsson +1
The interpolative decomposition (ID) aims to construct a low-rank approximation formed by a basis consisting of row/column skeletons in the original matrix and a corresponding inte…