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

Mathieu Faverge, Julien Herrmann, Julien Langou, Bradley Lowery, Yves Robert, Jack Dongarra

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

This paper introduces hybrid LU-QR algorithms for solving dense linear systems 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. 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 extension 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. A comprehensive set of experiments shows that hybrid LU-QR algorithms provide a continuous range of trade-offs between stability and performances.

Original languageEnglish
Pages (from-to)32-46
Number of pages15
JournalJournal of Parallel and Distributed Computing
Volume85
DOIs
StatePublished - Nov 1 2015
Externally publishedYes

Funding

The work of Jack Dongarra was funded in part by the Russian Scientific Fund , Agreement N14-11-00190 . The work of Julien Langou and Bradley R. Lowery was fully funded by the National Science Foundation grant # NSF CCF 1054864 . The work of Yves Robert was funded in part by the French ANR Rescue project and by the Department of Energy # DOE DE-SC0010682 . This work is made in the context of the Inria associate team MORSE. Yves Robert is with Institut Universitaire de France. The authors thank Thomas Herault for his help with PaRSEC, and Jean-Yves L’Excellent for discussions on stability estimators within the MUMPS software. We would like to thank the reviewers for their comments and suggestions, which greatly helped improve the final version of the paper.

Keywords

  • LU factorization
  • Numerical algorithms
  • Performance
  • QR factorization
  • Stability

Fingerprint

Dive into the research topics of 'Mixing LU and QR factorization algorithms to design high-performance dense linear algebra solvers'. Together they form a unique fingerprint.

Cite this