Abstract
This paper introduces LU_PRRP and its communication-avoiding counterpart, CALU_PRRP, which utilize Strong Rank Revealing QR (RRQR) factorization for pivoting. These algorithms address the long-standing trade-off between numerical stability and computational efficiency in matrix factorization. Unlike standard Gaussian Elimination with Partial Pivoting (GEPP), which can exhibit exponential growth factors in pathological cases, LU_PRRP provides much tighter bounds on element growth. CALU_PRRP further optimizes performance for parallel systems through tournament pivoting, achieving theoretical lower bounds for communication while maintaining superior stability.
Introduction
LU factorization is a fundamental operation in numerical linear algebra, essential for solving linear systems and computing determinants. For decades, Gaussian Elimination with Partial Pivoting (GEPP) has been the standard approach. However, GEPP faces two significant challenges in modern computing: numerical instability in specific "pathological" cases and a performance bottleneck caused by communication overhead on parallel architectures.
GEPP's theoretical worst-case growth factor is $2^{n-1}$, which leads to failure when decomposing matrices such as the Wilkinson or Foster matrices. Simultaneously, the frequent synchronization required by standard pivoting strategies limits performance on supercomputers where data movement costs far exceed computation costs. This paper proposes a solution that is both more stable than GEPP and communication-optimal.
Methods
The authors propose two innovative algorithms designed to resolve the stability-speed paradox:
LU_PRRP (Panel Rank Revealing Pivoting)
LU_PRRP represents a departure from the traditional column-wise pivoting of GEPP. Instead of selecting the largest element in a single column, LU_PRRP considers a "panel"—a block of $b$ columns. By performing a Strong Rank Revealing QR (RRQR) factorization on the transpose of this panel, the algorithm identifies a set of $b$ pivot rows that are well-conditioned, effectively bounding the growth of elements during the elimination process. The theoretical upper bound for the growth factor in LU_PRRP is $(1 + \tau b)^{n/b}$, offering a significantly more stable alternative to GEPP's exponential bound.
CALU_PRRP (Communication Avoiding LU_PRRP)
Designed for parallel systems, CALU_PRRP utilizes "Tournament Pivoting" to minimize data movement costs. The matrix is partitioned into blocks, and each block independently identifies candidate pivot rows using RRQR. These candidates then enter a reduction tree—a tournament where the most stable pivots are selected at each level. This allows the algorithm to determine pivots for an entire block of columns with a single communication step, reaching the theoretical lower bounds for communication complexity while maintaining the stability benefits of RRQR.
Experimental Evaluation
The algorithms were evaluated using a comprehensive suite of test cases, including:
- Random Matrices: To assess average-case performance and stability.
- Pathological Matrices: Specifically the Wilkinson, Foster, and Wright matrices, which are known to cause standard solvers to fail.
- The Matrix Computation Toolbox: A collection of 37 specialized matrices used to stress-test numerical stability across a wide range of conditions.
Key Results
The experimental results demonstrate that stability does not have to be sacrificed for speed:
- Defeating Pathological Cases: LU_PRRP and CALU_PRRP successfully decomposed Wilkinson and Foster matrices with growth factors near 1, whereas GEPP failed with growth factors as high as $10^{18}$.
- Practical Stability: In tests on random matrices, the growth factor for the new methods was typically around $n^{1/2}$ or $n^{3/4}$, performing as well as or better than GEPP in practice.
- Communication Efficiency: CALU_PRRP was shown to be communication-optimal, attaining the theoretical lower bounds for both the volume of data moved and the number of messages sent between processors.
- Backward Error: The normwise and componentwise backward errors remained on the order of machine epsilon ($10^{-16}$ to $10^{-14}$), confirming high numerical precision.
Conclusion
LU_PRRP and CALU_PRRP represent a significant advancement in matrix factorization. By integrating rank-revealing principles into the pivoting strategy, the authors have created algorithms that are more robust than GEPP while being optimized for modern parallel hardware. Future work will focus on fine-tuning parameters like panel size for specific architectures and extending these principles to other types of matrix decompositions.
Summary updated