计算矩阵行列式

Question

我正在尝试计算矩阵(任何大小)的行列式,用于自编码/面试练习.我的第一次尝试是使用递归,这导致我进行以下实现:

import java.util.Scanner.*;
public class Determinant {

    double A[][];
    double m[][];
    int N;
    int start;
    int last;

    public Determinant (double A[][], int N, int start, int last){
            this.A = A;
            this.N = N;
            this.start = start;
            this.last = last;
    }

    public double[][] generateSubArray (double A[][], int N, int j1){
            m = new double[N-1][];
            for (int k=0; k<(N-1); k++)
                    m[k] = new double[N-1];

            for (int i=1; i<N; i++){
                  int j2=0;
                  for (int j=0; j<N; j++){
                      if(j == j1)
                            continue;
                      m[i-1][j2] = A[i][j];
                      j2++;
                  }
              }
            return m;
    }
    /*
     * Calculate determinant recursively
     */
    public double determinant(double A[][], int N){
        double res;

        // Trivial 1x1 matrix
        if (N == 1) res = A[0][0];
        // Trivial 2x2 matrix
        else if (N == 2) res = A[0][0]*A[1][1] - A[1][0]*A[0][1];
        // NxN matrix
        else{
            res=0;
            for (int j1=0; j1<N; j1++){
                 m = generateSubArray (A, N, j1);
                 res += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * determinant(m, N-1);
            }
        }
        return res;
    }
}

到目前为止,这一切都很好,它给了我一个正确的结果.现在我想通过利用多个线程来计算这个行列式值来优化我的代码.我尝试使用Java Fork/Join模型对其进行并行化.这是我的方法:

@Override
protected Double compute() {
     if (N < THRESHOLD) {
         result = computeDeterminant(A, N);
         return result;
     }

     for (int j1 = 0; j1 < N; j1++){
          m = generateSubArray (A, N, j1);
          ParallelDeterminants d = new ParallelDeterminants (m, N-1);
          d.fork();
          result += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * d.join();
     }

     return result;
}

public double computeDeterminant(double A[][], int N){
    double res;

    // Trivial 1x1 matrix
    if (N == 1) res = A[0][0];
    // Trivial 2x2 matrix
    else if (N == 2) res = A[0][0]*A[1][1] - A[1][0]*A[0][1];
    // NxN matrix
    else{
        res=0;
        for (int j1=0; j1<N; j1++){
             m = generateSubArray (A, N, j1);
             res += Math.pow(-1.0, 1.0+j1+1.0) * A[0][j1] * computeDeterminant(m, N-1);
        }
    }
    return res;
}

/*
 * Main function
 */
public static void main(String args[]){
    double res;
    ForkJoinPool pool = new ForkJoinPool();
    ParallelDeterminants d = new ParallelDeterminants();
    d.inputData();
    long starttime=System.nanoTime();
    res = pool.invoke (d);
    long EndTime=System.nanoTime();

    System.out.println("Seq Run = "+ (EndTime-starttime)/100000);
    System.out.println("the determinant valaue is  " + res);
}

然而,在比较性能之后,我发现Fork/Join方法的性能非常糟糕,矩阵维度越高,它变得越慢(与第一种方法相比).开销在哪里？任何人都可以阐明如何改善这一点吗？

Answer 1

ForkJoin 代码较慢的主要原因是它实际上是在序列化时引入了一些线程开销。要从 fork/join 中受益，您需要 1) 首先 fork 所有实例，然后 2) 等待结果。将“计算”中的循环拆分为两个循环：一个用于 fork（将 ParallelDeterminants 的实例存储在数组中），另一个用于收集结果。

另外，我建议只在最外层进行分叉，而不是在任何内部进行分叉。您不想创建 O(N^2) 线程。