Abstract
We consider the problem of designing efficient iterative methods for solving linear systems. In its full generality, this is one of the oldest problems in numerical analysis with a tremendous number of practical applications. We focus on a particular type of linear systems, associated with Laplacian matrices of undirected graphs, and study a class of iterative methods for which it is possible to speed up the convergence through combinatorial preconditioning. We consider a class of preconditioners, known as tree preconditioners, introduced by Vaidya, that have been shown to lead to asymptotic speed-up in certain cases. Rather than trying to improve the structure of the trees used in preconditioning, we propose a very simple modification to the basic tree preconditioner, which can significantly improve the performance of the iterative linear solvers in practice. We show that our modification leads to better conditioning for some special graphs, and provide extensive experimental evidence for the decrease in the complexity of the preconditioned conjugate gradient method for several graphs, including 3D meshes and complex networks.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abraham, I., Neiman, O.: Using petal-decompositions to build a low stretch spanning tree. In: Proc. STOC, pp. 395–406. ACM (2012)
Alon, N., Karp, R.M., Peleg, D., West, D.B.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24(1), 78–100 (1995)
Batson, J.D., Spielman, D.A., Srivastava, N.: Twice-ramanujan sparsifiers. SIAM Review 56(2), 315–334 (2014)
Batson, J.D., Spielman, D.A., Srivastava, N., Teng, S.: Spectral sparsification of graphs: theory and algorithms. Commun. ACM 56(8), 87–94 (2013)
Beauwens, R.: Lower eigenvalue bounds for pencils of matrices. Linear Algebra and its Applications 85, 101–119 (1987)
Bern, M.W., Gilbert, J.R., Hendrickson, B., Nguyen, N., Toledo, S.: Support-graph preconditioners. SIAM J. Matrix Analysis Applications 27(4), 930–951 (2006)
Boman, E., Hendrickson, B.: Support theory for preconditioning. SIAM Journal on Matrix Analysis and Applications 25(3), 694–717 (2003)
Castelli Aleardi, L.C., Nolin, A., Ovsjanikov, M.: Efficient and practical tree preconditioning for solving Laplacian systems (2015). Preprint https://hal.inria.fr/hal-01138603
Chen, D., Toledo, S.: Vaidya’s preconditioners: implementation and experimental study. Elect. Trans. on Numerical Analysis 16, 30–49 (2003)
Cohen, M.B., Kyng, R., Miller, G.L., Pachocki, J., Peng, R., Rao, A., Xu, S.C.: Solving SDD linear systems in nearly \(m\log ^{1/2}\)n time. STOC, pp. 343–352 (2014)
Cohen, M.B., Miller, G.L., Pachocki, J.W., Peng, R., Xu, S.C.: Stretching stretch (2014). CoRR, abs/1401.2454
Golub, G.H., Van Loan, C.F.: Matrix Computations. 4th edn (2013)
Hoske, D., Lukarski, D., Meyerhenke, H., Wegner, M.: Is nearly-linear the same in theory and practice? a case study with a combinatorial laplacian solver. In: Proc, SEA (2015)
Kolla, A., Makarychev, Y., Saberi, A., Teng, S.-H.: Subgraph sparsification and nearly optimal ultrasparsifiers. In: Proc. STOC, pp. 57–66. ACM (2010)
Koren, Y.: Drawing graphs by eigenvectors: Theory and practice. Computers and Mathematics with Applications 49, 2005 (2005)
Koutis, I., Miller, G.L., Peng, R.: A fast solver for a class of linear systems. Commun. ACM 55(10), 99–107 (2012)
Krishnan, D., Fattal, R., Szeliski, R.: Efficient preconditioning of Laplacian matrices for Computer Graphics. ACM Trans. Graph. 32(4), 142 (2013)
Poulalhon, D., Schaeffer, G.: Optimal coding and sampling of triangulations. Algorithmica 46(3–4), 505–527 (2006)
Spielman, D.A., Teng, S.: Spectral sparsification of graphs. SIAM J. Comput. 40(4), 981–1025 (2011)
Spielman, D.A., Teng, S.: A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM J. Comput. 42(1), 1–26 (2013)
Spielman, D.A., Teng, S.: Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Analysis Applications 35(3), 835–885 (2014)
Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. STOC, pp. 81–90 (2004)
Vaidya, P.M.: Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript (1991)
Vishnoi, N.K.: Lx = b. Foundations and Trends in Theoretical Computer Science 8(1–2), 1–141 (2013)
von Luxburg, U.: A tutorial on spectral clustering. Statistics and Computing 17(4), 395–416 (2007)
Acknowledgments
This work is supported by the ANR EGOS 12 JS02 002 01, a Google Faculty Research Award, the Marie Curie grant CIG-334283-HRGP, and a CNRS chaire dexcellence, Jean Marjoulet professorial chair.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Castelli Aleardi, L., Nolin, A., Ovsjanikov, M. (2015). Efficient and Practical Tree Preconditioning for Solving Laplacian Systems. In: Bampis, E. (eds) Experimental Algorithms. SEA 2015. Lecture Notes in Computer Science(), vol 9125. Springer, Cham. https://doi.org/10.1007/978-3-319-20086-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-20086-6_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-20085-9
Online ISBN: 978-3-319-20086-6
eBook Packages: Computer ScienceComputer Science (R0)