Recursive function and memory problem

[WeeBeng]

I have this recursive function which can be used to find the determinant of a n by n size matrix. The function can take in non-fixed size 2-dimensional array and works very well when n is small i.e. less than 10.
However problem arises when n is large, the function either does not work at all as in the programme crashes or takes an awlfully long time to compute. I need the function to be able to take in large n in the order of 100. Is there any other way to over come this?
Thanks for any help.



void main()
{

double deter;
double **alpha;
int i,j;

for (j=0;j<9;j++){
alpha = malloc(9*sizeof(double *));
}
for (i=0;i<9;i++){
alpha[i] = malloc(9*sizeof(double));
}

for (i=0;i<9;i++){
for(j=0;j<9;j++){
alpha[i][j]=rand()/55.34;
printf("%f\t",alpha[i][j]);
}
printf("\n");
}

deter=Determinant(alpha,9);
}

/***Function for Determinant***/
double Determinant(double **a,int n)
{
int i,j,j1,j2;
double det = 0;
double **m = NULL;

if (n < 1) { /* Error */

} else if (n == 1) { /* Shouldn't get used */
det = a[0][0];
} else if (n == 2) {
det = a[0][0] * a[1][1] - a[1][0] * a[0][1];
} else {
det = 0;
for (j1=0;j1<n;j1++) {
m = malloc((n-1)*sizeof(double *));
for (i=0;i<n-1;i++)
m[i] = malloc((n-1)*sizeof(double));
for (i=1;i<n;i++) {
j2 = 0;
for (j=0;j<n;j++) {
if (j == j1)
continue;
m[i-1][j2] = a[i][j];
j2++;
}
}
det += pow(-1.0,j1+2.0) * a[0][j1] * Determinant(m,n-1);
for (i=0;i<n-1;i++)
free(m[i]);
free(m);
}
}
return(det);
}

[DanM]

For the crasing part, you may want to increase your stack size.
For the performance part, I think you can rewrite the algorithm so it won't require to create and then destroy small matrixes - a little bit of C++ will make things easier (better abstraction).

Dan

[dude_1967]

WeeBeng,

I agree with Dan. There must be a better algorithm which does not create and destroy the various sub-matrices. Remember, the matrix elements already exist and are already allocated. It seems like a good algorithm would not recopy the elements.

Unfortunately, I do not have any sample code for matrix determinants or matrix inversion.

If I may I would like to append the original question:

Does anyone know of a scalable matrix library written in good platform-independent C++ which is available?

Sincerely,
Chris.

:)

[PaulWendt]

There is SOME form of a matrix library in boost, but I don't see a
whole lot of operations that exist for it. Perhaps it can be
extended by someone? I'd looked for matrix stuff in the past and
I'm surprised that boost doesn't have something more complete.
Actually, I didn't thoroughly examine boost so maybe they DO
have something more complex :)

http://www.boost.org/libs/numeric/ublas/doc/

--Paul

[KevinHall]

Numerical Recipes is always a good reference for math related stuff -- granted it is written in C and uses 1-based arrays (as opposed to 0-based arrays). But the algorithms are sound and rather efficient:

http://www.ulib.org/webRoot/Books/Numerical_Recipes/bookcpdf.html

And then there's the Matrix Template Library which has newer algorithms, is very fast, and is written in C++:

http://www.osl.iu.edu/research/mtl/