Replacing Pivoting in Distributed Gaussian Elimination with Randomized Techniques
Replacing Pivoting in Distributed Gaussian Elimination with Randomized Techniques
复制标题
DOI：
10.1109/scala51936.2020.00010
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Neil Lindquist;P. Luszczek;J. Dongarra
中科院分区：
文献类型：
--
作者：
Neil Lindquist;P. Luszczek;J. Dongarra
高斯消元法是求解稠密非对称线性方程组的关键技术。旋转是用来确保数值稳定性，但可以引入显着的开销。我们建议用递归蝶形变换（RBT）和迭代细化来代替旋转。RBT使用类似FFT的结构和随机化元素来为因子分解提供有效的双侧预条件子。该方法使用线性代数目标Exascale软件（SLATE）实现和测试。在数值实验中，我们的实现是更强大的高斯消元没有旋转（GENP），但未能解决所有的问题与高斯消元部分旋转（GEPP）可解。此外，建议的求解器能够优于GEPP时，分布在GPU加速的节点。
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.