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

any links..suggestions would do

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 !

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

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 ?