Replacing Pivoting in Distributed Gaussian Elimination with Randomized Techniques

TitleReplacing Pivoting in Distributed Gaussian Elimination with Randomized Techniques
Publication TypeConference Paper
Year of Publication2020
AuthorsLindquist, N., P. Luszczek, and J. Dongarra
Conference Name2020 IEEE/ACM 11th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA)
Date Published2020-11
Conference LocationAtlanta, GA
Keywordslinear systems, Randomized algorithms

Gaussian elimination is a key technique for solving dense, non-symmetric systems of linear equations. Pivoting is used to ensure numerical stability but can introduce significant overheads. We propose replacing pivoting with recursive butterfly transforms (RBTs) and iterative refinement. RBTs use an FFT-like structure and randomized elements to provide an efficient, two-sided preconditioner for factoring. This approach was implemented and tested using Software for Linear Algebra Targeting Exascale (SLATE). In numerical experiments, our implementation was more robust than Gaussian elimination with no pivoting (GENP) but failed to solve all the problems solvable with Gaussian elimination with partial pivoting (GEPP). Furthermore, the proposed solver was able to outperform GEPP when distributed on GPU-accelerated nodes.

Project Tags: 
External Publication Flag: