Evaluating the Potential of a Dual Randomized Kaczmarz Solver for Laplacian Linear Systems

Kevin Deweese, John Gilbert, Erik Boman


A new method for solving Laplacian linear systems proposed by Kelner et al. involves the random sampling and update of fundamental cycles in a graph. Kelner et al. proved asymptotic bounds on the complexity of this method but did not report experimental results. We seek to both evaluate the performance of this approach and to explore improvements to it in practice. We compare the performance of this method to other Laplacian solvers on a variety of real world graphs. We consider different ways to improve the performance of this method by exploring different ways of choosing the set of cycles and the sequence of updates, with the goal of providing more flexibility and potential parallelism. We propose a parallel
model of the Kelner et al. method, for evaluating potential parallelism in terms of the span of edges updated at each iteration. We provide experimental results comparing the potential parallelism of the fundamental cycle basis and our extended cycle set. Our preliminary experiments show that choosing a non-fundamental set of cycles can save significant work compared to a fundamental cycle basis.

Full Text:



I. Abraham and O. Neiman. Using petal-decompositions to build a low stretch spanning tree. In Proceedings of the 45th annual ACM Symp. on Theory of Comp., pages 395–406. ACM, 2012.

R. Agaev and P. Chebotarev. On the spectra of nonsymmetric Laplacian matrices. Linear Algebra and its Applications, 399:157–168, 2005.

N. Alon, R. M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78–100, 1995.

M. Bern, J. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo. Support-graph preconditioners. SIAM Journal Matrix Anal. Appl., 27(4):930–951, 2006.

E. G. Boman, D. Chen, B. Hendrickson, and S. Toledo. Maximum-weight-basis preconditioners. Numerical Linear Algebra Appl., 11:695–721, 2004.

E. G. Boman, B. Hendrickson, and S. Vavasis. Solving elliptic finite element systems in near-linear time with support preconditioners. SIAM Journal on Numerical Anal., 46(6):3264–3284, 2008.

D. Chen and S. Toledo. Vaidya’s preconditioners: Implementation and experimental study. ETNA. Electronic Transactions on Numerical Analysis [electronic only], 16:30–49, 2003.

P. Christiano, J. A. Kelner, A. Madry, D. A. Spielman, and S. H. Teng. Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the 43rd ACM Symp. Theory

of Comp. (STOC ’11), pages 273–282. ACM, 2011.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, pages 779–784. MIT Press and McGraw-Hill, 2009.

T. A. Davis and Y. Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38(1):1:1–1:25, Nov. 2011.

R. Diestel. Graph Theory, volume 173, pages 23–28. Springer, 2012.

L. Grady. Random walks for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(11):1768–1783, 2006.

K. Gremban. Combinatorial Preconditioners for Sparse, Symmetric, Diagonally Dominant Linear Systems. PhD thesis, Carnegie Mellon University, Pittsburgh, October 1996.

D. Hoske, D. Lukarski, H. Meyerhenke, and M. Wegner. Is nearly-linear the same in theory and practice? A case study with a combinatorial Laplacian solver. Computing Research Repository, abs/1502.07888, 2015.

S. Kaczmarz. Angenäherte auflösung vonsystemen linearer gleichungen. Bulletin International de l’Academie Polonaise des Sciences et des Lettres, 35:355–357, 1937.

J. A. Kelner, L. Orecchia, A. Sidford, and Z. A. Zhu. A simple, combinatorial algorithm for solving SDD systems in nearly-linear time. In Proceedings of the 45th ACM Symp. Theory of Comp. (STOC ’13), pages 911–920, New York, 2013.12

T. G. Kolda, A. Pinar, T. Plantenga, and C. Seshadhri. A scalable generative graph model with community structure. SIAM Journal on Scientific Comp., 36(5):C424–C452, 2014.

I. Koutis, G. L. Miller, and R. Peng. Approaching optimality for solving SDD systems. Computing Research Repository, abs/1003.2958, 2010.

I. Koutis, G. L. Miller, and D. Tolliver. Combinatorial preconditioners and multi-level solvers for problems in computer vision and image processing. Computer Vision and Image Understanding, 115(12):1638 – 1646, 2011.

O. E. Livne and A. Brandt. Lean algebraic multigrid (LAMG): Fast graph Laplacian linear solver. SIAM Journal on Scientific Comp., 34(4):B499–B522, 2012.

J. McCann and N. S. Pollard. Real-time gradient-domain painting. ACM Transactions on Graphics, 27(3):93, 2008.

P. A. Papp. Low-stretch spanning trees. Undergraduate thesis, Eötvös Loránd University, 2014.

D. A. Spielman. Algorithms, graph theory, and linear equations in Laplacian matrices. In Proceedings of the International Congress of Mathematicians, volume 4, pages 2698–2722, 2010.

D. A. Spielman and S. Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symp. on Theory of Comp., STOC ’04, pages 81–90, New York, NY, USA, 2004. ACM.

T. Strohmer and R. Vershynin. A randomized Kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications, 15(2):262–278, 2009.

Z. A. Zhu, S. Lattanzi, and V. S. Mirrokni. A local algorithm for finding well-connected clusters. Computing Research Repository, abs/1304.8132, 2013.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.