Recursive function and memory problem
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.
Code:
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);
}
Matrix: Are you "the one"
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.
:)
