Jump to content
  • Advertisement
Sign in to follow this  
shaobohou

fast matrix inverse

This topic is 4358 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

if I have a symmetric matrix A and a diagonal matrix B, is there a fast way of computing the inverse of A+B using the inverse of A and the inverse of B?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by ury
You might find Woodbury's formula useful.
Please note that it'll only help you if A = UUT, where U is a NxM matrix with M << N.


Hmm, not sure a diagonal matrix can be decomposed into the necessary format

Share this post


Link to post
Share on other sites
In your original post, A is the symmetric matrix.
To avoid any further confusion, can you tell me more about your problem and the kind of matrices that you have.

Woodbury's formula is useful in the following case.
Let's say that you have a matrix A and you already know its inverse matrix.
Now, if you want to update A by adding another matrix B, such that B has a small rank, the inverse of A+B can be computed by the Woodbury's formula.

After reading your original post once again, I noticed that both your A and B are invertible. This means that they have a full rank. If this is really the case, Woodbury's formula is useless.

Share this post


Link to post
Share on other sites
Quote:
Original post by ury
After reading your original post once again, I noticed that both your A and B are invertible. This means that they have a full rank. If this is really the case, Woodbury's formula is useless.


Yes, unfortunately, both A and B have full rank and B is diagonal. Thanks anyway

Share this post


Link to post
Share on other sites
Maybe I wasn't paying attention, but why has everybody abandoned Woodbury's formula all of a sudden?

Quote:
Original post by shaobohou
Quote:
Original post by ury
You might find Woodbury's formula useful.
Please note that it'll only help you if A = UUT, where U is a NxM matrix with M << N.


Hmm, not sure a diagonal matrix can be decomposed into the necessary format

It can over the complex numbers, or even over the reals if B is a positive diagonal matrix. If B = diag(a1, a2, ..., an) then let U = diag(√a1, √a2, ..., √an). As U is also diagonal, it is symmetric and so UUT = B. So Woodbury's formula will apply.
I'm not convinced, though, that application of Woodbury's formula would save you computational time for any reasonably-size matrices.

Matrix sums aren't too friendly with inversion, so I'm afraid I have no suggestions to add.

Regards
Admiral

Share this post


Link to post
Share on other sites
TheAdmiral: your matrix U does not give a solution to UUT=B.

It could be that a general method can be used, say, if AB-1 or BA-1 has a spectral radius or even operator norm under 1?

Share this post


Link to post
Share on other sites
some considerations:

1. A+B is a symmetric matrix itself...therefore, inverting that matrix by method of cofactors (adjoint matrix) can be optimized considering you only have to compute a little more than half the elements.

2. If you can diagonalize A+B, then the diagonalization will break A+B into an orthonormal matrix, times a diagonal matrix, times the transpose of the orthogonal matrix. then, it is elementary to invert the matrix by inverting each element of the diagonal matrix and taking the transpose of each orthonormal matrix.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!