Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs (1993)
Axelsson, O., Lindskög, G.: The rate of convergence of the preconditioned conjugate gradient method. Numer. Math. 52, 499–523 (1986)
Bazaraa, M.S., Jarvis, J.J., Sherali, H.D.: Linear Programming and Network Flows. Wiley, New York (1990)
Bhatia, R.: Matrix Analysis. Springer Verlag, New York (1997)
Boman,E.G., Chen, D., Hendrickson, B., Toledo, S.: Maximum-weight-basis preconditioners. Numer. Linear Algebra Appl. 11(8–9), 695–721 (2004)
Boman, E.G., Hendrickson, B.: Support theory for preconditioning. SIAM J. Matrix Anal. Appl. 25(3), 694–717 (2003)
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)
Castro, J.: A specialized interior-point algorithm for multicommodity network flows. SIAM J. Opt. 10, 852–877 (2000)
Cayley, A.: A theorem on trees. Quart. J. Math. 23, 376–378 (1889)
Cicone, A., Serra-Capizzano, S.: GOOGLE PageRanking problem: the model and the analysis. J. Comput. Appl. Math. 234–11, 3140–3169 (2010)
Cvetkovic, D., Doob, M., Sachs, H.: Spectra of Graphs. Academic Press, New York (1979)
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)
Del Corso, G., Gullí, A., Romani, F.: Fast PageRank computation via a sparse linear system. Internet Math. 3–2, 259–281 (2005)
Dell’Acqua, P.: Algorithmic variations on the theme of structured matrices, with applications to graphs and imaging. Ph.D. thesis, Università dell’Insubria (2013)
Donatelli, M.: A note on grid transfer operators for multigrid methods. Manuscript (2008) arXiv:0807.2565v1
Frangioni, A., Gentile, C.: New preconditioners for KKT systems of network flow problems. SIAM J. Opt. 14, 894–913 (2004)
Frangioni, A., Gentile, C.: Prim-based BCT preconditioners for min-cost flow problems. Comput. Opt. Appl. 36, 271–287 (2007)
Frangioni, A., Gentile, C.: Experiments with hybrid interior point/combinatorial approaches for network flow problems optim. Methods Softw. 22–4, 573–585 (2007)
Frangioni, A., Serra Capizzano, S.: Spectral analysis of (sequences of) graph matrices. SIAM J. Matrix Anal. Appl. 23–2, 339–348 (2001)
Greenbaum, A.: Analysis of a multigrid method as an iterative technique for solving linear systems. SIAM J. Numer. Anal. 21–3, 473–485 (1984)
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)
Langville, A., Meyer, C.: A survey of eigenvector methods for WEB information retrieval. SIAM Rev. 47–1, 135–161 (2005)
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)
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)
Ng, M., Serra-Capizzano, S., Tablino Possio, C.: Multigrid preconditioners for symmetric Sinc systems. ANZIAM J. 45-E, 857–869 (2004)
Notay, Y.: An aggregation-based algebraic multigrid method. Electron. Trans. Numer. Anal. 37, 123–146 (2010)
Notay, Y., Vassilevski, P.S.: Recursive Krylov-based multigrid cycles. Numer. Linear Algebra Appl. 15, 473–487 (2008)
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)
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)
Ruge, J.W., Stüben, K.: Algebraic multigrid. In: Multigrid Methods, vol. 3. Frontiers Applied Mathematics, pp. 73–130. SIAM, Philadelphia (1987)
Serra Capizzano, S.: Multi-iterative methods. Comput. Math. Appl. 26–4, 65–87 (1993)
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)
Stüben, K.: A review of algebraic multigrid. J. Comput. Appl. Math. 128, 281–309 (2001)
Trottenberg, U., Oosterlee, C., Schuller, A.: Multigrid. Academic Press, London (2001)
Varga, R.S.: Matrix Iterative Analysis. Prentice Hall, Englewood Cliffs (1962)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dell’Acqua, P., Frangioni, A. & Serra-Capizzano, S. Computational evaluation of multi-iterative approaches for solving graph-structured large linear systems. Calcolo 52, 425–444 (2015). https://doi.org/10.1007/s10092-014-0123-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10092-014-0123-y