Designing LU-QR hybrid solvers for performance and stability

Abstract : This paper introduces hybrid LU-QR al- gorithms for solving dense linear systems of the form Ax = b. Throughout a matrix factorization, these al- gorithms dynamically alternate LU with local pivoting and QR elimination steps, based upon some robustness criterion. LU elimination steps can be very efficiently parallelized, and are twice as cheap in terms of floating- point operations, as QR steps. However, LU steps are not necessarily stable, while QR steps are always stable. The hybrid algorithms execute a QR step when a robustness criterion detects some risk for instability, and they execute an LU step otherwise. Ideally, the choice between LU and QR steps must have a small computational overhead and must provide a satisfactory level of stability with as few QR steps as possible. In this paper, we introduce several robustness criteria and we establish upper bounds on the growth factor of the norm of the updated matrix incurred by each of these criteria. In addition, we describe the implementation of the hybrid algorithms through an exten- sion of the PaRSEC software to allow for dynamic choices during execution. Finally, we analyze both stability and performance results compared to state-of-the-art linear solvers on parallel distributed multicore platforms.
Type de document :
Communication dans un congrès
IEEE International Parallel & Distributed Processing Symposium (IPDPS 2014), May 2014, Phoenix, United States. 2013
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00930238
Contributeur : Mathieu Faverge <>
Soumis le : mardi 14 janvier 2014 - 14:56:52
Dernière modification le : samedi 21 avril 2018 - 01:27:39
Document(s) archivé(s) le : mardi 15 avril 2014 - 16:25:18

Fichier

luqr-arxiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00930238, version 1

Citation

Mathieu Faverge, Julien Herrmann, Julien Langou, Bradley Lowery, Yves Robert, et al.. Designing LU-QR hybrid solvers for performance and stability. IEEE International Parallel & Distributed Processing Symposium (IPDPS 2014), May 2014, Phoenix, United States. 2013. 〈hal-00930238〉

Partager

Métriques

Consultations de la notice

395

Téléchargements de fichiers

172