efficient matrix inversion problem

Question

So I'm trying to invert a matrix of the $\begin{pmatrix} A & B \\ C & D \end{pmatrix}$ where $A$ and $D$ are square, $D$ is much larger than $A$, and $D$ is diagonal. $A$ $B$ and $C$ have no particular structure. Is there a fast way to do this that takes advantage of D's being diagonal?

Answer 1

Copied from Wikipedia (for archive purposes):

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

In this case we only need to invert D (easy) and $\mathbf{A-BD^{-1}C}$ (hopefully small).

Answer 2

If all the diagonal elements of $D$ were all nonzero, then you could use row and column operations to change the matrix to $X\begin{pmatrix} A & B \\ C & D \end{pmatrix}Y =\begin{pmatrix} \overline{A} & 0 \\ 0 & D \end{pmatrix}$ and being nonsingular this has an inverse $Z$:

$\begin{pmatrix} A & B \\ C & D \end{pmatrix}YZX =I$

If $\overline{A}$ is small, its inverse would not be computationally complex, and likewise D is easy to invert, and the rest is row/column operations.