CODEWITHSUNDEEP
c++algorithmvectorlinear-algebra
Phorce
Phorce

Reputation: 4642

An optimal way to calculate the subset of a vector of vectors

Okay, so I'm implementing an algorithm that calculates the determinant of a 3x3 matrix give by the following placements: 

A = [0,0 0,1 0,2 
     1,0 1,1 1,2 
     2,0 2,1 2,2]

Currently, the algorithm is like so:

float a1 = A[0][0]; 
float calula1 = (A[1][1] * A[2][2]) - (A[2][1] * A[1][2])

Then we move over to the next column, so it would be be:

float a2 = A[0][1];
float calcula2 = (A[1][0] * A[2][2]) - (A[2][0] * A[1][2]);

Like so, moving across one more. Now, this, personally is not very efficient and I've already implemented a function that can calculate the determinant of a 2x2 matrix which, is basically what I'm doing for each of these calculations.

My question is therefore, is there an optimal way that I can do this? I've thought about the idea of having a function, that invokes a template (X, Y) which denotes the start and ending positions of the particular block of the 3x3 matrix:

template<typename X, Y> 
float det(std::vector<Vector> data)
{
   //....

}

But, I have no idea if this was the way to do this, how I would be able to access the different elements of this like the proposed approach?

Upvotes: 1

Views: 180

Answers (1)

G. Bach
G. Bach

Reputation: 3909

You could hardcode the rule of Sarrus like so if you're exclusively dealing with 3 x 3 matrices.

float det_3_x_3(float** A) {
    return A[0][0]*A[1][1]*A[2][2] + A[0][1]*A[1][2]*A[2][0]
           + A[0][2]*A[1][0]*A[2][1] - A[2][0]*A[1][1]*A[0][2]
           - A[2][1]*A[1][2]*A[0][0] - A[2][2]*A[1][0]*A[0][1];
}

If you want to save 3 multiplications, you can go

float det_3_x_3(float** A) {
    return A[0][0] * (A[1][1]*A[2][2] - A[2][1]*A[1][2])
           + A[0][1] * (A[1][2]*A[2][0] - A[2][2]*A[1][0])
           + A[0][2] * (A[1][0]*A[2][1] - A[2][0]*A[1][1]);
}

I expect this second function is pretty close to what you have already.

Since you need all those numbers to calculate the determinant and thus have to access each of them at least once, I doubt there's anything faster than this. Determinants aren't exactly pretty, computationally. Faster algorithms than the brute force approach (which the rule of Sarrus basically is) require you to transform the matrix first, and that'll eat more time for 3 x 3 matrices than just doing the above would. Hardcoding the Leibniz formula - which is all that the rule of Sarrus amounts to - is not pretty, but I expect it's the fastest way to go if you don't have to do any determinants for n > 3.

Upvotes: 1

Related Questions