米瑞琪 于 朋

（中国石油大学〈华东〉，山东 青岛266580）

Gauss-Seidel迭代法求解线性方程组的并行化研究

米瑞琪 于 朋

（中国石油大学〈华东〉，山东 青岛266580）

Gauss-Seidel迭代法在工程计算中具有广泛应用。高维矩阵对线性方程组的求解效率提出了新的要求。本文提出了两种模式下的Gauss-Seidel并行计算方法，并对比了在不同矩阵维数下的加速效率，得到了具有较高加速比的并行迭代方法。

Gauss-Seidel；迭代法；并行；MPI;矩阵运算

1 问题背景与提出

在实际工程应用中经常需要用到求解维数较高的线性代数方程组，对于线性代数方程组的求解方法可以分成两类：直接法和迭代法，其中直接法得到的是方程组的真解，其求解过程为通过有限步四则运算，常用的实现方式是Gauss消去方法和矩阵的三角分解方法，这种计算方式在求解过程中会产生大量的非零元素，存储量和计算量均比较大，因此常用于求解低阶、稠密线性方程组。对于高维线性方程组，可以采用并行运算的方式进一步提高计算效率，Gauss-Seidel迭代法具有收敛速度快、计算稳定性好等优点，是求解高维线性方程组的常用方法，因此本文将对Gauss-Seidel迭代法的并行化进行研究，期望获取较高的运行效率和加速比。

2 Gauss-Seidel迭代法的并行算法描述

任务分配模式一：连续等分矩阵法

在《并行算法的设计与分析》一书中给出了一种矩阵分配的算法，设矩阵的阶为N，采用m个线程进行计算，则将矩阵等分成m块，每一块分到的任务量为N/m,每一个线程计算完自己的分量之后立刻向其他的线程进行广播。……