Accelerated multigrid for graph Laplacian operators. (English) Zbl 1410.65099
Summary: We consider multigrid type techniques for the numerical solution of large linear systems, whose coefficient matrices show the structure of (weighted) graph Laplacian operators. We combine ad hoc coarser-grid operators with iterative techniques used as smoothers. Empirical tests suggest that the most effective smoothers have to be of Krylov type with subgraph preconditioners, while the projectors, which define the coarser-grid operators, have to be designed for maintaining as much as possible the graph structure of the projected matrix at the inner levels. The main theoretical contribution of the paper is the characterization of necessary and sufficient conditions for preserving the graph structure. In this framework it is possible to explain why the classical projectors inherited from differential equations are good in the differential context and why they may behave unsatisfactorily for unstructured graphs. Furthermore, we report and discuss several numerical experiments, showing that our approach is effective even in very difficult cases where the known approaches are rather slow. As a conclusion, the main advantage of the proposed approach is the robustness, since our multigrid type technique behaves uniformly well in all cases, without requiring either the setting or the knowledge of critical parameters, as it happens when using the best known preconditioned Krylov methods.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A12 | Conditioning of matrices |
References:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin., J. B., Network flows: theory, Algorithms and Applications (1993), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 1201.90001 |
| [2] | Aricó, A.; Donatelli, M.; Serra-Capizzano, S., V-cycle optimal convergence for certain (multilevel) structured linear systems, SIAM J. Matrix Anal. Appl., 26, 1, 186-214 (2004) · Zbl 1105.65322 |
| [3] | Axelsson, O.; Neytcheva, M., The algebraic multilevel iteration methods - theory and applications, (Bainov, D., Proceedings of the 2nd International Colloquium on Numerical Analysis, Plovdiv, Bulgaria (1993)), 13-23 · Zbl 0845.65012 |
| [4] | Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D., Linear Programming and Network Flows (1990), Wiley: Wiley New York, NY · Zbl 0722.90042 |
| [5] | Bhatia, R., Matrix Analysis (1997), Springer Verlag: Springer Verlag New York |
| [6] | Bern, M.; Gilbert, J.; Hendrickson, B.; Nuygen, N.; Toledo, S., Support-graph preconditioners, SIAM J. Matrix Anal. Appl., 27, 4, 930-951 (2006) · Zbl 1106.65040 |
| [7] | Bocanegra, S.; Castro, J.; Oliveira, A. R.L., Improving an interior-point approach for large block-angular problems by hybrid preconditioners, Eur. J. Oper. Res., 231, 263-273 (2013) · Zbl 1317.90195 |
| [8] | Boman, E. G.; Chen, D.; Hendrickson, B.; Toledo, S., Maximum-weight-basis preconditioners, Numer. Linear Algebra Appl., 11, 8-9, 695-721 (2004) · Zbl 1164.65393 |
| [9] | Boman, E. G.; Hendrickson, B., Support theory for preconditioning, SIAM J. Matrix Anal. Appl., 25, 3, 694-717 (2003) · Zbl 1063.65033 |
| [10] | Brezina, M.; Falgout, R. D.; MacLachlan, S.; Manteuffel, T. A.; McCormick, S. F.; Ruge, J., Adaptive smoothed aggregation (SA) multigrid, SIAM Rev., 47, 2, 317-346 (2005) · Zbl 1075.65042 |
| [11] | Brezina, M.; Falgout, R. D.; MacLachlan, S.; Manteuffel, T. A.; McCormick, S. F.; Ruge, J., Adaptive algebraic multigrid, SIAM J. Sci. Comput., 27, 4, 1261-1286 (2006) · Zbl 1100.65025 |
| [12] | Briggs, W. L.; Henson, V. E.; McCormick, S. F., A Multigrid Tutorial second ed., SIAM (2000) · Zbl 0958.65128 |
| [13] | Castro, J., A specialized interior-point algorithm for multicommodity network flows, SIAM J. Opt., 10, 852-877 (2000) · Zbl 0955.90087 |
| [14] | Castro, J.; Frangioni, A., A parallel implementation of an interior-point algorithm for multicommodity network flows, (Palma, J.; Dongarra, J.; Hernandez, V., Vector and Parallel Processing - VECPAR 2000. Vector and Parallel Processing - VECPAR 2000, Lecture Notes in Computer Science, vol. 1981 (2001), Springer-Verlag), 301-315 · Zbl 1044.90526 |
| [15] | Castro, J.; Cuesta, J., Quadratic regularizations in an interior-point method for primal block-angular problems, Math. Program., 130, 415-445 (2011) · Zbl 1229.90086 |
| [16] | Castro, J.; Cuesta, J., Improving an interior-point algorithm for multicommodity flows by quadratic regularizations, Networks, 5, 117-131 (2012) · Zbl 1245.90081 |
| [17] | Cayley, A., A theorem on trees, Q. J. Math., 23, 376-378 (1889) · JFM 21.0687.01 |
| [18] | Cherubini, D.; Fanni, A.; Frangioni, A.; Mereu, A.; Murgia, C.; Scutellà, M. G.; Zuddas, P., A linear programming model for traffic engineering in 100 · Zbl 1215.90018 |
| [19] | Cvetkovic, D.; Doob, M.; Sachs, H., Spectra of Graphs (1979), Academic Press: Academic Press New York |
| [20] | De Sterck, H.; Manteuffel, T. A.; McCormick, S. F.; Nguyen, Q.; Ruge, J., Multilevel adaptive aggregation for Markov chains, with application to web ranking, SIAM J. Sci. Comput., 30, 5, 2235-2262 (2008) · Zbl 1173.65028 |
| [21] | De Sterck, H.; Manteuffel, T. A.; McCormick, S. F.; Miller, K.; Pearson, J.; Ruge, J.; Sanders, G., Smoothed aggregation multigrid for Markov chains, SIAM J. Sci. Comput., 32, 1, 40-61 (2010) · Zbl 1209.65011 |
| [22] | De Sterck, H.; Manteuffel, T. A.; McCormick, S. F.; Miller, K.; Ruge, J.; Sanders, G., Algebraic multigrid for Markov chains, SIAM J. Sci. Comput., 32, 2, 544-562 (2010) · Zbl 1210.65016 |
| [23] | De Sterck, H.; Manteuffel, T. A.; Miller, K.; Sanders, G., Top-level acceleration of adaptive algebraic multilevel methods for steady-state solution to Markov chains, Adv. Comput. Math., 35, 375-403 (2010) · Zbl 1230.65013 |
| [24] | De Sterck, H.; Miller, K.; Sanders, G.; Winlaw, M., Recursively accelerated multilevel aggregation for Markov chains, SIAM J. Sci. Comput., 32, 3, 1652-1671 (2010) · Zbl 1213.65018 |
| [25] | Corso, G. D.; Gullí, A.; Romani, F., Fast PageRank computation via a sparse linear system, Internet Math., 3, 2, 259-281 (2005) |
| [26] | Dell’Acqua, P.; Frangioni, A.; Serra-Capizzano, S., Computational evaluation of multi-iterative approaches for solving graph-structured large linear systems, Calcolo, 22 (2015) · Zbl 1329.65069 |
| [27] | Donatelli, M., An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices, Numer. Linear Algebra Appl., 17, 179-197 (2010) · Zbl 1240.65353 |
| [28] | Donatelli, M.; Garoni, C.; Manni, C.; Serra-Capizzano, S.; Speleers, H., Robust and optimal multi-iterative techniques for IgA Galerkin linear systems, Comput. Methods Appl. Mech. Eng. (2014) |
| [29] | Donatelli, M.; Semplice, M.; Serra-Capizzano, S., Analysis of multigrid preconditioning for implicit PDE solvers for degenerate parabolic equations, SIAM J. Matrix Anal. Appl., 32, 4, 1125-1148 (2011) · Zbl 1242.65198 |
| [30] | Frangioni, A.; Gallo, G., A bundle type dual-ascent approach to linear multicommodity Min Cost Flow problems, INFORMS J. Comput., 11, 370-393 (1999) · Zbl 1034.90534 |
| [31] | Frangioni, A.; Gendron, B., 0-1 reformulations of the multicommodity capacitated network design problem, Discrete Appl. Math., 157, 1229-1241 (2009) · Zbl 1168.90002 |
| [32] | Frangioni, A.; Gentile, C., New preconditioners for KKT systems of network flow problems, SIAM J. Opt., 14, 894-913 (2004) · Zbl 1073.90064 |
| [33] | Frangioni, A.; Gentile, C., Prim-based BCT preconditioners for Min-Cost Flow problems, Comput. Opt. Appl., 36, 271-287 (2007) · Zbl 1148.90304 |
| [34] | Frangioni, A.; Manca, A., A computational study of cost reoptimization for Min Cost Flow problems, INFORMS J. Comput., 18, 1, 61-70 (2006) · Zbl 1241.90158 |
| [35] | Frangioni, A.; Serra-Capizzano, S., Spectral analysis of (sequences of) graph matrices, SIAM J. Matrix Anal. Appl., 23, 2, 339-348 (2001) · Zbl 1004.05041 |
| [36] | Golub, G. H.; Loan, C. F.V., Matrix Computations (1983), North Oxford Academic · Zbl 0559.65011 |
| [37] | Gremban, K., Combinatorial preconditioners for sparse, symmetric, diagonally dominant linear systems (Ph.D. thesis), Carnegie Mellon University (1996) |
| [38] | Greenbaum, A., Analysis of a multigrid method as an iterative technique for solving linear systems, SIAM J. Numer. Anal., 21, 3, 473-485 (1984) · Zbl 0539.65011 |
| [39] | Horn, R.; Serra-Capizzano, S., A general setting for the parametric Google matrix, Internet Math., 3, 4, 385-411 (2008) · Zbl 1146.65315 |
| [40] | Keller, H. B., Numerical Methods for Two-Points Boundary-Value Problems (1968), Blaisdell: Blaisdell London · Zbl 0172.19503 |
| [41] | Kirchhoff, G., Uber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys., 148, 12, 497-508 (1847) |
| [42] | Koutis, I., Combinatorial and algebraic algorithms for optimal multilevel algorithms (Ph.D. thesis), Carnegie Mellon University (2007) |
| [43] | Koutis, I.; Miller, G. L., Graph partitioning into isolated, high conductance clusters: theory, computation and applications to preconditioning, Symposium on Parallel Algorithms and Architectures (SPAA) (2008) |
| [44] | Koutis, I.; Miller, G. L., A linear work, \(o(n^{1/6})\) time, parallel algorithm for solving planar Laplacians, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (SODA ’07) (2007) · Zbl 1302.68308 |
| [45] | Koutis, I.; Miller, G. L.; Tolliver, D., Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing, International Symposium of Visual Computing, 1067-1078 (2009) |
| [46] | Langville, A.; Meyer, C., A survey of eigenvector methods for web information retrieval, SIAM Rev., 47, 1, 135-161 (2005) · Zbl 1075.65053 |
| [47] | Livne, O. E.; Brandt, A., Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver, SIAM J. Sci. Comput., 34, 4, 499-522 (2012) · Zbl 1253.65045 |
| [48] | Mohar, B., Some applications of Laplace eigenvalues of graphs, (Hahn, G.; Sabidussi, G., Graph Symmetry: Algebraic Methods and Applications. Graph Symmetry: Algebraic Methods and Applications, NATO ASI Series C, 497 (1997), Kluwer), 225-275 · Zbl 0883.05096 |
| [49] | Monteiro, R. D.C.; O’Neal, J. W.; Tsuchiya, T., Uniform boundedness of a preconditioned normal matrix used in interior-point methods, SIAM J. Opt., 15, 1, 96-100 (2004) · Zbl 1075.65085 |
| [50] | Ng, M.; Serra-Capizzano, S.; Tablino-Possio, C., Multigrid preconditioners for symmetric Sinc systems, ANZIAM J., 45, E, 857-869 (2004) · Zbl 1063.65585 |
| [51] | Noutsos, D.; Serra-Capizzano, S.; Vassalos, P., The conditioning of FD matrix sequences coming from semi-elliptic differential equations, Linear Algebra Appl., 428, 2/3, 600-624 (2008) · Zbl 1137.65050 |
| [52] | Notay, Y., An aggregation-based algebraic multigrid method, Electron. Trans. Numer. Anal., 37, 123-146 (2010) · Zbl 1206.65133 |
| [53] | Olfati-Saber, R.; Murray, R. M., Consensus problems in networks of agents with switching topology and time-delays, IEEE Trans. Autom. Control, 49, 9, 1520-1533 (2004) · Zbl 1365.93301 |
| [54] | Portugal, L. F.; Resende, M. G.C.; Veiga, G.; Jùdice, J. J., A truncated primal-infeasible dual-feasible network interior point method, Networks, 35, 91-108 (2000) · Zbl 0957.90022 |
| [55] | Ruge, J. W.; Stüben, K., Algebraic multigrid, Multigrid Methods. Multigrid Methods, Frontiers in Applied Mathematics, vol. 3, 73-130 (1987), SIAM: SIAM Philadelphia · Zbl 0659.65094 |
| [56] | Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS: PWS Boston · Zbl 1002.65042 |
| [57] | Serra-Capizzano, S., Multi-iterative methods, Comput. Math. Appl., 26, 4, 65-87 (1993) · Zbl 0790.65025 |
| [58] | Serra-Capizzano, S.; Tablino-Possio, C., Multigrid methods for multilevel circulant matrices, SIAM J. Sci. Comput., 26, 1, 55-85 (2004) · Zbl 1079.65033 |
| [59] | Spielman, D. A.; Teng, S. H., Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 81-90 (2004) · Zbl 1192.65048 |
| [60] | Stüben, K., A review of algebraic multigrid, J. Comput. Appl. Math., 128, 281-309 (2001) · Zbl 0979.65111 |
| [61] | Trottenberg, U.; Oosterlee, C.; Schuller, A., Multigrid (2001), Academic Press · Zbl 0976.65106 |
| [62] | Vaidya, P. M., Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners, A talk based on the manuscript was presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation Minneapolis (1991), Unpublished manuscript |
| [63] | Vanek, P.; Mandel, J.; Brezina, M., Algebraic multigrid on unstructured meshes, Center for Computational Mathematics, Mathematics Department (1994) |
| [64] | Varga, R. S., Matrix Iterative Analysis (1962), Prentice Hall: Prentice Hall Englewood Cliffs · Zbl 0133.08602 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
