|
|
Post by trejkaz on Feb 28, 2022 0:13:42 GMT
So I ran across this apparently well-known algorithm: en.wikipedia.org/wiki/LU_decompositionCalculating inverse of a 4x4 matrix, best times for 10,000 runs: Algorithm in the book: 61.3729 ms Using LU decomposition: 12.0178 ms Not too bad! In the grand scheme though, it only shaves a second off a render time of ~ 40 seconds. |
|
|
|
Post by Jamis on Feb 28, 2022 23:58:04 GMT
Thanks for pointing that other algorithm out! Ultimately, it came down to which algorithm I felt I could describe and decompose sufficiently in the space I had, such that it could be implemented test-first.
|
|
|
|
Post by trejkaz on Mar 22, 2022 6:51:23 GMT
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.
But actually, the reason why I was looking at faster ways was that I wanted to compute the determinant of a 200x200 matrix and it was taking minutes to run.  |
|
