Calculate the matrix determinant and inverse faster

I was talking with a friend about this one and they reminded me that at school we were taught a different way to calculate determinants, which might also be fairly performant for 4x4 matrices, but I haven't tried coding it up yet:

• Set resultSign to 1
• If the top left cell is a zero:
• • If everything below is zero, then your determinant is zero, so you can return 0
  • If something below was non-zero, swap the rows and flip the sign on resultSign
  • Now that the top-left cell is non-zero, for every row below which was also non-zero, add or subtract the top row until you get 0
• Repeat for the next diagonal. (Could even use recursion still, if you wanted to get the 2x2 case right first and then work up to 3x3 and then 4x4.)
• If you get to the end without returning 0, compute the product of the cells on the diagonal and multiply by the sign, and bam, there's your determinant.
  
  

And now that I've read the forum a bit, I see that I'm about the 10,000th person to make this discovery.

The usual tricks to speed up multiplication assume that every multiplication between two values is one operation. They assume you will have n³ multiplication ops.

Then they go on to say that a 4×4 matrix multiplication only needs 47 multiplications. Compared to 4³ = 64, that's 73% of the time.

But wait, when I multiply matrices, I use vector operations to do the dot product. So I'm already running 3-4 times faster than the naïve case.

So I'm not sure these "smart" algorithms for multiplication will help me. At best, they will cause me to have to do new research to figure out how to apply vector operations to their new, more complex algorithm.

What would help my situation immensely would be matrix operations on the CPU.


(That and, a faster way to do cross product. Because when I profile my code, that is where all the time seems to be going right now.)




As an additional note on vector ops:

I tried to make a library where you just fed it multiplication operations to perform and it packed them into vectors for you. But it turns out, if you try to do this, the extra time copying the values around costs so much that there is no benefit. So the only way to profit from vector ops seems to be to use them to store your raw values.

Thus, my "tuple" type is wrapping a DoubleVector. My matrix, though, is still wrapping an ImmutableDoubleArray. So there might be some slight wins to converting the matrix to an array of DoubleVector. In saying that, to do that, you'd have an interesting time choosing whether to make it row major or column major. Intuition says, storing it column major might actually be more efficient, since that's what modern graphics APIs appear to have chosen. But for multiplying a matrix by a vector, row major is obviously going to be faster. Store it in both ways?