Sign in to follow this  
AzurArcher

Determinant

Recommended Posts

Hi, I am trying to write a member function for a matrix class to compute the determinant, the code is as follows:
t matrix::determinant()
{
   if(rows != cols);
      //throw DimensionMismatchException

   if(rows == 1)
      return mat[0][0];
   else
   {
      t det = 0;
      for(int i = 0; i < cols; i++)
      {
         det += (t)pow(-1,i) * mat[0][i] * this.deleteRowCol(0,i).determinant(); 
      }
      return det;
   }
}
the expansion by minors for an nxm matrix. The matrix class is a template defined as follows:
template<int rows, int cols, typename t>
class matrix
When I try to compile this, I get it still trying to compile a matrix with size 0x0 which creates a compile error. Why is this happening even with the check if(rows == 1)? Thanks, Max

Share this post


Link to post
Share on other sites
Both branches get generated. If statements are code, not template metacode.

First, write a square matrix class (well you can avoid this, but it makes things easier). (A square matrix being a class templated on one integer size parameter, plus t. It inherits a generic n x n matrix, and forwards constructors onto it. Note that as POD, you can do layout based binary casting safely!). Write a function that takes a generic matrix, and either returns a square matrix or throws.

Write a row removal function that takes a square matrix, and returns a square matrix one smaller.

Then write a template determinate function that takes a square matrix.

Specialize the 1x1 matrix version to simply return the value in the matrix.

Then your non-specialized determinate function reads like your else clause. There is no need to check for rows==1, as that is handled by the specialization.

You can do this without creating the square matrix class, but it can make things easier. :)

...

Actually...

template<int size, typename T>
struct determinateHelper {
T operator()( Matrix<size, size, T> const& src ) const {
// the non-size=1 case
}
};

template<typename T>
struct determinateHelper<1, T> {
T operator()( Matrix<1, 1, T> const& src ) const {
// the size=1 case
}
};

template<int size, typename T>
T determinate( Matrix<size,size,T> const& src ) {
return determinateHelper<size, T>()(src);
}


Now you do compile-time checking on the Matrix passed in. If you pass in a Matrix that isn't square, you fail to compile. :) (This can cause issues down the road).

You can allow for non-square matrix options via:

template< typename Matrix, typename T>
T determinate( Matrix const& src ) {
throw you_suck();
return T();
}


which is an override that will match less than the square matrix, I think (or maybe it won't work, hmm).

Share this post


Link to post
Share on other sites
Besides the problem with templates, I should mention that that method to compute the determinant is actually pretty slow: The running time is O(n!).

A much better procedure is to use Gaussian elimination and multiply the elements in the diagonal: The running time is O(n^3).

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
Besides the problem with templates, I should mention that that method to compute the determinant is actually pretty slow: The running time is O(n!).

A much better procedure is to use Gaussian elimination and multiply the elements in the diagonal: The running time is O(n^3).

I always figured that algorithm would run slower but i never bothered to analyze it, i'll switch to that way, converting it to a triangular matrix and using the diagonals correct?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this