Minimal number of multiplications required to invert a 4x4 matrix
Four by four real (well, floating point...) matrices are used in computer
graphics to represent projections. Sometimes we need to compute their
inverses. How many multiplications are required?
Valve's Source SDK implements the "pen&paper" algorithm: start with a 4x8
matrix whose left hand side is $A$ (the matrix to invert) and whose right
hand side is $I_4$ (the 4x4 identity matrix); apply Gauss moves until the
left hand side is $I_4$ and the right hand will be $A^{-1}$. This
algorithm requires (by inspecting the code) $4 \cdot 8 + 4 \cdot 4 \cdot 8
= 160$ multiplications.
Solving $AX = I$ applying Cramer's rule for each element and computing
each 3x3 determinant with Sarrus's rule improves on that: we need $6 \cdot
16$ multiplications for the cofactors, then $4$ more for the determinant
of the 4x4 matrix, plus $16$ multiplications for the inverse of that, for
a total of $6 \cdot 16 + 4 + 16 = 116$ multiplications.
Cleverly precalculating products of two elements as in this answer
requires (again inspecting the code) $2\cdot 12 + 6 + 4 \cdot 16 = 94$
multiplications.
Can we do better? Can we prove we can't?
No comments:
Post a Comment