Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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)$?

share|improve this question
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.