基于高斯消去法解线性方程组（MPI） 基于高斯消去法解线性方程组（MPI） 一、基本原理 高斯消去法把 Ax=b 归约为上三角方程组 Tx=c，这样利用回带算法求解 x。第 i 次迭代 时，选取 i 列的最大元素作为主元，主元所在的行称为枢轴行（枢轴行的行数会被标记）， 枢轴行与第 i 行进行交换，算法利用枢轴行和第 i+1 到 n-1 行各行的倍数将第 i 列上所有 的非零元归约成零。最终将 nxn 的稠密矩阵化成上三角形，再用回带的方法算出每一个元 素的值。 二、并行分析 （1） 找到枢轴行之后，对所有未被标记的行的修改可以同时进行； （2） 一旦枢轴行与第 i 行的倍数确定，从第 i 行的第 i+1 元素到第 n-1 元素可以同时进 行。 三、代码实现 #include "stdio.h" #include "mpi.h" #include "malloc.h" #define n 4 #define BLOCK_LOW(id,p,n) ((id) * (n)/(p)) #define BLOCK_HIGH(id,p,n) (BLOCK_LOW((id)+1,p,n)-1) #define BLOCK_SIZE(id,p,n) (BLOCK_LOW((id)+1,p,n)-BLOCK_LOW((id),p,n)) #define BLOCK_OWNER(index,p,n) (((p) * ((index)+1)-1)/(n)) #define MIN(a,b) ((a)<(b)?(a):(b)) int NotIn(int id,int *picked); struct { double value; int index; 1 / 5 

基于高斯消去法解线性方程组（MPI） }local,global; int main(int argc,char *argv[]) { int id,p; MPI_Init(&argc,&argv); MPI_Comm_rank(MPI_COMM_WORLD,&id); MPI_Comm_size(MPI_COMM_WORLD,&p); //double a[n][n+1] = {{4,6,2,-2,8},{2,0,5,-2,4},{-4,-3,-5,4,1},{8,18,- 2,3,40}}; double a[n][n+1] = {{2,1,-5,1,8},{1,-3,0,-6,9},{0,2,-1,2,-5},{1,4,-7,6,0}}; int i,j; int index; int *picked; picked = (int *)malloc(sizeof(int) * n); //记录已被选中的行 for(i=0;i

基于高斯消去法解线性方程组（MPI） } MPI_Allreduce(&local,&global,1,MPI_DOUBLE_INT,MPI_MAXLOC,MPI_COMM_WORLD); // 归 约最大的值，并存入到 global 中 picked[i] = global.index; if(id == global.index) { } MPI_Bcast(&global.index,1,MPI_INT,id,MPI_COMM_WORLD); MPI_Allgather(&a[id][0],n+1,MPI_DOUBLE,a,n+1,MPI_DOUBLE,MPI_COMM_WORLD); /*每个线程解决的是对应行的求解，例如：线程号为 0 的线程仅得到 0 行的解，但是第 1 行的改动，0 线程没有办法得到，只有 1 线程自己才知道，所以需要使用 MPI_Allgather（） 函数进行去收集，并将结果存入到各个线程中，最后各个线程得到 a 为最新解*/ if(NotIn(id,picked)) { double temp = 0 - a[id][i] / a[picked[i]][i]; for(j=i;j

基于高斯消去法解线性方程组（MPI） printf("\n"); } double *x; x = (double *)malloc(sizeof(double) * n); for(i=(n-1);i>=0;i--) { x[i] = a[picked[i]][n] / a[picked[i]][i]; printf("x[%d] = %f\n",i,x[i]); for(j=0;j

基于高斯消去法解线性方程组（MPI） } return 1; } 四、并行结果 测试案例选用的是 4*4 的线程方程组，具体形式见公式（4-1），运行结果见图 4-1。 2 1 0 1       1 3  2 4 5  0 1  7  1 6  2 6       1 x 2 x 3 x 4 x              8 9 5  0       （4-1） 五、总结 图 4-1 并行结果 （1） 本次设计的算法是让一个线程去解决一个线性方程，但是当线程方程组的规模变大 时，需要按行分块，每一个线程负责一部分线程方程，这个程序还有待优化； （2） 本次实习熟悉 MPI_Allgather（）和 MPI_Allreduce（）函数的使用； （3） 明白线程之间在没有通信之前只能使用属于自己线程的数据，不能够使用其他线程 中的数据，否则，会造成程序或结果的错误。 5 / 5