Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Communication avoiding low rank approximation based on QR with tournament pivoting

Matthias Beaupère 1 Laura Grigori 1
1 ALPINES - Algorithms and parallel tools for integrated numerical simulations
INSMI - Institut National des Sciences Mathématiques et de leurs Interactions, Inria de Paris, LJLL (UMR_7598) - Laboratoire Jacques-Louis Lions
Abstract : We introduce a parallel algorithm for computing the low rank approximation $A_k$ of a large matrix $A$ which minimizes the number of messages exchanged between processors (modulo polylogarithmic factors) and has guarantees for the approximations of the singular values of $A$ provided by $A_k$. This operation is essential in many applications in scientific computing and data analysis when dealing with large data sets. Our algorithm is based on QR factorization that consists in selecting a subset of columns from the matrix $A$ that allow to approximate the range of $A$, and then projecting the columns of $A$ on a basis of the subspace spanned by those columns. The selection of columns is performed by using tournament pivoting, a strategy introduced previously for matrices partitioned into blocks of columns. This strategy is extended here to matrices partitioned along both dimensions that are distributed on a two-dimensional grid of processors, and also to tournaments with more general reduction trees. Performance results show that the algorithm scales well on up to $1024$ cores of $16$ nodes.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-02947991
Contributor : Matthias Beaupère <>
Submitted on : Thursday, September 24, 2020 - 1:15:37 PM
Last modification on : Saturday, September 26, 2020 - 3:33:11 AM

File

qr_with_tournament_pivoting.pd...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02947991, version 1

Citation

Matthias Beaupère, Laura Grigori. Communication avoiding low rank approximation based on QR with tournament pivoting. 2020. ⟨hal-02947991⟩

Share

Metrics

Record views

115

Files downloads

157