Calcule la diagonal principal de $(K + D)^{-1}$ en menos de $O(n^3)$ operaciones

Question

Calcule la diagonal principal de $(K + D)^{-1}$ en menos de $O(n^3)$ operaciones dadas de matrices de rango completo, densas y simétricas $K$ y $K^{-1}$ y una matriz diagonal $D$ con elementos positivos en su diagonal principal.

Lo he intentado durante un mes y no consigo realizar esta operación en menos de $O(n^3)$ . También me alegraría conocer una prueba o una indicación clara de que es realmente imposible.

Nota: Supongo que estamos utilizando $O(n^3)$ para las operaciones de productos matriciales.

Answer 1

Su pregunta no es ni mucho menos nueva. Está claro que si $D$ no es pequeño frente a $K$ entonces el conocimiento de $K^{-1}$ no añade nada. Si $K+D$ es disperso, entonces existe un método reciente para resolver aproximadamente el problema; sin embargo, aquí no es el caso.

Supongamos que $||K^{-1}D||<<1$ . Entonces podemos obtener una aproximación de la diagonal de $(K+D)^{-1}$ en $O(n^2)$ .

Prueba. No es difícil ver que $(K+D)^{-1}=(I+K^{-1}D)^{-1}K^{-1}=K^{-1}-K^{-1}DK^{-1}+O(||K^{-1}D||^2)K^{-1}$ . La diagonal de $K^{-1}DK^{-1}$ se puede calcular en $O(n²)$ .

Answer 2

Cálculo de la inversa de un $n \times n$ matriz se puede hacer más rápido que el tiempo cúbico (es decir $o(n^3)$ ). Ver esto enlace de wikipedia por ejemplo. Por lo tanto, se podría calcular la inversa directamente.