# Bidiagonalization with Parallel Tiled Algorithms

1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We consider algorithms for going from a full'' matrix to a condensed band bidiagonal'' form using orthogonal transformations. We use the framework of algorithms by tiles''. Within this framework, we study: (i) the tiled bidiagonalization algorithm \bidiag, which is a tiled version of the standard scalar bidiagonalization algorithm; and (ii) the R-bidiagonalization algorithm \rbidiag, which is a tiled version of the algorithm which consists in first performing the QR factorization of the initial matrix, then performing the band-bidiagonalization of the R-factor. For both bidiagonalization algorithms \bidiag and \rbidiag, we use four main types of reduction trees, namely \FlatTS, \FlatTT, \Greedy, and a newly introduced auto-adaptive tree, \Auto. We provide a study of critical path lengths for these tiled algorithms, which shows that (i) \rbidiag has a shorter critical path length than \bidiag for tall and skinny matrices, and (ii) \Greedy based schemes are much better than earlier proposed variants with unbounded resources. We provide experiments on a single multicore node, and on a few multicore nodes of a parallel distributed shared-memory system, to show the superiority of the new algorithms on a variety of matrix sizes, matrix shapes and core counts.
Type de document :
Rapport
[Research Report] RR-8969, INRIA. 2016
Domaine :

Littérature citée [40 références]

https://hal.inria.fr/hal-01389232
Contributeur : Equipe Roma <>
Soumis le : vendredi 18 novembre 2016 - 15:39:06
Dernière modification le : samedi 21 avril 2018 - 01:27:36

### Fichier

bidiag_RRv2.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01389232, version 2

### Citation

Mathieu Faverge, Julien Langou, Yves Robert, Jack Dongarra. Bidiagonalization with Parallel Tiled Algorithms . [Research Report] RR-8969, INRIA. 2016. 〈hal-01389232v2〉

### Métriques

Consultations de la notice

## 349

Téléchargements de fichiers