मैट्रिक्स निर्धारक की गणना

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

अब तक यह सब अच्छा है और यह मेरे लिए एक सही परिणाम देता है। अब मैं इस निर्धारक मूल्य की गणना करने के लिए एकाधिक धागे का उपयोग करके अपना कोड अनुकूलित करना चाहता हूं। मैंने जावा फोर्क/मॉडल में शामिल होने का उपयोग करके इसे समानांतर करने की कोशिश की। यह मेरा दृष्टिकोण है:

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

हालांकि प्रदर्शन की तुलना के बाद, मैंने पाया कि कांटा के प्रदर्शन/दृष्टिकोण से जुड़ें बहुत खराब है, और उच्च मैट्रिक्स आयाम, धीमी हो जाता है (पहले की तुलना में दृष्टिकोण)। ओवरहेड कहां है? क्या कोई इस पर सुधार करने के लिए प्रकाश डाल सकता है?

Answer 1

फोर्कजॉइन कोड धीमा होने का मुख्य कारण यह है कि वास्तव में इसे फेंकने वाले कुछ थ्रेड ओवरहेड के साथ क्रमबद्ध किया जाता है। कांटा/जुड़ने से लाभ उठाने के लिए, आपको पहले सभी उदाहरणों को फोर्क करना होगा, फिर 2) परिणामों की प्रतीक्षा करें। अपने लूप को "गणना" में दो लूपों में विभाजित करें: एक फोर्क (समानांतर डिटर्मिनेंट्स के उदाहरणों को संग्रहीत करना, कहें, एक सरणी) और दूसरा परिणाम एकत्र करने के लिए।

इसके अलावा, मैं केवल बाहरी स्तर पर कांटा का सुझाव देता हूं, न कि किसी भी आंतरिक में। आप ओ (एन^2) थ्रेड बनाना नहीं चाहते हैं।