# Fast calculation of commute distances on large graphs (i.e. fast computation of the pseudo-inverse of a large Laplacian / Kirchhoff matrix)

I have a large, locally connected and undirected graph $G$ with $\approx 10^4$ vertices and $\approx 10^5$ to $\approx 10^6$ edges. Moreover I can bound the maximum vertex degree as $Q_{max}$. I would like to obtain all pairwise commute times between vertices in two sets $(v_{(a,1)}, ..., v_{(a,M)}) \in V_a$ and $(v_{(b,1)}, ..., v_{(b,N)}) \in V_b$ where $N >> M$, and do this without simulation of the underlying Markov process. To do this I need to compute the Laplacian matrix of $G$ (which is apparently computed using KirchhoffMatrix[G] in Mathematica, and takes about $\approx 50$ milliseconds on an X5690 3.47 GHz Intel Xeon processor), and then to compute its pseudoinverse, which I believe is an $O(n^3)$ operation.

My question is - does Mathematica have a nice way of computing the pseudoinverse for a large Laplacian matrix, allowing me to efficiently extract commute times between pairs of vertices? How large can $G$ be?

Update - Following from Szabolcs comments, can anyone confirm that the time complexity of PseudoInverse[] is $O(n^3)$?

-
This is bound to be slow because while your starting matrix is sparse, the inverse is going to be dense. You can calculate the pseudoinverse using PseudoInverse. –  Szabolcs Apr 23 '13 at 23:11
The same as what exactly? It sounds like you are not sure what pseudoinverse means in the context of your problem. This would be a math question, not a Mathematica one. Once you know precisely what you want to calculate, we can look at how to do it in Mathematica. –  Szabolcs Apr 23 '13 at 23:17
@Szabolcs You wrote that I should use SingularValueDecomposition[] instead of PseudoInverse[] originally. I was just curious why you recommended that. –  Peter Apr 23 '13 at 23:20
Sorry about the confusion. When I saw your message it was already corrected. If Mathematica didn't have PseudoInverse built in, you could implement it using SingularValueDecomposition. –  Szabolcs Apr 23 '13 at 23:21
@Szabolcs Sorry about that - my browser isn't updating quickly because PseudoInverse is apparently automatically running on all the available cores and slowing everything down. Right, your comments all make sense now, thanks! –  Peter Apr 23 '13 at 23:22