Threshold Pivoting for Dense LU Factorization
SessionWorkshop on Latest Advances in Scalable Algorithms for Large-Scale Heterogeneous Systems (ScalAH'22)
DescriptionLU factorization is a key approach for solving large, dense systems of linear equations. Partial row pivoting is commonly used to ensure numerical stability; however, the data movement needed for the row interchanges can reduce performance. To improve this, we propose using threshold pivoting to find pivots almost as good as those selected by partial pivoting but that result in less data movement. Our theoretical analysis bounds the element growth similarly to partial pivoting; however, it also shows that the growth of threshold pivoting for a given matrix cannot be bounded by that of partial pivoting and vice versa. Additionally, we experimentally tested the approach on the Summit supercomputer. Threshold pivoting improved performance by up to 32% without a significant effect on accuracy. For a more aggressive configuration with up to one digit of accuracy lost, the improvement was as high as 44%.
Event Type
Workshop
TimeSunday, 13 November 20222:15pm - 2:40pm CST
LocationC146
Recorded
Algorithms
Exascale Computing
Extreme Scale Computing
Heterogeneous Systems
Post-Moore Computing
Quantum Computing
W