Inverting really big symmetric block diagonal matrix

Question

I have a really big symmetric 7.000.000 X 7.000.000 matrix that i would like to invert. The matrix is extremely sparse and it can be rearranged as to become a block diagonal matrix. The biggest blocks are around 1500 X 1500 but most blocks are much smaller like 4 X 4. What is an efficient way to find the inverse? scipy.sparse.linalg.inv in Python gives me a memory error.

Answer 1

I think you already know the answer- find the inverse of each of the small diagonal blocks. The details of how you might break the matrix up into the block in Python are something out of scope for this stackexchange group.

As others have suggested you most likely don't really need the inverse of this matrix and could probably do everything you need with a Cholesky factorization of the individual blocks.

I'd encourage you to step back and ask a broader question that includes relevant background and explains what problem you are actually trying to solve.

Answer 2

I believe breaking your monstrous matrix into smaller blocks won't help you that much cause as I mentioned in my comment, using inverse of a huge sparse matrix is a really bad idea cause generally inverse of a huge sparse matrix could be a dense matrix, which probably you can't afford to even store it in your memory. But, in order to show you how you can find the inverse of a general matrix in terms of inverse of blocks (keep in mind that you need to break up your matrix into blocks that actually each block should be invertible.), I would suggest this mechanism, which I doubt would be useful at all here. Let's say you can break up your $\mathbf{X}$ matrix into this block form:

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

Remember $\mathbf{A}$ and $\mathbf{D}$ must be square matrices and be invertible and also $\mathbf{D} - \mathbf{C} \mathbf{A}^{-1} \mathbf{B}$ must be invertible too. So, you see it's not really easy to satisfy these conditions, specifically the last one, but if you satisfy them, you find the inverse of $\mathbf{X}$ as:

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

Also, somewhere in your comments, you mentioned that your matrix is block diagonal. So, if it is the case, instead of using the above mechanism, you have this for $\mathbf{X}$:

$$\mathbf{X} = \begin{bmatrix} \mathbf{A}_1 & 0 & \cdots & 0 \\ 0 & \mathbf{A}_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{A}_n \end{bmatrix}$$

Where $\mathbf{A}_{i}$ are block diagonals. So, you find the inverse much easier but still you need the inverse of each block diagonal, as:

$$\mathbf{X}^{-1} = \begin{bmatrix} \mathbf{A}_{1}^{-1} & 0 & \cdots & 0 \\ 0 & \mathbf{A}_{2}^{-1} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{A}_{n}^{-1} \end{bmatrix}$$

It looks easier, but the challenge is that can you guarantee that each block diagonal $\mathbf{A}_{i}$ is invertible? I doubt you can, but give it a try!

Finally, I second Brian Borchers suggestion and recommend you to think if it is possible to avoid using inverse, which makes your life much much easier.