Results 1 to 4 of 4

Math Help - Inverse of a large matrix

  1. #1
    Newbie
    Joined
    Aug 2007
    Posts
    6

    Inverse of a large matrix

    I have a symmetric positive definite matrix of size 50 000 \times 50 000, that is about 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by hapap View Post
    I have a symmetric positive definite matrix of size 50 000 \times 50 000, that is about 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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2007
    Posts
    6
    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 \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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2007
    Posts
    6

    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 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);
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Finding the inverse of a matrix using it's elementary matrix?
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 7th 2011, 07:08 PM
  2. [SOLVED] Derivative of a matrix inverse and matrix determinant
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 24th 2011, 09:18 AM
  3. Replies: 2
    Last Post: September 24th 2010, 12:43 PM
  4. Replies: 3
    Last Post: March 1st 2010, 07:22 AM
  5. trave of a large inverse Matrix
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 30th 2008, 07:46 PM

Search Tags


/mathhelpforum @mathhelpforum