8 papers
Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms
James Demmel, Hengrui Luo, Ryan Schneider +1
This paper presents several parallel versions of Jacobi's method for the symmetric eigenvalue problem and the SVD. A continuation of [Demmel, Luo, Schneider, & Wang 2025], we devel…
Anatomy of High-Performance Column-Pivoted QR Decomposition
Maksim Melnichenko, Riley Murray, William Killian +4
We introduce an algorithmic framework for performing QR factorization with column pivoting (QRCP) on general matrices. The framework enables the design of practical QRCP algorithms…
Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part One -- Serial Algorithms
James Demmel, Hengrui Luo, Ryan Schneider +1
We analyze several versions of Jacobi's method for the symmetric eigenvalue problem. Our goal is to reduce the asymptotic cost of the algorithm as much as possible, as measured by…
Tackling Parallelization Challenges of Randomized Preconditioners With Dependency Tracking
Tianyu Liang, Chao Chen, Yotam Yaniv +6
Incomplete Cholesky (IC) preconditioners are the standard black-box, memory-efficient first resort for large graph Laplacian systems, but classical IC can break down on irregular g…
Parallelizing the Approximate Minimum Degree Ordering Algorithm: Strategies and Evaluation
Yen-Hsiang Chang, Aydın Buluç, James Demmel
The approximate minimum degree algorithm is widely used before numerical factorization to reduce fill-in for sparse matrices. While considerable attention has been given to the num…
An Efficient Sparse Kernel Generator for O(3)-Equivariant Deep Networks
Vivek Bharadwaj, Austin Glover, Aydin Buluc +1
Rotation equivariant graph neural networks, i.e. networks designed to guarantee certain geometric relations between their inputs and outputs, yield state of the art performance on…
CholeskyQR with Randomization and Pivoting for Tall Matrices (CQRRPT)
Maksim Melnichenko, Oleg Balabanov, Riley Murray +3
This paper develops and analyzes a new algorithm for QR decomposition with column pivoting (QRCP) of rectangular matrices with many more rows than columns. The algorithm carefully…
Fast multiplication of random dense matrices with fixed sparse matrices
Tianyu Liang, Riley Murray, Aydın Buluç +1
This work focuses on accelerating the multiplication of a dense random matrix with a (fixed) sparse matrix, which is frequently used in sketching algorithms. We develop a novel sch…