# Fast Determinant evaluator

• 05-21-2009
jack_carver
Fast Determinant evaluator
Can any 1 help me in implementing a fast determinant evaluator
i have a wriiten a code but its way too slow when determinant size is 1000x1000

Code:

```#include <iostream> using namespace std; int determinant(int size,int det[][100])  // size & row of the square matrix {         int temp[100][100],a=0,b=0,i,j,k;         int sum=0,sign;  /* sum will hold value of determinant of the current matrix */         if(size==2) return (det[0][0]*det[1][1]-det[1][0]*det[0][1]);                 sign=1;         for(i=0;i<size;i++)  // note that 'i' will indicate column no.         {                 a=0;                 b=0;                 // copy into submatrix and recurse                 for(j=1;j<size;j++) // should start from the next row !!                 {                         for(k=0;k<size;k++)                         {                                 if(k==i) continue;                                   temp[a][b++]=det[j][k];                         }                         a++;                         b=0;                 }                 sum+=sign*det[0][i]*determinant(size-1,temp);  // increnting row & decrementing size                 sign*=-1;         }         return sum; } int main() {         int i,j,det[100][100];         for(i=0;i<6;i++)                 for(j=0;j<6;j++)                         cin>>det[i][j];                 cout<<endl;                                cout<<determinant(6,det)<<endl; }```
Thank u !
• 05-21-2009
Snafuist
You are using Laplace expansion to compute the determinant, which is very slow by itself.

There are however some optimizations:
- apply Laplace expansion along a row / column which contains a lot of zeros
- do "sum+=sign*det[0][i]*determinant(size-1,temp);" only if det[0][i] is non-zero.
- don't compute a temporary matrix, instead think of a more general function interface. For users, use a wrapper function for convenience if necessary.
- the Rule of Sarrus is a nice base case for 3x3 matrices, check Wikipedia. You can easily derive the rule by applying Laplace expansion on a 3x3 matrix.

Rather than using Laplace expansion, consider faster methods of computing determinants. The easiest one is probably the Gaussian algorithm for computing determinants, best done by LU decomposition: remember that if A is a (upper/lower) triangular matrix, its determinant is the product of its diagonal entries. Hence:

det(A) = det(L*U) = det(L) * det(U) = det(U) = u(1,1) * u(2,2) * ... * u(n,n)

(Note that the diagonal entries of L are all 1, hence det(L) = 1.)

Greets,
Philip
• 12-28-2009
jack_carver
Determinant
Is there any way to compute the determinant % N using gaussian elim

Since while we are reducing the rows the other elements are forced to become fractions :(

Is there any way around this ?