SC20 Is Everywhere We Are

SC20 Virtual Platform
Replacing Pivoting in Distributed Gaussian Elimination with Randomized Techniques
Event Type
Workshop
Tags
Algorithms
Extreme Scale Computing
Performance/Productivity Measurement and Evaluation
Scalable Computing
Scientific Computing
Registration Categories
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.
Back To Top Button