Mixing LU and QR factorization algorithms to design high-performance dense linear algebra solvers

Abstract : This paper introduces hybrid LU-QR algorithms for solving dense linear sys-tems of the form Ax = b. Throughout a matrix factorization, these algorithms 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 pos-sible. 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 extension of the PaRSEC software to allow for dynamic choices during execution. Finally, we analyze both stability and perfor-mance results compared to state-of-the-art linear solvers on parallel distributed multicore platforms. $ A shorter version of this paper appeared in the proceedings of IPDPS 2014 [18].
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2015, IPDPS 2014 Selected Papers on Numerical and Combinatorial Algorithms, 85, pp.15. 〈10.1016/j.jpdc.2015.06.007〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01107457
Contributeur : Mathieu Faverge <>
Soumis le : mardi 20 janvier 2015 - 17:04:57
Dernière modification le : vendredi 20 avril 2018 - 15:44:27

Lien texte intégral

Identifiants

Citation

Mathieu Faverge, Julien Herrmann, Julien Langou, Bradley Lowery, Yves Robert, et al.. Mixing LU and QR factorization algorithms to design high-performance dense linear algebra solvers. Journal of Parallel and Distributed Computing, Elsevier, 2015, IPDPS 2014 Selected Papers on Numerical and Combinatorial Algorithms, 85, pp.15. 〈10.1016/j.jpdc.2015.06.007〉. 〈hal-01107457〉

Partager

Métriques

Consultations de la notice

313