# Optimization of matrix determinant calculation

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?

## 1 Answer

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.

• could you suggest me any better alternative algorithm? – AndreaF May 18 '14 at 1:05
• Start with stackoverflow.com/questions/2435133/… – vnp May 18 '14 at 6:37
• 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? – AndreaF May 18 '14 at 20:15
• Gaussian elimination en.wikipedia.org/wiki/… is a good starting point. – vnp May 18 '14 at 21:25
• what do you think about the efficency of the second c method proposed here? thanks rosettacode.org/wiki/Matrix_arithmetic – AndreaF May 18 '14 at 23:47