Let $A$ be a real symmetric positive-definite matrix, with known inverse $A^{-1}$. Is there an efficient algorithm to compute $(A+R)^{-1}$, where $R$ is a real diagonal matrix? Assume that $A+R$ is also positive-definite.

Failed idea with Cholesky decomposition

I have read about the Cholesky decomposition and how it can be updated efficiently when the matrix changes by a rank-one modification. Since adding $R$ is the same as many rank-one modifications (one for each entry in the diagonal), in principle I could use this algoritm to compute the updated Cholesky decomposition. However this turns out to be $O(n^3)$ (where $n$ is the dimension of the matrices), no better than matrix inversion, because each rank-one update of the Cholesky decomposition is $O(n^2)$, and there are $n$ entries in the diagonal.


This is closely related to Efficient diagonal update of matrix inverse. However in that question, the diagonal update is homogeneous. Here the diagonal entries $R_{nn}$ are in principle distinct for each $n$.


Your Answer

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

Browse other questions tagged or ask your own question.