I have to find the diagonal of the pseudoinverse of a Laplacian matrix evaluated on a directed and weighted graph. My Laplacian is defined as $L=D-A$, where $D$ is a diagonal matrix (with $D_{i,i}$ being the sum of the weights of in or out edges from node $i$) and $A$ is the adjacency matrix where $A_{i,j} = \operatorname{weight}(i,j)$.
My Laplacian is quite big, about $20$k * $20$k and hence its pseudoinversion requires about $10$ hours with the Python scipy.pinv$2$ command and a lot of RAM, over $15$ GB.
I need only the diagonal entries of this matrix. Is there any mathematical rule that I can use in order to avoid the evaluation of the entire pseudoinverse? Is there any faster method than using the whole pseudoinverse method? I need to have best performance possible (both memory and speed.)
Thank you.
First note that the obvious approach -- inverting $L$ using a sparse direct method like sparse QR (found in the excellent SuiteSparse package, for instance) -- should take on the order of seconds for a matrix of this size, not 10 hours.
If performance is critical, it seems that the topic of numerically extracting the diagonal of the inverse of a matrix is well-studied; I found these slides for instance (http://www-users.cs.umn.edu/~saad/PDF/Sparse_days_06_15_2010.pdf) with an overview of possible approaches and references.