Computational evaluation of multi-iterative approaches for solving graph-structured large linear systems. (English) Zbl 1329.65069
Summary: We analyse the practical efficiency of multi-iterative techniques for the numerical solution of graph-structured large linear systems. In particular we evaluate the effectiveness of several combinations of coarser-grid operators which preserve the graph structure of the projected matrix at the inner levels and smoothers. We also discuss and evaluate some possible strategies (inverse projection and dense projection) to connect coarser-grid operators and graph-based preconditioners. Our results show that an appropriate choice of adaptive projectors and tree-based preconditioned conjugate gradient methods result in highly effective and robust approaches, that are capable to efficiently solve large-scale, difficult systems, for which the known iterative solvers alone can be rather slow.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F08 | Preconditioners for iterative methods |
Keywords:
graph matrices; multigrid; conditioning; preconditioning; numerical examples; graph-structured large linear systemsReferences:
| [1] | Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs (1993) · Zbl 1201.90001 |
| [2] | Axelsson, O., Lindskög, G.: The rate of convergence of the preconditioned conjugate gradient method. Numer. Math. 52, 499-523 (1986) · Zbl 0564.65017 · doi:10.1007/BF01389448 |
| [3] | Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows. Wiley, New York (1990) · Zbl 0722.90042 |
| [4] | Bhatia, R.: Matrix Analysis. Springer Verlag, New York (1997) · Zbl 0863.15001 · doi:10.1007/978-1-4612-0653-8 |
| [5] | 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 |
| [6] | Boman, E.G., Hendrickson, B.: Support theory for preconditioning. SIAM J. Matrix Anal. Appl. 25(3), 694-717 (2003) · Zbl 1063.65033 · doi:10.1137/S0895479801390637 |
| [7] | Brezina, M., Falgout, R.D., MacLachlan, S., Manteuffel, T.A., McCormick, S.F., Ruge, J.: Adaptive algebraic multigrid. SIAM J. Sci. Comput. 27, 1261-1286 (2006) · Zbl 1100.65025 · doi:10.1137/040614402 |
| [8] | Castro, J.: A specialized interior-point algorithm for multicommodity network flows. SIAM J. Opt. 10, 852-877 (2000) · Zbl 0955.90087 · doi:10.1137/S1052623498341879 |
| [9] | Cayley, A.: A theorem on trees. Quart. J. Math. 23, 376-378 (1889) · JFM 21.0687.01 |
| [10] | Cicone, A., Serra-Capizzano, S.: GOOGLE PageRanking problem: the model and the analysis. J. Comput. Appl. Math. 234-11, 3140-3169 (2010) · Zbl 1197.65035 · doi:10.1016/j.cam.2010.02.005 |
| [11] | Cvetkovic, D., Doob, M., Sachs, H.: Spectra of Graphs. Academic Press, New York (1979) · Zbl 0824.05046 |
| [12] | 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, 40-61 (2010) · Zbl 1209.65011 · doi:10.1137/080719157 |
| [13] | Del Corso, G., Gullí, A., Romani, F.: Fast PageRank computation via a sparse linear system. Internet Math. 3-2, 259-281 (2005) |
| [14] | Dell’Acqua, P.: Algorithmic variations on the theme of structured matrices, with applications to graphs and imaging. Ph.D. thesis, Università dell’Insubria (2013) · Zbl 1177.90287 |
| [15] | Donatelli, M.: A note on grid transfer operators for multigrid methods. Manuscript (2008) arXiv:0807.2565v1 · Zbl 1073.90064 |
| [16] | Frangioni, A., Gentile, C.: New preconditioners for KKT systems of network flow problems. SIAM J. Opt. 14, 894-913 (2004) · Zbl 1073.90064 · doi:10.1137/S105262340240519X |
| [17] | Frangioni, A., Gentile, C.: Prim-based BCT preconditioners for min-cost flow problems. Comput. Opt. Appl. 36, 271-287 (2007) · Zbl 1148.90304 · doi:10.1007/s10589-006-9005-9 |
| [18] | Frangioni, A., Gentile, C.: Experiments with hybrid interior point/combinatorial approaches for network flow problems optim. Methods Softw. 22-4, 573-585 (2007) · Zbl 1177.90287 · doi:10.1080/00207160600848017 |
| [19] | 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 · doi:10.1137/S089547989935366X |
| [20] | 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 · doi:10.1137/0721035 |
| [21] | Kirchhoff, G.: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72, 497-508 (1847) (translated by J. B. O’Toole in I.R.E. Trans. Circuit Theory, CT-5, 1958, 4) |
| [22] | Langville, A., Meyer, C.: A survey of eigenvector methods for WEB information retrieval. SIAM Rev. 47-1, 135-161 (2005) · Zbl 1075.65053 · doi:10.1137/S0036144503424786 |
| [23] | Mohar, B.: Some applications of Laplace eigenvalues of graphs. Graph symmetry: algebraic methods and applications. In: Hahn, G., Sabidussi, G. (Eds.) NATO ASI Series C, vol. 497, pp. 225-275, Kluwer (1997) · Zbl 0883.05096 |
| [24] | 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 · doi:10.1137/S1052623403426398 |
| [25] | Ng, M., Serra-Capizzano, S., Tablino Possio, C.: Multigrid preconditioners for symmetric Sinc systems. ANZIAM J. 45-E, 857-869 (2004) · Zbl 1063.65585 |
| [26] | Notay, Y.: An aggregation-based algebraic multigrid method. Electron. Trans. Numer. Anal. 37, 123-146 (2010) · Zbl 1206.65133 |
| [27] | Notay, Y., Vassilevski, P.S.: Recursive Krylov-based multigrid cycles. Numer. Linear Algebra Appl. 15, 473-487 (2008) · Zbl 1212.65132 · doi:10.1002/nla.542 |
| [28] | Olfati-Saber, R., Murray, R.M.: Consensus problems in networks of agents with switching topology and time-dealays. IEEE Trans. Autom. Control 49-9, 1520-1533 (2004) · Zbl 1365.93301 · doi:10.1109/TAC.2004.834113 |
| [29] | 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 · doi:10.1002/(SICI)1097-0037(200003)35:2<91::AID-NET1>3.0.CO;2-T |
| [30] | Ruge, J.W., Stüben, K.: Algebraic multigrid. In: Multigrid Methods, vol. 3. Frontiers Applied Mathematics, pp. 73-130. SIAM, Philadelphia (1987) |
| [31] | Serra Capizzano, S.: Multi-iterative methods. Comput. Math. Appl. 26-4, 65-87 (1993) · Zbl 0790.65025 · doi:10.1016/0898-1221(93)90035-T |
| [32] | Sterck, H.D., 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 · doi:10.1137/070685142 |
| [33] | Stüben, K.: A review of algebraic multigrid. J. Comput. Appl. Math. 128, 281-309 (2001) · Zbl 0979.65111 · doi:10.1016/S0377-0427(00)00516-1 |
| [34] | Trottenberg, U., Oosterlee, C., Schuller, A.: Multigrid. Academic Press, London (2001) · Zbl 0976.65106 |
| [35] | Varga, R.S.: Matrix Iterative Analysis. Prentice Hall, Englewood Cliffs (1962) · 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.
