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 Answer 1

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\$
6
  • 1
    \$\begingroup\$ could you suggest me any better alternative algorithm? \$\endgroup\$
    – AndreaF
    May 18, 2014 at 1:05
  • \$\begingroup\$ Start with stackoverflow.com/questions/2435133/… \$\endgroup\$
    – vnp
    May 18, 2014 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, 2014 at 20:15
  • \$\begingroup\$ Gaussian elimination en.wikipedia.org/wiki/… is a good starting point. \$\endgroup\$
    – vnp
    May 18, 2014 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, 2014 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.