5 papers · 1 filter
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…