Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e.

$(A_1+A_2)^{-1},(A_1+A_3)^{-1},(A_2+A_3)^{-1},(A_1+A_2+A_3)^{-1}$

My main limitation is memory, i.e. I don't want to store the $2^c$ inverses, but find a way given a limited number of inverses to be able to compute the inverse I want from those I stored.

To go a bit farther, the matrices will be continuously updated using rank-one updates. Thus I would like to compute the rank-one updates of a limited subset of these $2^c$ inverses and be able to compute the inverse I want in $O(n^2)$.

share|improve this question
    
Could you clarify a bit? Do you really need to compute all the $2^c$ inverses? Is that exponential time acceptable, because later you say that "...to compute the inverse from those stored.."---because it seems better to really just compute the desired inverse directly. –  Suvrit Sep 1 '13 at 2:42
    
I will access them all multiple times and dont mind paying $O(n^2)$ each time I need an inverse. My main problem is I dont have the RAM to store all $2^c$ inverses. –  Leo Sep 1 '13 at 11:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.