Iterative solution of spatial network models by subspace decomposition

Görtz, Morgan; Hellman, Fredrik; Målqvist, Axel

doi:10.1090/mcom/3861

Iterative solution of spatial network models by subspace decomposition
HTML articles powered by AMS MathViewer

by Morgan Görtz, Fredrik Hellman and Axel Målqvist

Math. Comp. 93 (2024), 233-258

DOI: https://doi.org/10.1090/mcom/3861

Published electronically: June 20, 2023

HTML | PDF | Request permission

Abstract:

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.

References

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.
Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X
J. Brannick, Y. Chen, J. Kraus, and L. Zikatanov, Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs, SIAM J. Numer. Anal. 51 (2013), no. 3, 1805–1827. MR 3069092, DOI 10.1137/120876083
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 3rd ed., Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. MR 2373954, DOI 10.1007/978-0-387-75934-0
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.
F. Chung, Discrete Isoperimetric Inequalities, Surveys in Differential Geometry IX, International Press, 2004, pp. 53–82.
F. Chung, Spectral Graph Theory, American Mathematical Society, Providence, 1997.
Fan Chung, Alexander Grigor′yan, and Shing-Tung Yau, Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs, Comm. Anal. Geom. 8 (2000), no. 5, 969–1026. MR 1846124, DOI 10.4310/CAG.2000.v8.n5.a2
F. R. K. Chung and S.-T. Yau, Eigenvalues of graphs and Sobolev inequalities, Combin. Probab. Comput. 4 (1995), no. 1, 11–25. MR 1336652, DOI 10.1017/S0963548300001449
Ph. Clément, Approximation by finite element functions using local regularization, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér. 9 (1975), no. no. , no. R-2, 77–84 (English, with French summary). MR 400739, DOI 10.1051/m2an/197509R200771
M. Görtz, G. Kettil, A. Målqvist, M. Fredlund, K. Wester, and F. Edelvik, Network models for predicting structural properties of paper, Nordic Pulp Paper, 37 (2022), 712–724.
M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23, no. 2 (1973), pp. 298–305.
Tomáš Gergelits and Zdeněk Strakoš, Composite convergence bounds based on Chebyshev polynomials and finite precision conjugate gradient computations, Numer. Algorithms 65 (2014), no. 4, 759–782. MR 3187962, DOI 10.1007/s11075-013-9713-z
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).
I. G. Graham, P. O. Lechner, and R. Scheichl, Domain decomposition for multiscale PDEs, Numer. Math. 106 (2007), no. 4, 589–626. MR 2317926, DOI 10.1007/s00211-007-0074-1
X. Hu, E. Keilegavlen, and J. M. Nordbotten, Effective preconditioners for mixed-dimensional scalar elliptic problems, Water Resources Research, 2023, published online.
Xiaozhe Hu, Kaiyi Wu, and Ludmil T. Zikatanov, A posteriori error estimates for multilevel methods for graph Laplacians, SIAM J. Sci. Comput. 43 (2021), no. 5, S727–S742. MR 4331968, DOI 10.1137/20M1349618
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.
Jim E. Jones and Panayot S. Vassilevski, AMGe based on element agglomeration, SIAM J. Sci. Comput. 23 (2001), no. 1, 109–133. MR 1860907, DOI 10.1137/S1064827599361047
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.
Oleg Iliev, Raytcho Lazarov, and Joerg Willems, Fast numerical upscaling of heat equation for fibrous materials, Comput. Vis. Sci. 13 (2010), no. 6, 275–285. MR 2748452, DOI 10.1007/s00791-010-0144-2
Oren E. Livne and Achi Brandt, Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver, SIAM J. Sci. Comput. 34 (2012), no. 4, B499–B522. MR 2970416, DOI 10.1137/110843563
G. Kettil, A. Målqvist, A. Mark, M. Fredlund, K. Wester, and F. Edelvik, Numerical upscaling of discrete network models, BIT 60 (2020), no. 1, 67–92. MR 4068382, DOI 10.1007/s10543-019-00767-2
Ralf Kornhuber, Daniel Peterseim, and Harry Yserentant, An analysis of a class of variational multiscale methods based on subspace decomposition, Math. Comp. 87 (2018), no. 314, 2765–2774. MR 3834684, DOI 10.1090/mcom/3302
Ralf Kornhuber and Harry Yserentant, Numerical homogenization of elliptic multiscale problems by subspace decomposition, Multiscale Model. Simul. 14 (2016), no. 3, 1017–1036. MR 3536998, DOI 10.1137/15M1028510
Axel Målqvist and Daniel Peterseim, Computation of eigenvalues by numerical upscaling, Numer. Math. 130 (2015), no. 2, 337–361. MR 3343928, DOI 10.1007/s00211-014-0665-6
A. Målqvist and D. Peterseim, Numerical homogenization by localized orthogonal decomposition, SIAM Spotlights, vol. 5, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, [2021] ©2021. MR 4191211
Artem Napov and Yvan Notay, An algebraic multigrid method with guaranteed convergence rate, SIAM J. Sci. Comput. 34 (2012), no. 2, A1079–A1109. MR 2914316, DOI 10.1137/100818509
Artem Napov and Yvan Notay, An efficient multigrid method for graph Laplacian systems, Electron. Trans. Numer. Anal. 45 (2016), 201–218. MR 3510804
Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
Robert Scheichl, Panayot S. Vassilevski, and Ludmil T. Zikatanov, Multilevel methods for elliptic problems with highly varying coefficients on nonaligned coarse grids, SIAM J. Numer. Anal. 50 (2012), no. 3, 1675–1694. MR 2970760, DOI 10.1137/100805248
Jean-Pierre Tillich, Edge isoperimetric inequalities for product graphs, Discrete Math. 213 (2000), no. 1-3, 291–320. Selected topics in discrete mathematics (Warsaw, 1996). MR 1755430, DOI 10.1016/S0012-365X(99)00189-2
B. Smith, P. Bjørstad, and W. Gropp, Domain Decomposition, Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, 1996.
K. Stüben, A review of algebraic multigrid, J. Comput. Appl. Math. 128 (2001), no. 1-2, 281–309. Numerical analysis 2000, Vol. VII, Partial differential equations. MR 1820878, DOI 10.1016/S0377-0427(00)00516-1
Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
Jinchao Xu and Ludmil Zikatanov, Algebraic multigrid methods, Acta Numer. 26 (2017), 591–721. MR 3653855, DOI 10.1017/S0962492917000083