Cómo calcular la inversa de la suma de un producto de Kronecker y una matriz diagonal

Question

Quiero calcular la inversa de una matriz de la forma $S = (A\otimes B+C)$ donde $A$ $B$ son simétricos y invertible, $C$ es una matriz diagonal con elementos positivos. Básicamente, si la dimensión es alta, el cálculo directo puede ser costoso. Así que me pregunto si es posible para acelerar el cálculo de tomar ventaja de algunas estructuras algebraicas?

Por ejemplo, supongamos $A$ $m\times m$ matriz y $B$ $n\times n$ matriz, entonces tenemos $(A\otimes B)^{-1}=A^{-1}\otimes B^{-1}$, de modo que el costo aproximado en operaciones de punto flotante (flops) puede ser reducido de $7m^3n^3/3$$7(m^3+n^3)/3+m^2n^2$.

Debido a que la matriz $S$ también tiene alguna estructura especial, cualquier idea sobre el cálculo eficiente de $S^{-1}$?

Muchas gracias!

• Además, ¿qué acerca de la $S^{-1}a$ donde $a$ $mn\times 1$ vector.

Answer 1

Bien, sabemos que:

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

(e $(\mathbf{A} \otimes \mathbf{B})$ es invertible $\iff$ $\mathbf{A}$ y $\mathbf{B}$ son invertible). Así que cuida de su primer mandato.

$\mathbf{C}$ es invertible con inversa igual a la diagonal de la matriz diagonal con elementos formado por el elemento sabio recíproca de las entradas de la diagonal de a $\mathbf{C}$.

Nosotros también sabemos que si $\mathbf{C}$ 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},$$

donde $\mathbf{D}=\mathbf{A} \otimes \mathbf{B}$. A continuación, utilice el hecho de que:

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

Conectando en la fórmula anterior se obtiene:

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

moviendo las cosas:

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

donde $\mathbf{I}$ es la matriz identidad de tamaño igual a $\mathbf{D}$.

Ahora, dada la descomposición espectral de $\mathbf{D}^{-1}\mathbf{C}$, $\left(\mathbf{I}+\mathbf{D}^{-1}\mathbf{C}\right)^{-1}$ es fácil de calcular, debido a la descomposición espectral de $\mathbf{I}+\mathbf{D}^{-1}\mathbf{C}$ está relacionado con el de la $\mathbf{D}^{-1}\mathbf{C}$ (el vector propio de la suma de los dos términos son los mismos que el autovector del segundo término y los eigen-valor de la suma es igual a la suma de los autovalores de los dos términos).

Debido al hecho de que $\mathbf{C}$ es diagonal, la descomposición espectral de $\mathbf{D}^{-1}\mathbf{C}$ sí es fácil de obtener a partir de la de $\mathbf{D}^{-1}$.

Ahora, usted todavía tiene que calcular la descomposición espectral de $\mathbf{D}$ pero creo que el hecho de que $\mathbf{D}$ es el producto de dos matrices de Kronecker ayuda mucho aquí.