Matrices – Finding the Inverse of the Sum of Two Symmetric Matrices

inversematrices

Consider calculating the inverse of matrix sum

$$A+B$$

where A is a symmetric dense matrix while B is a symmetric block diagonal matrix. I am interested in finding an efficient approach to update the inverse of the sum A+B if the values in one of the diagonal blocks of matrix B are multiplied by a real value s.

So my question is equivalent to updating the inverse of

$$A+B*K$$

where A and B are defined as above, and K is a diagonal matrix with some diagonal entries (corresponding to one block of B) being s while rest being 1. Is there a possible way for efficient iterative update of matrix inverse (A + B * K)^-1 when s is changing?

Thanks.

Best Answer

I think that this depends on the rank of the changed diagonal block in $B$.

The only thing that comes to mind is Sherman–Morrison formula, but this would require $r$ updates for if the rank of the block in question was $r$.

Also, to find the vectors $u$ and $v$ for each of these updates, one would probably also need an SVD, or - given that this is symmetric - the Eigenvalue decomposition of that diagonal block.

There may be better methods, more specific to what you want, but I'm not familiar with them.

Related Solutions

[Math] Sum of elements of inverse matrix

Let $\vec{1}$ denote the vector all of whose entries are $1$. Use Gaussian elimination (or, better, a fast matrix library with Gaussian elimination already implemented for you) to solve $$A \vec{v} = \vec{1}.$$ Then the dot product $\vec{1} \cdot \vec{v}$ will equal $\vec{1}^T A^{-1} \vec{1}$, which is what you want. A fast implementation of Gaussian elimination should beat a fast implementation of matrix inverse.

[Math] Efficient computation of Cholesky decomposition during tridiagonal matrix inverse

Here is my matlab code

     function[L]=MyChol(A)

     [n,m]=size(A);
     L=eye(n);
     for k=1:n-1
           L(k,k)=sqrt(A(k,k));
           L(k+1:n,k)=(A(k+1:n,k))/L(k,k);
           A(k+1:n,k+1:n)=A(k+1:n,k+1:n)-L(k+1:n,k)*L(k+1:n,k)';
     end
     L(n,n)=sqrt(A(n,n));
     end

$A=LL^T$

Best Answer

Related Solutions

[Math] Sum of elements of inverse matrix

[Math] Efficient computation of Cholesky decomposition during tridiagonal matrix inverse

Related Question