Designing LU-QR hybrid solvers for performance and stability

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 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 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 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.

Original languageEnglish
Title of host publicationProceedings - IEEE 28th International Parallel and Distributed Processing Symposium, IPDPS 2014
PublisherIEEE Computer Society
Pages1029-1038
Number of pages10
ISBN (Print)9780769552071
DOIs
StatePublished - 2014
Externally publishedYes
Event28th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2014 - Phoenix, AZ, United States
Duration: May 19 2014May 23 2014

Publication series

NameProceedings of the International Parallel and Distributed Processing Symposium, IPDPS
ISSN (Print)1530-2075
ISSN (Electronic)2332-1237

Conference

Conference28th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2014
Country/TerritoryUnited States
CityPhoenix, AZ
Period05/19/1405/23/14

Funding

Keywords

  • LU factorization
  • QR factorization
  • algorithm
  • hybrid
  • linear algebra
  • linear solvers
  • linear systems
  • runtime

Fingerprint

Dive into the research topics of 'Designing LU-QR hybrid solvers for performance and stability'. Together they form a unique fingerprint.

Cite this