GF(2)上大型稀疏线性方程组求解并行算法研究与实现.docx

GF(2)上大型稀疏线性方程组求解并行算法研究与实现
GF(2)上大型稀疏线性方程组求解并行算法研究与实现论文
摘要:
本论文主要研究了GF(2)上大型稀疏线性方程组求解并行算法的研究与实现，提出了一种StructuredGauss-Seidel（SGS）解法，采用MPI并行化，实现了在多核CPU上的高效求解。实践表明，在多核CPU上，该算法不仅具备良好的可扩展性，同时在效率上也优于常规的串行求解算法和其他并行算法。
关键词:GF(2)，稀疏线性方程组，并行算法，StructuredGauss-Seidel，MPI
引言：
在大型科学工程中，稀疏线性方程组的求解是一个广泛存在的问题。然而，由于其规模之大，常规的串行求解方法在效率和时间上都面临很大的挑战。因此，提出并实现高效的并行算法，能够加速线性方程组的求解，提高计算效率和性能。本论文主要研究了GF(2)上大型稀疏线性方程组求解并行算法，提出了一种StructuredGauss-Seidel（SGS）解法，并在MPI并行化的基础上，在多核CPU上实现了高效的线性方程组求解算法。
1GF(2)上稀疏线性方程组求解算法简介
在GF(2)上，线性方程组的求解可以使用高斯消元法、列主元Gauss消元和LU分解等方法，其中高斯消元法是最常见的求解方法。但是，由于其计算复杂度的上界介于$O(n^3)$和$O(n^2logn)$之间，因此在大规模线性方程组求解问题上效率较差。由此，稀疏矩阵的矩阵分解被广泛应用。
在稀疏情况下，线性方程组的解法有很多种，比如共轭梯度法、SOR迭代法、Jacobi迭代法、Gauss-Seidel迭代法等等。其中，StructuredGauss-Seidel（SGS）迭代法是一种基于高斯-赛德尔迭代法（Gauss-Seideliteration）的优化方法。它在每一个迭代步骤中，对系数矩阵进行分块，使得分块后的矩阵具有对角占优或严格对角占优性质，从而提高SGS算法的收敛速度。
2StructuredGauss-Seidel（SGS）算法
SGS算法是一种基于高斯-赛德尔迭代法（Gauss-Seideliteration）的优化方法。在每一个迭代步骤中，SGS算法将系数矩阵分块，使得分块后的矩阵具有对角占优或严格对角占优性质，从而提高SGS算法的收敛速度。其核心算法如下：
1.先将系数矩阵分块为A=[A11A12;A21A22]，其中A11是不在A22的对角线上的子矩阵，且A11是对角占优矩阵。
2.计算每个块的右端项，即$A_{11}x_1(t)+A_{12}x_2(t)=b_1$，$A_{21}x_1(t)+A_{22}x_2(t)=b_2$。
3.通过当前迭代的$x_2(t)$，求出$x_1(t+1)$：$x_1(t+1)=A{11}^{-1}(b_1-A_{12}x_2(t))$。
4.通过当前迭代的$x_1(t+1)$，求出$x_2(t+1)$：$x_2(t+1)=A_{22}^{-1}(b_2-A_{21}x_1(t+1))$。
5.重复以上步骤，直到数据达到临界点为止。
3并行算法设计和实现
为了进一步提高SGS算法的效率和性能，在本文的研究过程中，我们采用MPI并行化实现了该算法。MPI是一种通用且灵活的消息传递接口，它能够在分布式内存系统上实现并行计算，充分利用多核CPU的计算能力和资源，减少线程之间的数据传递和共享，提高计算效率和性能。
在本论文的实现中，我们使用了MPI通信库，基于C++语言实现，并使用了MKL线性代数库（IntelMathKernelLibrary）的线性方程组解法进行求解。算法的具体实现过程如下：
1.MPI环境初始化
在MPI并行计算算法中，首先需要在所有计算节点上初始化MPI通信库，为接下来的数据通信做好准备。MPI_Init()函数用于初始化MPI环境，MPI_Comm_rank()和MPI_Comm_size()用于获取当前进程号和进程总数。
2.数据划分
在本算法的实现过程中，我们采用了MPI的分块策略来实现矩阵的数据划分。将系数矩阵分为n行，m列的数据块，其中n是进程总数，m是矩阵的列数。每个进程负责一个子问题，按照SGS算法进行并行求解。
3.迭代求解
每个进程收到数据块后，按照SGS算法进行迭代求解，最后得到该进程所负责的线性方程的解，即子向量。然后，将各个进程得到的子向量通过MPI_Allgater()函数进行汇总，得到最终的线性方程的解。
4.MPI环境销毁
当所有计算任务结束后，需要调用MPI_Finalize()函数来释放MPI环境，销毁MPI通信库。
4实验结果和分析
为了验证算法的有效性，在本研究中，我们对比了SGS算法和常规的串行求解算法以及其他并行算法的效率和速度，并在一组大型稀疏线性方程组