#1




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. 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 submatrix 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 submatrix { // solve the next minor by building a // sub matrix det = 0 ; // initialize determinant of submatrix // for each column in submatrix for (j1 = 0 ; j1 < n ; j1++) { // get space for the pointer list m = (double **) malloc((n1)* sizeof(double *)) ; for (i = 0 ; i < n1 ; i++) m[i] = (double*) malloc((n1)* 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 submatrix with minor elements excluded for (i = 1 ; i < n ; i++) { j2 = 0 ; // start at first summatrix 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[i1][j2] = a[i][j] ; // copy source element into new submatrix // i1 because new submatrix is one row // (and column) smaller with excluded minors j2++ ; // move to next submatrix column position } } det += (double)pow(1.0,1.0 + j1 + 1.0) * a[0][j1] * Determinant(m,n1) ; // sum x raised to y power // recursively get determinant of next // submatrix which is now one // row & column smaller for (i = 0 ; i < n1 ; 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




Quote:
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 secondsabout 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 completionnot 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 submatrices. (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 (N1)x(N1) 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; 07152008 at 04:57 PM. 
Thread Tools  
Display Modes  

