When I was watching the course on convex optimization by Stephen Boyd, at some point he says is to exploit structure when possible. One of the examples is the following matrix.
$$ {\bf A} = \begin{pmatrix} A & B \\ C & D \\ \end{pmatrix} $$
where $A$ is a big diagonal matrix, and the rest are dense block matrices. Such as the following picture, where the white part is all zeros.
.
The linear system $\textbf{A}x=y$ is usually solved by solvers who are going to treat the matrix as a whole, in this case, the easy implementation is to have an sparse matrix to do work with an sparse solver. However, since there is a diagonal matrix, we might be able to do it faster. I was looking at the Block Matrix Inversion to solve the linear system and implement it.
Extracting from wikipedia, we have the following formula:
$$ {\displaystyle \mathbf {P} ={\begin{bmatrix}\mathbf {A} &\mathbf {B} \\\\\mathbf {C} &\mathbf {D} \end{bmatrix}}^{-1}={\begin{bmatrix}\left(\mathbf {A} -\mathbf {BD} ^{-1}\mathbf {C} \right)^{-1}&-\left(\mathbf {A} -\mathbf {BD} ^{-1}\mathbf {C} \right)^{-1}\mathbf {BD} ^{-1}\\\\-\mathbf {D} ^{-1}\mathbf {C} \left(\mathbf {A} -\mathbf {BD} ^{-1}\mathbf {C} \right)^{-1}&\quad \mathbf {D} ^{-1}+\mathbf {D} ^{-1}\mathbf {C} \left(\mathbf {A} -\mathbf {BD} ^{-1}\mathbf {C} \right)^{-1}\mathbf {BD} ^{-1}\end{bmatrix}}.} $$
Some parts of the matrix, such as $\left(\mathbf {A} -\mathbf {BD} ^{-1}\mathbf {C} \right)^{-1}$, seem to be non-optimal, since we are computing the inverse of a dense big matrix. Is there something I'm not seeing? I'm not sure how to tackle this problem.
Maybe I'm looking this problem from a wrong angle. Do you have any idea how to solve this linear system efficiently?