Hi all
I use this function to calculate Determinant of Matrix of size nxn
if size is 3x3 it works well but if size is 20x20 or large it continues forever without stopping.
could you help me please.

/* Recursive definition of determinate using expansion by minors.*/
double Determinant(double **a,int n)
{
int i,j,j1,j2 ; // general loop and matrix subscripts
double det = 0 ; // init determinant
double **m = NULL ; // pointer to pointers to implement 2D square array

if (n < 1) // error condition, should never get here
{
error("Number of Rows and Columns is less than 1");
}
else if (n == 1)
{ // should not get here
det = a[0][0] ;
}
else if (n == 2) // basic 2X2 sub-matrix determinate definition.
{ // When n==2, this ends the the recursion series

det = a[0][0] * a[1][1] - a[1][0] * a[0][1];
}

else // recursion continues, solve next sub-matrix
{ // solve the next minor by building a
// sub matrix
det = 0 ; // initialize determinant of sub-matrix

// for each column in sub-matrix
for (j1 = 0 ; j1 < n ; j1++)
{
// get space for the pointer list
m = (double **) malloc((n-1)* sizeof(double *)) ;

for (i = 0 ; i < n-1 ; i++)
m[i] = (double*) malloc((n-1)* sizeof(double)) ;
// i[0][1][2][3] first malloc
// m -> + + + + space for 4 pointers
// | | | | j second malloc
// | | | +-> _ _ _ [0] pointers to
// | | +----> _ _ _ [1] and memory for
// | +-------> _ a _ [2] 4 doubles
// +----------> _ _ _ [3]
//
// a[1][2]
// build sub-matrix with minor elements excluded
for (i = 1 ; i < n ; i++)
{
j2 = 0 ; // start at first sum-matrix column position
// loop to copy source matrix less one column
for (j = 0 ; j < n ; j++)
{
if (j == j1)
continue ; // don't copy the minor column element

m[i-1][j2] = a[i][j] ; // copy source element into new sub-matrix
// i-1 because new sub-matrix is one row
// (and column) smaller with excluded minors
j2++ ; // move to next sub-matrix column position
}
}

det += (double)pow(-1.0,1.0 + j1 + 1.0) * a[0][j1] * Determinant(m,n-1) ;
// sum x raised to y power
// recursively get determinant of next
// sub-matrix which is now one
// row & column smaller

for (i = 0 ; i < n-1 ; i++) // free the storage allocated to
free(m[i]) ; // to this minor's set of pointers
free(m) ; // free the storage for the original
} // pointer to pointer

}
return(det) ;
}

Hi all
I use this function to calculate Determinant of Matrix of size nxn
if size is 3x3 it works well but if size is 20x20 or large it continues forever without stopping....
How do you know it continues forever? Maybe it will eventually arrive at the answer.

How long do you think you would have to wait? Without examining your code, and without any considerations of the amount of computer storage required to execute a deeply recursive calculation, let's think about it a little.

Here's an experiment: Run the program with a 10x10 matrix measure the time it takes.

I don't know what your system is (clock speed, etc.) but suppose for the sake of argument that it takes one second.

Now, it can be shown that a method that evaluates the determinant of an NxN matrix by expansion of minors requires a number of arithmetical operations that is proportional to N factorial. (That's N!.) See Footnote.

That means that if a 10x10 matrix takes one second, then an 11x11 matrix would take something like 11 seconds. A 12x12 matrix would take about 11*12 = 132 seconds. A 13x13 will take 11*12*13 seconds---about half an hour.

If you go up through 20x20, you can show that it would take something on the order of 10 to the power 11 seconds. This is more than twenty thousand years.

Suppose your computer is ten times as fast as mine, so it only takes 0.1 seconds for a 10x10. Then it will take about 1.1 seconds for an 11x11, etc. So you would only have to wait a couple of thousand years or so. (This assumes that your program wouldn't run out of memory before running to completion---not necessarily a valid assumption.)

Bottom line: Find another way to evaluate the determinant of a 20x20 matrix. Something like the Numerical Recipes LU decomposition routine can be used to find the determinant of a 20x20 matrix quite readily, and in a fraction of a second. (You can look it up; you can try it.)


Regards,

Dave

Footnote: It's not too hard to show formally, but we can get a feel for it by just looking at the work involved: The major work is evaluating the determinants of the sub-matrices. (A few more operations are required to combine the determinants.)

So...

A 3x3 requires evaluating three determinants of 2x2 matrices
A 4x4 requires four 3x3 evaluations
A 5x5 requires five 4x4
.
.
.
An NxN requres N (N-1)x(N-1) evaluations

So: that's where the "N factorial" comes from

.
"The purpose of computing is insight, not numbers"
---Richard W. Hamming