Iterative solution of spatial network models by subspace decomposition. (English) Zbl 1525.65025
Summary: We present and analyze a preconditioned conjugate gradient method (PCG) for solving spatial network problems. Primarily, we consider diffusion and structural mechanics simulations for fiber based materials, but the methodology can be applied to a wide range of models, fulfilling a set of abstract assumptions. The proposed method builds on a classical subspace decomposition into a coarse subspace, realized as the restriction of a finite element space to the nodes of the spatial network, and localized subspaces with support on mesh stars. The main contribution of this work is the convergence analysis of the proposed method. The analysis translates results from finite element theory, including interpolation bounds, to the spatial network setting. A convergence rate of the PCG algorithm, only depending on global bounds of the operator and homogeneity, connectivity and locality constants of the network, is established. The theoretical results are confirmed by several numerical experiments.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F08 | Preconditioners for iterative methods |
| 05C40 | Connectivity |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
Keywords:
algebraic connectivity; conjugate gradient; isoparametric dimension; iterative method; network model; preconditioner; subspace decompositionSoftware:
LAMGReferences:
| [1] | M. J. Blunt, B. Bijeljic, H. Dong, O. Gharbi, S. Iglauer, P. Mostaghimi, A. Paluszny, and C. Pentland, Pore-scale imaging and modelling, Adv. in Water Resour. 51 (2013), 197-216. |
| [2] | Brandt, Achi, Multi-level adaptive solutions to boundary-value problems, Math. Comp., 333-390 (1977) · Zbl 0373.65054 · doi:10.2307/2006422 |
| [3] | Brannick, J., Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs, SIAM J. Numer. Anal., 1805-1827 (2013) · Zbl 1281.65152 · doi:10.1137/120876083 |
| [4] | Brenner, Susanne C., The Mathematical Theory of Finite Element Methods, Texts in Applied Mathematics, xviii+397 pp. (2008), Springer, New York · Zbl 1135.65042 · doi:10.1007/978-0-387-75934-0 |
| [5] | J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis, R. C. Gunning, editor, Princeton University Press 1970, pp.195-199. · Zbl 0212.44903 |
| [6] | F. Chung, Discrete Isoperimetric Inequalities, Surveys in Differential Geometry IX, International Press, 2004, pp.53-82. · Zbl 1067.53025 |
| [7] | F. Chung, Spectral Graph Theory, American Mathematical Society, Providence, 1997. · Zbl 0867.05046 |
| [8] | Chung, Fan, Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs, Comm. Anal. Geom., 969-1026 (2000) · Zbl 1001.58022 · doi:10.4310/CAG.2000.v8.n5.a2 |
| [9] | Chung, F. R. K., Eigenvalues of graphs and Sobolev inequalities, Combin. Probab. Comput., 11-25 (1995) · Zbl 0843.05073 · doi:10.1017/S0963548300001449 |
| [10] | Cl\'{e}ment, Ph., Approximation by finite element functions using local regularization, Rev. Fran\c{c}aise Automat. Informat. Recherche Op\'{e}rationnelle S\'{e}r., 77-84 (1975) · Zbl 0368.65008 |
| [11] | M. G\"ortz, G. Kettil, A. M\aa lqvist, M. Fredlund, K. Wester, and F. Edelvik, Network models for predicting structural properties of paper, Nordic Pulp Paper, 37 (2022), 712-724. |
| [12] | M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23, no. 2 (1973), pp.298-305. · Zbl 0265.05119 |
| [13] | Gergelits, Tom\'{a}\v{s}, Composite convergence bounds based on Chebyshev polynomials and finite precision conjugate gradient computations, Numer. Algorithms, 759-782 (2014) · Zbl 1298.65054 · doi:10.1007/s11075-013-9713-z |
| [14] | M. Gjennestad, M. Vassvik, S. Kjelstrup, and A. Hansen, Stable and efficient time integration of a pore network model for two-phase flow in porous media, Front. Phys., 6 (2018). |
| [15] | Graham, I. G., Domain decomposition for multiscale PDEs, Numer. Math., 589-626 (2007) · Zbl 1141.65084 · doi:10.1007/s00211-007-0074-1 |
| [16] | X. Hu, E. Keilegavlen, and J. M. Nordbotten, Effective preconditioners for mixed-dimensional scalar elliptic problems, Water Resources Research, 2023, published online. |
| [17] | Hu, Xiaozhe, A posteriori error estimates for multilevel methods for graph Laplacians, SIAM J. Sci. Comput., S727-S742 (2021) · Zbl 1481.65257 · doi:10.1137/20M1349618 |
| [18] | X. Huang, W. Zhou, and D. Deng, Validation of pore network modeling for determination of two-phase transport in fibrous porous media, Sci. Rep. 10 (2020), 20852. |
| [19] | Jones, Jim E., AMGe based on element agglomeration, SIAM J. Sci. Comput., 109-133 (2001) · Zbl 0992.65140 · doi:10.1137/S1064827599361047 |
| [20] | I. Koutis, G. L. Miller, and D. Tolliver, Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing, Comput. Vis. Image Underst. 115 (2011), 1638-1646. |
| [21] | Iliev, Oleg, Fast numerical upscaling of heat equation for fibrous materials, Comput. Vis. Sci., 275-285 (2010) · Zbl 1419.74099 · doi:10.1007/s00791-010-0144-2 |
| [22] | Livne, Oren E., Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver, SIAM J. Sci. Comput., B499-B522 (2012) · Zbl 1253.65045 · doi:10.1137/110843563 |
| [23] | Kettil, G., Numerical upscaling of discrete network models, BIT, 67-92 (2020) · Zbl 1431.65208 · doi:10.1007/s10543-019-00767-2 |
| [24] | Kornhuber, Ralf, An analysis of a class of variational multiscale methods based on subspace decomposition, Math. Comp., 2765-2774 (2018) · Zbl 1397.65233 · doi:10.1090/mcom/3302 |
| [25] | Kornhuber, Ralf, Numerical homogenization of elliptic multiscale problems by subspace decomposition, Multiscale Model. Simul., 1017-1036 (2016) · Zbl 1352.65521 · doi:10.1137/15M1028510 |
| [26] | M\aa lqvist, Axel, Computation of eigenvalues by numerical upscaling, Numer. Math., 337-361 (2015) · Zbl 1333.65127 · doi:10.1007/s00211-014-0665-6 |
| [27] | M\aa lqvist, A., Numerical Homogenization by Localized Orthogonal Decomposition, SIAM Spotlights, xii+108 pp. ([2021] ©2021), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1479.65001 |
| [28] | Napov, Artem, An algebraic multigrid method with guaranteed convergence rate, SIAM J. Sci. Comput., A1079-A1109 (2012) · Zbl 1248.65037 · doi:10.1137/100818509 |
| [29] | Napov, Artem, An efficient multigrid method for graph Laplacian systems, Electron. Trans. Numer. Anal., 201-218 (2016) · Zbl 1347.65059 |
| [30] | Saad, Yousef, Iterative Methods for Sparse Linear Systems, xviii+528 pp. (2003), Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 1031.65046 · doi:10.1137/1.9780898718003 |
| [31] | Scheichl, Robert, Multilevel methods for elliptic problems with highly varying coefficients on nonaligned coarse grids, SIAM J. Numer. Anal., 1675-1694 (2012) · Zbl 1259.65190 · doi:10.1137/100805248 |
| [32] | Tillich, Jean-Pierre, Edge isoperimetric inequalities for product graphs, Discrete Math., 291-320 (2000) · Zbl 0959.05064 · doi:10.1016/S0012-365X(99)00189-2 |
| [33] | B. Smith, P. Bj\o rstad, and W. Gropp, Domain Decomposition, Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, 1996. · Zbl 0857.65126 |
| [34] | St\"{u}ben, K., A review of algebraic multigrid, J. Comput. Appl. Math., 281-309 (2001) · Zbl 0979.65111 · doi:10.1016/S0377-0427(00)00516-1 |
| [35] | Xu, Jinchao, Iterative methods by space decomposition and subspace correction, SIAM Rev., 581-613 (1992) · Zbl 0788.65037 · doi:10.1137/1034116 |
| [36] | Xu, Jinchao, Algebraic multigrid methods, Acta Numer., 591-721 (2017) · Zbl 1378.65182 · doi:10.1017/S0962492917000083 |
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.
