2
\$\begingroup\$

I'm looking for the best and fastest way to do a determinant, for determinants until 15x15.

int Determinant(const vector<vector<int> > &a,int n)
{
   int i,j,j1,j2;
   int det = 0;
   vector<vector<int> > m(n, vector<int>(n));

    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++) 
      {
         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 += pot(-1,1+j1+1) * a[0][j1] * Determinant(m,n-1);
      }
   }
   det = abs(det)%2;
   return det;
}
\$\endgroup\$
  • \$\begingroup\$ Could you indicate whether my answer was helpful, or if not, how it could be improved? \$\endgroup\$ – TemplateRex Jun 13 '13 at 21:21
2
\$\begingroup\$

Unless this is a homework assignment, you should probably not be writing your own linear algebra routines, but rely on libraries instead. Not only is it very hard to write correct and efficient general-purpose algorithms, for numerical algorithms there is an added requirement of numerical stability. For those reasons it is best to use established libraries such as Eigen.

A determinant can be done using the example in the documentation

#include <iostream>
#include <Eigen/Dense>
using namespace std;
using namespace Eigen;
int main()
{
    Matrix3f A;
    A << 1, 2, 1,
         2, 1, 0,
        -1, 1, 2;
    cout << "Here is the matrix A:\n" << A << endl;
    cout << "The determinant of A is " << A.determinant() << endl;
}

Output

Here is the matrix A:
1 2 1
2 1 0
-1 1 2
The determinant of A is -3

Granted, for binary matrices the numerical stability argument that holds for floating point matrices is not really relevant, but the correctness and efficiency arguments remain important enough to warrant library use over hand-written implementations.

UPDATE: I just noticed that you got the same suggestion to start exploring Eigen in your other CodeReview question. I really encourage you to do so because it lets you focus on your application rather than on low-level implementation details that have been solved by others already. Unless of course, learning such details is what you are interested in.

\$\endgroup\$
  • \$\begingroup\$ Ok, the point is that has be able to be compiled in any computer without the need of installing something new \$\endgroup\$ – Trouner Jun 14 '13 at 7:15
  • \$\begingroup\$ @Trouner I understand your hesitance for reliance on 3rd party code. OTOH, reinventing the wheel has its own costs. Regarding portability: Eigen is available on Windows, Linux and Mac, and it is open source. Other than that, I don't think this forum is the best place to get good matrix-algorithm feedback. \$\endgroup\$ – TemplateRex Jun 14 '13 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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