Replacing Pivoting in Distributed Gaussian Elimination with Randomized Techniques
Event Type
Workshop
Algorithms
Extreme Scale Computing
Performance/Productivity Measurement and Evaluation
Scalable Computing
Scientific Computing
W
TimeThursday, 12 November 20203:20pm - 3:45pm EDT
LocationTrack 8
DescriptionGaussian 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), although 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 heterogeneous nodes.
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), although 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 heterogeneous nodes.
