Threshold Pivoting for Dense LU Factorization

TitleThreshold Pivoting for Dense LU Factorization
Publication TypeConference Paper
Year of Publication2022
AuthorsLindquist, N., M. Gates, P. Luszczek, and J. Dongarra
Conference NameScalAH22: 13th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Heterogeneous Systems
Date Published2022-11
Conference LocationDallas, Texas

LU 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%.

Project Tags: 
External Publication Flag: