What's the best algorithm to invert a matrix of non-commutative elements? In my case I have a matrix of matrices.

From first principals by equating the elements of M * M' to I (where M' is the inverse) I've worked out the inverse for a 2x2 Matrix:

$$ M=\begin{bmatrix} A &B \\ C &D \\ \end{bmatrix} $$

$$ M^{-1}=\begin{bmatrix} (A-BD^{-1}C)^{-1} &(C-DB^{-1}A)^{-1} \\ -D^{-1}C(A-BD^{-1}C)^{-1} &-B^{-1}A(C-DB^{-1}A)^{-1} \\ \end{bmatrix} $$

In the above, you only need to perform 4 inversions: B, D and the components of the top row. The bottom row elements are obtained by multiplying the top row by 2 existing matrices.

One further optimisation of this is to choose to 2 "easiest" matrices to invert since you can transpose and/or swap the columns around and obtain the final result by transposing and/or swapping the rows.

As pointed out in the answers, one can use Schur complements to obtain similar / better formulae and recursively apply them to reach the result.

I've implemented the Doolittle LU Decomposition ensuring it respects multiplication order. Is there a better approach? It seems the concept of "pivot" is not really applicable (or at least more complex) when the elements are matrices, which is why I chose the simple Doolittle approach.