diagonal de la pseudoinversión de la matriz lapona

Question

Tengo que encontrar la diagonal del pseudoinverso de una matriz Laplaciana evaluada en un gráfico dirigido y ponderado. Mi laplaciano se define como $L=D-A$ donde $D$ es una matriz diagonal (con $D_{i,i}$ siendo la suma de los pesos de los bordes de entrada o salida del nodo $i$ ) y $A$ es la matriz de adyacencia donde $A_{i,j} = \operatorname {weight}(i,j)$ .

Mi Laplaciano es bastante grande, alrededor de $20$ k * $20$ k y por lo tanto su pseudoinversión requiere alrededor de $10$ horas con el Python scipy.pinv $2$ y un montón de RAM, sobre $15$ GB.

Sólo necesito las entradas diagonales de esta matriz. ¿Hay alguna regla matemática que pueda usar para evitar la evaluación de todo el pseudoinverso? ¿Hay algún método más rápido que usar el método del pseudoinverso completo? Necesito tener el mejor rendimiento posible (tanto de memoria como de velocidad.)

Gracias.

Answer 1

Primero note que el enfoque obvio invertir $L$ usando un escasos método directo como el QR disperso (que se encuentra en el excelente paquete SuiteSparse, por ejemplo) - debería tomar el orden de los segundos para una matriz de este tamaño, no 10 horas.

Si el rendimiento es crítico, parece que el tema de la extracción numérica de la diagonal del inverso de una matriz está bien estudiado; encontré estas diapositivas por ejemplo ( http://www-users.cs.umn.edu/~saad/PDF/Sparse_days_06_15_2010.pdf ) con una visión general de los posibles enfoques y referencias.