# Thread: Inverse of a large matrix

1. ## Inverse of a large matrix

I have a symmetric positive definite matrix of size 50 000 $\displaystyle \times$ 50 000, that is about $\displaystyle 1.3\cdot10^{9}$ unique elements. I need the diagonal elements of it's inverse.

Is there a direct way to obtain the diagonal of the inverse matrix, without calculating all the elements of the inverse, for example with some decomposition?

The matrix is too big to be inverted directly with Matlab on my computer, but I think I might be able to contruct an algorithm to calculate the inverse recursively blockwise. This programming task would take a couple of days however, and also the calculation would require probably several hours.

2. Originally Posted by hapap
I have a symmetric positive definite matrix of size 50 000 $\displaystyle \times$ 50 000, that is about $\displaystyle 1.3\cdot10^{9}$ unique elements. I need the diagonal elements of it's inverse.

Is there a direct way to obtain the diagonal of the inverse matrix, without calculating all the elements of the inverse, for example with some decomposition?

The matrix is too big to be inverted directly with Matlab on my computer, but I think I might be able to contruct an algorithm to calculate the inverse recursively blockwise. This programming task would take a couple of days however, and also the calculation would require probably several hours.
You might have an unforseen problem: your matrix is too big to fit in the
address space of a regular PC which is 4GB, of which 2 are not available.

You might get away with it on a 64bit machine, which ought to have a bigger
address space, but you will need 10GB just to store the elements, and
several times that to do anything with them.

Even if you decompose this into blocks each with 1 million distinct elements
that will leave you with over 1000 blocks.

What gives rise to such a large problem, meybe rethinking the approach will
allow you to avoid having to work with such large matrices.

RonL

3. Yes, I'm aware of the problem with 32-bit machines. I think I should test the operation with my home computer and 64-bit Linux.

I'm planning to divide the matrix into 100 blocks. My matlab can handle these slowly and even store two or three of them simultaneously in RAM. So I will need a lot of disk operations, but the problem can be cracked at least in theory. Time consumption is not a big problem, while also the creation of the matrix (to be inverted) takes like 30 hours. The research is mostly theoretical, so I don't have to care about the calculation times; they will be solved in the future anyway.

I think the matrix size (49153 $\displaystyle \times$ 49153 exactly) can't be reduced at the moment because of the application. I guess all the elements are also needed to calculate the diagonal of the inverse?

4. ## Solved

If someone is interested or facing a similar problem, here's what I eventually did:

I divided the matrix in 136 blocks, about 3000x3000 elements each. I computed cholesky decomposition $\displaystyle A=LL^T$ where L is triangular matrix. This can be done blockwise. (See: SpringerLink - Book Chapter Don't know if it's free content though). I inverted the cholesky matrix L blockwise, which is an easy task because it's triangular and multiplied it with its transpose (blockwise);
$\displaystyle A^{-1}=L^{-T}L^{-1}$

It seems to take some hours to calculate the inverse this way, but at least the problem can be solved with a modern desktop computer and with some simple block matrix operations.