109 citations · 261 across the 29 of their papers we have counts for
34 papers
Randomized Jacobi-Davidson method
Laura Grigori, Taejun Park, Igor Simunec
The Jacobi-Davidson method is a widely used subspace method for computing a few eigenpairs of a large, sparse, non-Hermitian matrix closest to a target. Like other subspace methods…
Adaptive Randomized Tensor Train Rounding using Khatri-Rao Products
Hussam Al Daas, Grey Ballard, Laura Grigori +3
Approximating a tensor in the tensor train (TT) format has many important applications in scientific computing. Rounding a TT tensor involves further compressing a tensor that is a…
Minimizing Communication for Parallel Symmetric Tensor Times Same Vector Computation
Hussam Al Daas, Grey Ballard, Laura Grigori +3
In this article, we focus on the parallel communication cost of multiplying the same vector along two modes of a -dimensional symmetric tensor. This is a key computation in the…
An additive two-level parallel variant of the DMRG algorithm with coarse-space correction
Laura Grigori, Muhammad Hassan
The density matrix renormalization group (DMRG) algorithm is a popular alternating minimization scheme for solving high-dimensional optimization problems in the tensor train format…
Communication Lower Bounds and Optimal Algorithms for Symmetric Matrix Computations
Hussam Al Daas, Grey Ballard, Laura Grigori +3
In this article, we focus on the communication costs of three symmetric matrix computations: i) multiplying a matrix with its transpose, known as a symmetric rank-k update (SYRK) i…
Randomized Householder QR
Laura Grigori, Edouard Timsit
This paper introduces a randomized Householder QR factorization (RHQR). This factorization can be used to obtain a well conditioned basis of a vector space and thus can be employed…
Randomized Orthogonal Projection Methods for Krylov Subspace Solvers
Edouard Timsit, Laura Grigori, Oleg Balabanov
Randomized orthogonal projection methods (ROPMs) can be used to speed up the computation of Krylov subspace methods in various contexts. Through a theoretical and numerical investi…
Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software
Riley Murray, James Demmel, Michael W. Mahoney +10
Randomized numerical linear algebra - RandNLA, for short - concerns the use of randomization as a resource to develop improved algorithms for large-scale linear algebra computation…
Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor Decomposition
Vivek Bharadwaj, Osman Asif Malik, Riley Murray +3
We present a data structure to randomly sample rows from the Khatri-Rao product of several matrices according to the exact distribution of its leverage scores. Our proposed sampler…
Block subsampled randomized Hadamard transform for low-rank approximation on distributed architectures
Oleg Balabanov, Matthias Beaupere, Laura Grigori +1
This article introduces a novel structured random matrix composed blockwise from subsampled randomized Hadamard transforms (SRHTs). The block SRHT is expected to outperform well-kn…
Communication Lower Bounds and Optimal Algorithms for Multiple Tensor-Times-Matrix Computation
Hussam Al Daas, Grey Ballard, Laura Grigori +2
Multiple Tensor-Times-Matrix (Multi-TTM) is a key computation in algorithms for computing and operating with the Tucker tensor decomposition, which is frequently used in multidimen…
Tight Memory-Independent Parallel Matrix Multiplication Communication Lower Bounds
Hussam Al Daas, Grey Ballard, Laura Grigori +2
Communication lower bounds have long been established for matrix multiplication algorithms. However, most methods of asymptotic analysis have either ignored the constant factors or…
A Directional Equispaced interpolation-based Fast Multipole Method for oscillatory kernels
Igor Chollet, Xavier Claeys, Pierre Fortin +1
Fast Multipole Methods (FMMs) based on the oscillatory Helmholtz kernel can reduce the cost of solving N-body problems arising from Boundary Integral Equations (BIEs) in acoustic o…
MAPPRAISER: A massively parallel map-making framework for multi-kilo pixel CMB experiments
Hamza El Bouhargani, Aygul Jamal, Dominic Beck +3
Forthcoming cosmic microwave background (CMB) polarized anisotropy experiments have the potential to revolutionize our understanding of the Universe and fundamental physics. The so…
Randomized block Gram-Schmidt process for solution of linear systems and eigenvalue problems
Oleg Balabanov, Laura Grigori
This article introduces randomized block Gram-Schmidt process (RBGS) for QR decomposition. RBGS extends the single-vector randomized Gram-Schmidt (RGS) algorithm and inherits its k…
Randomized Gram-Schmidt process with application to GMRES
Oleg Balabanov, Laura Grigori
A randomized Gram-Schmidt algorithm is developed for orthonormalization of high-dimensional vectors or QR factorization. The proposed process can be less computationally expensive…
Accelerating linear system solvers for time domain component separation of cosmic microwave background data
J. Papež, L. Grigori, R. Stompor
Component separation is one of the key stages of any modern, cosmic microwave background (CMB) data analysis pipeline. It is an inherently non-linear procedure and typically involv…
An improved analysis and unified perspective on deterministic and randomized low rank matrix approximations
James Demmel, Laura Grigori, Alexander Rusciano
We introduce a Generalized LU-Factorization (\textbf{GLU}) for low-rank matrix approximation. We relate this to past approaches and extensively analyze its approximation properties…
Parallel and Communication Avoiding Least Angle Regression
S. Das, J. Demmel, K. Fountoulakis +3
We are interested in parallelizing the Least Angle Regression (LARS) algorithm for fitting linear regression models to high-dimensional data. We consider two parallel and communica…
A 3D Parallel Algorithm for QR Decomposition
Grey Ballard, James Demmel, Laura Grigori +2
Interprocessor communication often dominates the runtime of large matrix computations. We present a parallel algorithm for computing QR decompositions whose bandwidth cost (communi…
Solving linear equations with messenger-field and conjugate gradients techniques - an application to CMB data analysis
J. Papez, L. Grigori, R. Stompor
We discuss linear system solvers invoking a messenger-field and compare them with (preconditioned) conjugate gradients approaches. We show that the messenger-field techniques corre…
URV Factorization with Random Orthogonal System Mixing
Stephen Becker, James Folberth, Laura Grigori
The unpivoted and pivoted Householder QR factorizations are ubiquitous in numerical linear algebra. A difficulty with pivoted Householder QR is the communication bottleneck introdu…
Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
Ariful Azad, Grey Ballard, Aydin Buluc +5
Sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high-performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. The s…
Accelerating Cosmic Microwave Background map-making procedure through preconditioning
Mikolaj Szydlarski, Laura Grigori, Radek Stompor
Estimation of the sky signal from sequences of time ordered data is one of the key steps in Cosmic Microwave Background (CMB) data analysis, commonly referred to as the map-making…