12 papers
Randomized Block Davidson Eigensolvers for Plane-Wave Density-Functional Theory
Moritz Gubler, Taejun Park, Augustin Bussy +4
Iterative diagonalization is the dominant cost of plane-wave density-functional theory (DFT), with search-space orthogonalization scaling particularly quickly with problem size and…
Accelerating the Canonical Polyadic Alternating Least Squares Optimization via a Randomized Interpolative Decomposition
Israa Fakih, Laura Grigori, Karl Pierce
We present a novel leverage score-based sampling strategy for the randomized alternating least squares optimization (ALS) of the canonical polyadic decomposition (CPD-ALS). Unlike…
Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices
Hussam Al Daas, Grey Ballard, Laura Grigori +4
Sketching is widely used in randomized linear algebra for low-rank matrix approximation, column subset selection, and many other problems, and it has gained significant traction in…
Sketch low-rank dynamics: orthogonal vs. oblique projections
Benjamin Carrel, Laura Grigori
We study how sketching techniques from randomized numerical linear algebra can be incorporated into the dynamical low-rank approximation (DLRA) of large-scale matrix differential e…
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…
Restoring similarity in randomized Krylov methods with applications to eigenvalue problems and matrix functions
Laura Grigori, Daniel Kressner, Nian Shao +1
The randomized Arnoldi process has been used in large-scale scientific computing because it produces a well-conditioned basis for the Krylov subspace more quickly than the standard…