Fast Determinant evaluator

This is a discussion on Fast Determinant evaluator within the C Programming forums, part of the General Programming Boards category; Can any 1 help me in implementing a fast determinant evaluator i have a wriiten a code but its way ...

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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 !
    Last edited by jack_carver; 05-21-2009 at 01:13 AM.

  2. #2
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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 ?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. matrix determinant
    By roaan in forum C Programming
    Replies: 1
    Last Post: 06-30-2009, 12:44 PM
  2. Replies: 6
    Last Post: 02-27-2009, 03:43 PM
  3. Expression Evaluator Contest
    By Stack Overflow in forum Contests Board
    Replies: 20
    Last Post: 03-29-2005, 09:34 AM
  4. determinant?! HELP!!!
    By ankurtrick in forum C Programming
    Replies: 1
    Last Post: 10-08-2004, 09:12 PM
  5. Saving a part of screen into a file fast!
    By Zap in forum C++ Programming
    Replies: 4
    Last Post: 06-28-2003, 10:56 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21