計算矩陣行列式

我試圖計算矩陣（任何大小）的行列式，用於自編碼/面試練習。我第一次嘗試使用遞歸現象，導致我到下面的實現：計算矩陣行列式

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); 
}

但是對比性能後，我發現，叉的性能/加入的做法是非常糟糕的，與基體的尺寸越大，越慢變（相比於第一方法）。開銷在哪裏？任何人都可以闡明如何改善這一點？

來源

2013-05-17 all_by_grace

在拋出線程之前，我會停止在循環中分配。一種選擇可能是有兩個數組參數決定哪些列和行要計算而不是N. –

我建議你看看一些算法設計爲並行。我沒有通過你的算法，但根據我的經驗，通過搜索可以發現很多聰明的優化問題。 –

ForkJoin代碼較慢的主要原因是它實際上是在拋出一些線程開銷的情況下序列化的。要從fork/join中受益，您需要1）先fork所有實例，然後2）等待結果。將「計算」中的循環拆分爲兩個循環：一個用於分叉（將數組中的ParallelDeterminants實例存儲在數組中），另一個用於收集結果。

此外，我建議只叉在最外層，而不是任何內層。你不想創建O（N^2）線程。

來源

2013-08-30 04:12:45

計算矩陣行列式

回答

相關問題