[Math] Minimal number of multiplications required to invert a 4×4 matrix

linear algebra

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 4×8 matrix whose left hand side is $A$ (the matrix to invert) and whose right hand side is $I_4$ (the 4×4 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 3×3 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 4×4 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?

Best Answer

We can invert a 2x2 matrix with 6 multiplies and one inversion. By Strassen's algorithm, we can multiply 2x2 matrices with 7 multiplies.

Partition your 4x4 matrix as

$$\left( \begin{matrix} A & B \\ C & D \end{matrix} \right) $$

We will reduce this to the identity.

Compute the inverse of $A$.

Perform Gaussian elimination

$$\left( \begin{matrix} I & A^{-1} B \\ 0 & D - CA^{-1}B \end{matrix} \right) $$

Let $E = D - C A^{-1} B$. Now compute $E^{-1}$. We can now finish Gaussian elimination.

Repeating these operations on an identity matrix tells us that the inverse is

$$ \left( \begin{matrix} A^{-1} + A^{-1} B E^{-1} C A^{-1} & -A^{-1} B E^{-1} \\ -E^{-1} C A^{-1} & E^{-1} \end{matrix} \right) $$

The calculation of this inverse requires two matrix inversions (12 multiplies and 2 real inversions), and six 2x2 multiplies:

  • $C A^{-1}$
  • $(C A^{-1}) B$
  • $E^{-1} (C A^{-1})$
  • $A^{-1} B$
  • $(A^{-1} B) E^{-1}$
  • $(A^{-1} B)(E^{-1} C A^{-1})$

for 54 multiplies and 2 real inversions in all.

Of course, using Strassen's algorithm for 2x2 matrices is a terrible idea. I don't know if the above organization of the calculation is reasonable or not even if you don't use Strasses algorithm; I suspect it is unlikely.

If $A$ turns out to be singular, you have to partition the matrix differently to do the calculation.

Related Question