在 MPI 上寻找矩阵行列式的方法的并行化

Question

如何在MPI上并行化求矩阵行列式的方法？如何并行化矩阵的填充，是否可以将数据从前一个进程传递到每个进程，我如何将其应用到我的代码中？

double GaussDet(double** mat, int size) {

    int determinant = 1;

    for (int i = 1; i < size; ++i)
    {
        for (int k = i; k < size; ++k)
        {
            for (int j = size - 1; j >= 0; --j)
            {
                mat[k][j] -= mat[k][i - 1] / mat[i - 1][i - 1] * mat[i - 1][j];
            }
        }
    }

    for (int i = 0; i < size; i++) {
      for(int j = 0; j < size; j++) {
        if(i == j)
        determinant *= mat[i][j];
      }
    }
    return determinant;
}

int main(int argc, const char * argv[])
{ 
    srand(time(NULL));
    int N = 4;

    double **matrix = malloc(N * sizeof(double*));
    for (int i = 0; i < N; i++) {
      matrix[i] = malloc(N * sizeof(double*));
    }
    fill_matrix(matrix, N);
    print_matrix(matrix, N);
    double det = GaussDet(matrix, N);
    print_matrix(matrix, N);
    printf("det = %f\n", det);
 
}

Answer 1

您描述的是通过简化为上三角形式，然后乘以对角线上的元素来计算行列式。上三角约简是高斯消元法（或：计算 LU 因式分解）的基础，所以我们假设这就是您要求的。

好的，所以你有一个矩阵和 MPI。 MPI 使用分布式内存，因此为了实现良好的实现，您需要分发矩阵。最简单的解决方案是让每个进程存储多个不同的行。列也是可能的，但这对参数没有影响。

高斯消元有很多并行性，但它有一个顺序组件：1/a[i,i] 主元的计算。您为 i 的一个值执行此操作，更新所有矩阵元素，为下一个 i 执行此操作，等等。需要注意的重要一点是，只有一个进程存储了该元素，因此只有一个进程知道枢轴的值。因此，该进程必须将其广播给所有其他进程。然后每个人都可以更新他们的矩阵元素。

首先编写代码：每个进程获取矩阵的一部分，然后计算因式分解。

现在，这个算法有问题：在你删除 pivot i 之后，存储它的进程不再活跃。所以在分解的过程中，你的并行度会越来越少。您可以通过给每个进程不是矩阵的块切片，而是通过循环的行来解决这个问题。还有一个更难描述的问题，其基本假设是将整行分配给一个进程。

因此，此算法的高质量实现非常罕见。 Scalapack 和 PLapack（均为 1990 年代），然后是 Elemental（2010 年代），它们几乎是唯一的。去显示这个问题是多么棘手。但正如我上面概述的那样，基础应该是可行的。

在 MPI 上寻找矩阵行列式的方法的并行化

Parallelization of the method for finding the determinant of a matrix on MPI

c

mpi