求解大型稀疏矩阵方程组的SPIKE算法

摘要

不同于传统的LU分解算法和QR分解算法，本文研究了一种新的基于DS矩阵分解的递归SPIKE算法。SPIKE算法采用了一种新颖的分解方法来平衡通信和算法开销，相比其他方法在现代并行架构上有更好的延展性。首先，从系数矩阵的分块、DS分解、简化系数矩阵方程组的提取和求解四方面介绍了递归SPIKE算法的工作原理。然后，首次将其应用到具体的系数矩阵规模不同的线性方程组中，并与LU分解算法与QR分解算法进行了比较。三组数值实验分别给出了各个求解算法的结果和运行时间。实验结果表明，递归SPIKE算法不仅能够求解得到准确结果，而且求解速度更快。数值案例表明，递归SPIKE算法所需的计算时间约为LU算法的40%，约为QR分解算法的8%。

关键词

一般带状矩阵 / 三对角矩阵 / DS矩阵分解 / 递归SPIKE算法