Thread: 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