7
$\begingroup$

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.
$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Eridk Poliruyt Mar 4 '15 at 19:55
  • 1
    $\begingroup$ Don't worry, it's not my homework.. I am reading a paper and want to extend a little bit where comes this question. $\endgroup$ – Eridk Poliruyt Mar 4 '15 at 21:27
  • $\begingroup$ Thanks! It looks promising. What about $S^{-1}a$? Can this be simplified in similar way? $\endgroup$ – Eridk Poliruyt Mar 5 '15 at 13:01
  • $\begingroup$ @EridkPoliruyt: I do not know if any simplifications are possible for $S^{-1}a$ $\endgroup$ – user603 Mar 5 '15 at 13:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.