Nick,I forgot to ask you. in the initial email, your friend had read about this blog entry (http://nuit-blanche.blogspot.fr/2013/03/nuit-blanche-readers-reviews-spash-r.html ) where I noted:On Andrew Davison's feed, Andrew talks about a new paper solving graph laplacians, I noted that a new algorithm for computing graph laplacians was shown to be a randomized instance of the Kaczmarz algorithm (see section 9, A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time by Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu)How does your approach compare to the algorithm of Kelner et al if it is at all comparable ?Cheers,Igor.
Nick Freris kindly responded:
Dear Igor,....The original title of our journal paper was meant to be: "Randomized Kaczmarz for Laplacian systems," so indeed our work is very related. We leverage the special structure of Laplacian to design fast distributed (parallelizable) algorithms for estimation based on measuring differences across edges. I am also copying my co-author, Tasos Zouzias in case you have any further questions about our work.Thanks once more on your interest.Regards,Nick
Then Anastasios (Tassos) added:
Dear Igor,Let me add a few comments on your question which may be helpful. Please let me know if you have any further questions.The main difference of the paper that you mentioned and ours [1,2] is on the model of computation. Kelner et al.'s algorithm works on the usual model of computation (unit-cost RAM) whereas ours works on the distributed model of computation (gossip model).First of all, I am not familiar with the work of Kelner et al. It looks very interesting and as far as I can tell their algorithm is an instantiation of the (randomized) Kaczmarz method on a *preconditioned* Laplacian system. Computing the preconditioned matrix is not a trivial task (see also Spielman Teng paper). The goal in this area is to get algorithms that work in time O(nnz(L) polylog(n)) where nnz(L) is the number of non-zero entries of the Laplacian and that are "simpler" than Spielman-Teng's solver.On the other hand, in our case the problem is to design asynchronous distributed algorithms that solve Laplacian systems. More precisely, the problem is to solve Laplacian systems in the gossip model of computation (see  for details). In [1,2], the expected number of iterations / rounds of the algorithm depends on the condition number of the Laplacian matrix (~ 1/lambda_2(G)). If you view these distributed algorithms as centralized (for comparison purposes), then the running time here is roughly O(nnz(L) kappa^2(L) ), where kappa^2(L) is the squared condition number of L (which can be arbitrarily large as opposed to Kelnel's et al paper / Spielman-Teng).We also have an implementation of the Randomized Extended Kaczmarz method underwhich we used in our paper http://arxiv.org/abs/1205.5770 . I am not familiar with the GraphLab framework, so I can not answer your second question.Best,Tassos
Thanks Nick and Tassos ! Looks like this algorithm is ripe for an implementation in the GraphLab framework. Danny just wrote a small entry on the upcoming The GraphLab Workshop and Why Should You Care?