6 papers
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…
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…
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…
Parallel GPU-Accelerated Randomized Construction of Approximate Cholesky Preconditioners
Tianyu Liang, Chao Chen, Yotam Yaniv +5
We introduce a parallel algorithm to construct a preconditioner for solving a large, sparse linear system where the coefficient matrix is a Laplacian matrix (a.k.a., graph Laplacia…
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…