1
$\begingroup$

I have a big matrix of size 200000 x 200000. I need to compute its inverse. But it gives out of memory error on using numpy.linalg.inv. Is there any way to compute the inverse of a large sized matrix.

$\endgroup$
  • $\begingroup$ You may want to see here. It may help you. $\endgroup$ – Media Mar 23 '19 at 9:28
  • $\begingroup$ That is a large matrix to compute an inverse. If the data elements are floats then there is fair amount of floating point operations in progress. That needs memory. Try increasing your RAM for such bigger operations. Suggestion by @Media is also helpful $\endgroup$ – Savinay_ Mar 23 '19 at 9:37
  • $\begingroup$ @Savinay_ Yes the data elements are floats. Some values are even of the range of 10^-6 $\endgroup$ – shaifali Gupta Mar 23 '19 at 9:40
  • $\begingroup$ Another approach can be using another programming language. I guess in java there are some supports for that even if the RAM is full. I don't know the inner implementation but I guess they use paging capabilities. $\endgroup$ – Media Mar 23 '19 at 9:49
  • $\begingroup$ @shaifaliGupta You need to increase your memory for sure.Floating point operations such as matrix inversions take up to O(n^3) complexity (time and memory expensive). You have a very big matrix to inverse. That needs memory. $\endgroup$ – Savinay_ Mar 23 '19 at 9:52
1
$\begingroup$

Well it does not matter the language you will use, I am surprised you can even store that matrice in memory... I had a similar problem while researching on kernel methods.

  • First, to put in perspective how huge that matrix is, I will assume each element is 32 bit word: $ 200,000 \times 200,000 \times 32 = 1.28 \times 10^{12} $ bits or 149 GB

The bitlenght is variable but even for a boolean matrix that is about 4,65 GB and you said your data is a bit more complex than that.

Solution 1

If you trying to solve a linear system there are many iterative solutions that might help you computing an 200,000 x 1 array aproximation of your system answer without having to store that absurdly large matrix in memory. But you should be aware that this might take a bit long because you might have to load information from the disk.

Solution 2

Another possible solution, if you really need that inverse is if that matrix can be expressed as sumation of outer products of vectors. If so, you can do this:

$$ M = \sum v_i.u_i^T $$

Get the first set element of the sum and invert it so you have $M^{-1}_{bad aproximation}$ matrix by using pseudoinverse, instead of doing the outerproduct you can invert $u_1$ and $v_1$ and use Moore-Penrose Inverse property:

$$ M^{-1}_{bad aproximation} = (v_1.u_1)^\dagger = v_1^\dagger . u_1^\dagger $$

Combine this with Sherman-Morrison formula to add the other $v_i$ and $u_i$ vectors.

Sherman-Morrison formula gives: $$ (A + uv^T)^{-1} = A^{-1} - \dfrac{A^{-1}uv^TA^{-1}}{1 + v^TA^{-1}u} $$

Solution 3

You might try using Schur Complement which allows you to do the following:

Given a matrix $M$, it can be expressed as $$ M = \begin{bmatrix} A & B \\ C & D \\ \end{bmatrix} $$ where $A$ and $B$ must be square you can solve the inverse of $M$ blockwise as:

$$ M^{-1} = \begin{bmatrix} (M/D)^{-1} & (M/D)^{-1}BD \\ -D^{-1}C(M/D)^{-1} & (M/A)^{-1} \\ \end{bmatrix} $$ where $(M/D)$ denotes the schur complement of block D of the Matrix M and is defines as

$$ (M/D) = A - BD^{-1}C $$

also $$ (M/A) = D - BA^{-1}C $$

If $A$ or $D$ are singular, the matrice $M$ is singular and a pseudo inverse might be used.

This can give a reduction from inverting a $200,000 \times 200,000$ matrice to inverting 4 $50,000 \times 50,000$ matrices and some matrice multiplication, also this can be implement in parallel applications and there is way to do this recursively given certain conditions (enabling a reduction greater than 4 in size)

The $50,000 \times 50,000$ matrices store is only 9.3 GB each and will be easier to invert

Hope it helps. Also you might want to search answers in Math Stack or in Stack Overflow and even ask there.

Edit: Added another solution with Schur Complement

| improve this answer | |
$\endgroup$
  • $\begingroup$ The first solution also works for matrix multiplication, i.e. finding $A^{-1}B$ without the knowledge of $A^{-1}$ $\endgroup$ – Pedro Henrique Monforte Mar 26 '19 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.