Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have done a program to calculate a determinant of a matrix. My program works, but the problem is that it takes long time to calculate, especially for big matrix. Could you tell me how can a perform my program in order to calculate the determinant in the shortest possible time?

double Matrice::Determinant(int n)
{
   cout<<"n = "<<n<<endl;
   int i,j,j1,j2;
   double det = 0;
   Matrice tmp(n,n);
   if (n < 1) 
   {
   } 
   else if (n == 1) 
   { 
      det = this->get_el(0,0);
   } else if (n == 2) {
      det = this->get_el(0,0) * this->get_el(1,1) - this->get_el(1,0) * this->get_el(0,1);
   } else {
      det = 0;
      for (j1=0;j1<n;j1++) {
         for (i=1;i<n;i++) {
            j2 = 0;
            for (j=0;j<n;j++) {
               if (j == j1)
                  continue;
               tmp.set_el(i-1,j2,get_el(i,j));
               j2++;
            }
         }
         det += pow(-1.0,1.0+j1+1.0) * get_el(0,j1) * tmp.Determinant(n-1);
      }
   }
   return det;
}

Thank you.

share|improve this question
1  
Your algorithm runs in time $O(n!)$ and is probably numerically unstable. Always try to use a library routine when doing calculations with matrices. In this case, there is no LAPACK routine for determinant, but you can use some of the decomposition routines to get access to the eigenvalue. See for example the link in my comment to Berci's answer. –  Yuval Filmus Oct 1 '12 at 14:12
    
Wow! This makes me think of sorting an array by generating all permutations and returning the first one that is ordered. –  marty cohen Oct 1 '12 at 16:20
add comment

2 Answers 2

up vote 2 down vote accepted

One simple way is to do an LU decomposition and then multiply the determinants of the resulting matrices, because

$$\det M=\det LU =\det L \det U.$$

This is $O(n^3)$.

There are faster but more complicated ways.

I should mention that answer is just if you are writing this for your own edification. If you actually need to use such a routine in some application, you should follow Yuval Filmus's advice and find a library routine.

share|improve this answer
add comment

Use the Gaussian algorithm to get an upper triangle matrix, and multiply its elements in the diagonal.

share|improve this answer
    
Here is a link to some code using LAPACK: r-bloggers.com/matrix-determinant-with-the-lapack-routine-dspsv –  Yuval Filmus Oct 1 '12 at 14:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.