Optimization of matrix determinant calculation

Question

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?

Answer 1

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.

• AndreaF: could you suggest me any better alternative algorithm?
• vnp: Start with stackoverflow.com/questions/2435133/…
• AndreaF: 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?
• vnp: Gaussian elimination en.wikipedia.org/wiki/… is a good starting point.
• AndreaF: what do you think about the efficency of the second c method proposed here? thanks rosettacode.org/wiki/Matrix_arithmetic