4
\$\begingroup\$

I have this algorithm that calculates the matrix determinant using recursive divide-and conquer-approach:

int determ(int a[max][max],int max) {
  int det=0, p, h, k, i, j, temp[max][max];
    //base case omitted
    for(p=0;p<max;p++) {
      h = 0;
      k = 0;
      for(i=1;i<max;i++) {
        for( j=0;j<max;j++) {
          if(j==p) {
            continue;
          }
          temp[h][k] = a[i][j];
          k++;
          if(k==max-1) {
            h++;
            k = 0;
          }
        }
      }
      det=det+a[0][p]*pow(-1,p)*determ(temp,max-1);
    }
    return det;
}

I want to optimize the main loop (with a loop unwinding or any strategy that can reduce the execution time). Any suggestion?

\$\endgroup\$
1
\$\begingroup\$

Sorry, it is not a divide and conquer, it's a combinatorial explosion. The timing complexity

$$T(n) = nT(n-1)$$

evaluates to n! - exponential growth. There is no way to heal the code; you have to choose another algorithm.

\$\endgroup\$
  • 1
    \$\begingroup\$ could you suggest me any better alternative algorithm? \$\endgroup\$ – AndreaF May 18 '14 at 1:05
  • \$\begingroup\$ Start with stackoverflow.com/questions/2435133/… \$\endgroup\$ – vnp May 18 '14 at 6:37
  • \$\begingroup\$ Seems that using the Cramer rule find determinant is O(n^3) but I don't know if is this strategy valid for all n*n matrix of any size, and I haven't idea how exactly should I implement this algorithm to get O(n^3) complexity code. Could you give me more details? \$\endgroup\$ – AndreaF May 18 '14 at 20:15
  • \$\begingroup\$ Gaussian elimination en.wikipedia.org/wiki/… is a good starting point. \$\endgroup\$ – vnp May 18 '14 at 21:25
  • \$\begingroup\$ what do you think about the efficency of the second c method proposed here? thanks rosettacode.org/wiki/Matrix_arithmetic \$\endgroup\$ – AndreaF May 18 '14 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.