Designing LU-QR Hybrid Solvers for Performance and Stability
- 1 May 2014
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1029-1038
- https://doi.org/10.1109/ipdps.2014.108
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.Keywords
This publication has 11 references indexed in Scilit:
- Hierarchical QR factorization algorithms for multi-core clustersParallel Computing, 2013
- Accelerating Linear System Solutions Using Randomization TechniquesACM Transactions on Mathematical Software, 2013
- Communication-optimal Parallel and Sequential QR and LU FactorizationsSIAM Journal on Scientific Computing, 2012
- DAGuE: A generic distributed DAG engine for High Performance ComputingParallel Computing, 2012
- CALU: A Communication Optimal LU Factorization AlgorithmSIAM Journal on Matrix Analysis and Applications, 2011
- Programming Matrix Algorithms-by-Blocks for Thread-Level ParallelismACM Transactions on Mathematical Software, 2009
- A class of parallel tiled linear algebra algorithms for multicore architecturesParallel Computing, 2008
- The Snap-Back Pivoting Method for Symmetric Banded Indefinite MatricesSIAM Journal on Matrix Analysis and Applications, 2006
- Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite ProblemsSIAM Journal on Matrix Analysis and Applications, 2005
- Accuracy and Stability of Numerical AlgorithmsPublished by Society for Industrial & Applied Mathematics (SIAM) ,2002