11

I want to calculate the inverse of a matrix of the form $S = (A\otimes B+C)$, where $A$ and $B$ are symetric and invertible, $C$ is a diagonal matrix with positive elements. Basically if the dimension is high, direct calculation can be expensive. So I wonder if it is possible to speed up the calculation taking advantage of some algebraic structures?

For example, let $A$ be a $m\times m$ matrix and $B$ be a $n\times n$ matrix, then we have $(A\otimes B)^{-1}=A^{-1}\otimes B^{-1}$ so that the approximate cost in floating point operations (flops) can be reduced from $7m^3n^3/3$ to $7(m^3+n^3)/3+m^2n^2$.

Since the matrix $S$ also has some special structure, any idea on the efficient calculation of $S^{-1}$?

Many thanks!

  • In addition, what about $S^{-1}a$, where $a$ is a $mn\times 1$ vector.
Eridk Poliruyt
  • 425
  • 3
  • 9

1 Answers1

7

Well, we know that:

$$(\mathbf{A} \otimes \mathbf{B})^{-1} = \mathbf{A}^{-1} \otimes \mathbf{B}^{-1}$$

(and $(\mathbf{A} \otimes \mathbf{B})$ is invertible $\iff$ $\mathbf{A}$ and $\mathbf{B}$ are invertible as well). So that takes care of the first term.

$\mathbf{C}$ is invertible with inverse equal to the diagonal matrix with diagonal elements formed of the element-wise inverses of the diagonal entries of $\mathbf{C}$.

We also know that if $\mathbf{C}$ is diagonal:

$$\left(\mathbf{D}+\mathbf{C}\right)^{-1} = \mathbf{D}^{-1} - \mathbf{D}^{-1} \left(\mathbf{C}^{-1}+\mathbf{D}^{-1} \right)^{-1}\mathbf{D}^{-1},$$

where $\mathbf{D}=\mathbf{A} \otimes \mathbf{B}$. Next, you use the fact that:

$$\left(\mathbf{C}^{-1}+\mathbf{D}^{-1} \right)^{-1}=\mathbf{C}\left(\mathbf{C}+\mathbf{D}\right)^{-1}\mathbf{D}.$$

Plugging this in the previous formula yields:

$$\left(\mathbf{D}+\mathbf{C}\right)^{-1} = \mathbf{D}^{-1} - \mathbf{D}^{-1} \mathbf{C}\left(\mathbf{C}+\mathbf{D}\right)^{-1},$$

moving things around:

$$\left(\mathbf{D}+\mathbf{C}\right)^{-1} = \left(\mathbf{I}+\mathbf{D}^{-1}\mathbf{C}\right)^{-1}\mathbf{D}^{-1},$$

where $\mathbf{I}$ is the identity matrix of same size as $\mathbf{D}$.

Now, given the spectral decomposition of $\mathbf{D}^{-1}\mathbf{C}$, that of $\left(\mathbf{I}+\mathbf{D}^{-1}\mathbf{C}\right)^{-1}$ is easy to compute because the spectral decomposition of $\mathbf{I}+\mathbf{D}^{-1}\mathbf{C}$ is related to that of $\mathbf{D}^{-1}\mathbf{C}$ (the eigenvector of the sum of the two terms are the same as the eigenvector of the second term and the eigen-value of the sum equals the sum of the eigenvalues of the two terms).

Because of the fact that $\mathbf{C}$ is diagonal, the spectral decomposition of $\mathbf{D}^{-1}\mathbf{C}$ itself is easy to obtain from that of $\mathbf{D}^{-1}$.

Now, you still have to compute the spectral decomposition of $\mathbf{D}$ but I think that the fact that $\mathbf{D}$ is the product of two Kronecker matrices helps considerably here.

user603
  • 21,225
  • 3
  • 71
  • 135
  • 1
    Thanks! I thought this. However, we notice that in the final formula, there is the term $(C^{-1}+D^{-1})^{-1}$, which is still expensive to calculate as $C^{-1}+D^{-1}$ doesn't have special structure? – Eridk Poliruyt Mar 04 '15 at 19:55
  • 1
    Don't worry, it's not my homework.. I am reading a paper and want to extend a little bit where comes this question. – Eridk Poliruyt Mar 04 '15 at 21:27
  • Thanks! It looks promising. What about $S^{-1}a$? Can this be simplified in similar way? – Eridk Poliruyt Mar 05 '15 at 13:01
  • @EridkPoliruyt: I do not know if any simplifications are possible for $S^{-1}a$ – user603 Mar 05 '15 at 13:33
  • @user603 Could you please explain how to compute the spectral decomposition of $D^{-1}C$ from that of $D^{-1}$? – shani Dec 23 '21 at 04:59
  • @shani: because C is diag, the eigen-vectors of D^{-1}C are the same (up to a re-ordering) as those of D^{-1}. The eigenvalue of D^{-1}C are the product of C with the eigen-values of D^{-1}. – user603 Dec 23 '21 at 09:44
  • @user603 that would be true for scalar matrix, but I don't see how this is true for arbitrary diagonal $C$. – mihaild Dec 23 '21 at 11:43
  • @user603 This statement is incorrect. As an example, let $D$ and $C$ be such that $$ D^{-1} = \pmatrix{2&1\\1&2}, \quad C = \pmatrix{1&0\\0&2}. $$ The eigenvectors of $D^{-1}$ are $(\pm 1, 1)$. The eigenvectors of $D^{-1}C$ are $(-1 \pm \sqrt{3},1)$. – Ben Grossmann Dec 23 '21 at 21:03
  • By the way, the corresponding choice of $D$ is $$ D = \frac 13 \pmatrix{2&-1\\-1&2}. $$ As a simpler example, you could also repeat the above with $$ D = \pmatrix{0&1\\1&0}, $$ for which we find that $D^{-1} = D$. – Ben Grossmann Dec 23 '21 at 21:04
  • you right, let me think about it a bit, – user603 Dec 23 '21 at 22:11