Numerical Recipes Forum Determinant of Matrix nxn
 Register FAQ Calendar Search Today's Posts Mark Forums Read

#1
07-14-2008, 10:56 PM
 mahcs2010 Registered User Join Date: Jul 2008 Posts: 5
Determinant of Matrix nxn

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.

/* 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) ;
}
#2
07-15-2008, 12:10 AM
 davekw7x Registered User Join Date: Jan 2008 Posts: 453
Quote:
 Originally Posted by mahcs2010 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

Last edited by davekw7x; 07-15-2008 at 05:57 PM.

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Numerical Recipes Official Announcements     About the Numerical Recipes Forum     General Information on Numerical Recipes     Official Bug Reports (NR3, the Third Edition)     Old Bug Reports (Obsolete Editions of NR) Numerical Recipes Third Edition Forum     General Hints, Tips, and Tricks for Using NR3     General Problems in Using NR3     Rollover and Empanel     Plugin Problems     Methods: All Chapters in NR3     NR3 in Java     Using NR3 with MATLAB     Using NR3 with Python Obsolete Editions Forum     General Hints, Tips, and Tricks for Using NR     General Problems in Using NR     C++ Programming with NR     Fortran 90 Programming with NR     Alternatives to Numerical Recipes     NR in Other Computer Languages     General Computing and Open Discussions     Methods: Chapters 2, 11, and 18     Methods: Chapters 3, 4, 5, and 6     Methods: Chapters 7, 8, and 20     Methods: Chapters 9 and 10     Methods: Chapters 12 and 13     Methods: Chapters 14 and 15     Methods: Chapters 16 and 17     Methods: Chapter 19

All times are GMT -5. The time now is 03:28 PM.

 Numerical Recipes Software - Archive - Top