Minimal number of multiplications required to invert a 4×4 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 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?

Solutions Collecting From Web of "Minimal number of multiplications required to invert a 4×4 matrix"

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

Partition your 4×4 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 2×2 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 2×2 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.

In his paper Gaussian Elimination is not optimal, Volker Strassen stated the following:

enter image description here

A more recent treatment of matrix inversion is provided by Intel. However, they are aiming at speed rather than at the minimum number of multiplications.