Communication avoiding low rank approximation based on QR with tournament pivoting - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

## Communication avoiding low rank approximation based on QR with tournament pivoting

(1) , (1)
1
Matthias Beaupère
Laura Grigori

#### 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.

### Dates and versions

hal-02947991 , version 1 (24-09-2020)
hal-02947991 , version 2 (18-01-2021)

### Identifiers

• HAL Id : hal-02947991 , version 2

### Cite

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

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

436 View