Bidiagonalization and R-Bidiagonalization: Parallel Tiled Algorithms, Critical Paths and Distributed-Memory Implementation

Abstract : We study tiled algorithms for going from a " full " matrix to a condensed " band bidiagonal " form using orthogonal transformations: (i) the tiled bidiagonalization algorithm BIDIAG, which is a tiled version of the standard scalar bidiagonalization algorithm; and (ii) the R-bidiagonalization algorithm R-BIDIAG, 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 BIDIAG and R-BIDIAG, 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) R-BIDIAG has a shorter critical path length than BIDIAG for tall and skinny matrices, and (ii) GREEDY based schemes are much better than earlier proposed algorithms 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 :
Communication dans un congrès
IPDPS'17 - 31st IEEE International Parallel and Distributed Processing Symposium , May 2017, Orlando, United States. 2017, 〈http://ipdps.org/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01484113
Contributeur : Mathieu Faverge <>
Soumis le : lundi 6 mars 2017 - 18:24:24
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : mercredi 7 juin 2017 - 16:06:35

Fichier

ipdps-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01484113, version 1

Citation

Mathieu Faverge, Julien Langou, Yves Robert, Jack Dongarra. Bidiagonalization and R-Bidiagonalization: Parallel Tiled Algorithms, Critical Paths and Distributed-Memory Implementation. IPDPS'17 - 31st IEEE International Parallel and Distributed Processing Symposium , May 2017, Orlando, United States. 2017, 〈http://ipdps.org/〉. 〈hal-01484113〉

Partager

Métriques

Consultations de la notice

523

Téléchargements de fichiers

123