Function-based block multigrid strategy for a two-dimensional linear elasticity-type problem. (English) Zbl 1390.74176
Summary: We consider the solution of block-coupled large-scale linear systems of equations, arising from the finite element approximation of the linear elasticity problem. Due to the large scale of the problems we use properly preconditioned iterative methods, where the preconditioners utilize the underlying block matrix structures, involving inner block solvers and, when suited, broadly established tools such as the algebraic Multigrid method (AMG).
For the considered problem, despite of its optimal rate of convergence, AMG, as implemented in some publicly available scientific libraries, imposes unacceptably high demands for computer resources. In this paper we propose and analyze an efficient multilevel preconditioner, based on the Generalized Locally Toeplitz framework, with a specialized transfer operator. We prove and numerically illustrate the optimal convergence rate of the proposed preconditioner, and experimentally report memory and CPU time savings. We also provide comparisons with respect to another aggregation-based algebraic multigrid algorithm.
For the considered problem, despite of its optimal rate of convergence, AMG, as implemented in some publicly available scientific libraries, imposes unacceptably high demands for computer resources. In this paper we propose and analyze an efficient multilevel preconditioner, based on the Generalized Locally Toeplitz framework, with a specialized transfer operator. We prove and numerically illustrate the optimal convergence rate of the proposed preconditioner, and experimentally report memory and CPU time savings. We also provide comparisons with respect to another aggregation-based algebraic multigrid algorithm.
MSC:
| 74S05 | Finite element methods applied to problems in solid mechanics |
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 74B05 | Classical linear elasticity |
| 35Q74 | PDEs in connection with mechanics of deformable solids |
Keywords:
multilevel Toeplitz matrices; multigrid methods; coupled PDEs; linear elasticity; finite elementsReferences:
| [1] | Georgiev, I.; Kraus, J.; Margenov, S.; Schicho, J., Locally optimized MIC(0) preconditioning of rannacher-turek FEM systems, Appl. Numer. Math., 59, 2402-2415, (2009) · Zbl 1167.65453 |
| [2] | Axelsson, O., On iterative solvers in structural mechanics; separate displacement orderings and mixed variable methods, Math. Comput. Simulation, 50, 1-4, 11-30, (1999) · Zbl 1053.74651 |
| [3] | Turan, E.; Arbenz, P., Large scale micro finite element analysis of 3D bone poroelasticity, Parallel Comput., 40, 7, 239-250, (2014) |
| [4] | Donatelli, M.; Molteni, M.; Pennati, V.; Serra-Capizzano, S., Multigrid methods for cubic spline solution of two point (and 2D) boundary value problems, Ann. Numer. Math., 104, 15-29, (2016) · Zbl 1336.65120 |
| [5] | Wu, P., Deformation of an incompressible viscoelastic flat Earth with power law creep: a finite element approach, Geophys. J. Int., 108, 136-142, (1992) |
| [6] | Wu, P., Using commercial finite element packages for the study of Earth deformations, sea levels and the state of stress, Geophys. J. Int., 158, 401-408, (2004) |
| [7] | Lund, B.; Näslund, J. O., Glacial isostatic adjustment: implications for glacially induced faulting and nuclear waste repositories, (Volcanic and Tectonic Hazard Assessment of Nuclear Facilities, (2009), Cambridge University Press) |
| [8] | Braess, D., Finite Elements. Theory, Fast Solvers, and Applications in Solid Mechanics, (2001), Cambridge University Press Cambridge · Zbl 0976.65099 |
| [9] | Saad, Y.; Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869, (1986) · Zbl 0599.65018 |
| [10] | Murphy, M.; Golub, G.; Wathen, A., A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21, 1969-1972, (2000) · Zbl 0959.65063 |
| [11] | Ipsen, I., A note on preconditioning nonsymmetric matrices, SIAM J. Sci. Stat. Comput., 23, 1050-1051, (2001) · Zbl 0998.65049 |
| [12] | H.C. Elman, D.J. Silvester, A.J. Wathen, Finite Elements and Fast Iterative Solvers : with Applications in Incompressible Fluid Dynamics, Oxford, 2005.; H.C. Elman, D.J. Silvester, A.J. Wathen, Finite Elements and Fast Iterative Solvers : with Applications in Incompressible Fluid Dynamics, Oxford, 2005. · Zbl 1083.76001 |
| [13] | Neytcheva, M., On element-by-element Schur complement approximations, Linear Algebra Appl., 434, 11, 2308-2324, (2011), special Issue: Devoted to the 2nd NASC 08 Conference in Nanjing (NSC) · Zbl 1216.65041 |
| [14] | Axelsson, O.; Blaheta, R.; Neytcheva, M., Preconditioning of boundary value problems using elementwise Schur complements, SIAM J. Matrix Anal. Appl., 31, 2, 767-789, (2009) · Zbl 1194.65047 |
| [15] | Kraus, J., Algebraic multilevel preconditioning of finite element matrices using local Schur complements, Numerical Linear Algebra Appl., 13, 1, 49-70, (2006) · Zbl 1174.65398 |
| [16] | Dorostkar, A.; Neytcheva, M.; Lund, B., Numerical and computational aspects of some block-preconditioners for saddle point systems, Parallel Comput., 49, 164-178, (2015) |
| [17] | Fiorentino, G.; Serra Capizzano, S., Multigrid methods for Toeplitz matrices, Calcolo, 28, 283-305, (1991) · Zbl 0778.65021 |
| [18] | Chan, R. H.; Chang, Q.; Sun, H., Multigrid method for ill-conditioned symmetric Toeplitz systems, SIAM J. Sci. Comput., 19, 2, 516-529, (1998) · Zbl 0916.65029 |
| [19] | Huckle, T.; Staudacher, J., Multigrid preconditioning and Toeplitz matrices, Electron. Trans. Numer. Anal., 13, 81-105, (2002) · Zbl 1065.65063 |
| [20] | Chang, Q.; Jin, X.; Sun, H., Convergence of the multigrid method for ill-conditioned block Toeplitz systems, BIT, 41, 1, 179-190, (2001) · Zbl 0991.65033 |
| [21] | Serra-Capizzano, S., Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences, Numer. Math., 92, 3, 433-465, (2002) · Zbl 1013.65026 |
| [22] | Aricò, A.; Donatelli, M., A V-cycle multigrid for multilevel matrix algebras: proof of optimality, Numer. Math., 105, 4, 511-547, (2007) · Zbl 1114.65033 |
| [23] | 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 |
| [24] | Donatelli, M.; Serra-Capizzano, S.; Sesana, D., Multigrid methods for Toeplitz linear systems with different size reduction, BIT, 52, 2, 305-327, (2012) · Zbl 1251.65047 |
| [25] | Bolten, M.; Donatelli, M.; Huckle, T., Analysis of smoothed aggregation multigrid methods based on Toeplitz matrices, Electron. Trans. Numer. Anal., 44, 25-52, (2015) · Zbl 1312.65205 |
| [26] | Huckle, T.; Staudacher, J., Multigrid methods for block matrices with small size blocks, BIT, 46, 61-83, (2006) · Zbl 1103.65035 |
| [27] | Huckle, T., Compact Fourier analysis for designing multigrid methods, SIAM J. Sci. Comput., 31, 1, 644-666, (2008) · Zbl 1186.65037 |
| [28] | Ruge, J. W.; Stüben, K., Algebraic multigrid, (McCormick, S., Frontiers in Applied Mathematics: Multigrid Methods, (1987), SIAM Philadelphia), 73-130 |
| [29] | Serra-Capizzano, S.; Tablino-Possio, C., Two-grid methods for Hermitian positive definite linear systems connected with an order relation, Calcolo, 51, 2, 261-285, (2014) · Zbl 1311.65034 |
| [30] | Tilli, P., A note on the spectral distribution of Toeplitz matrices, Linear Multilinear Algebra, 45, 147-159, (1998) · Zbl 0951.65033 |
| [31] | Tilli, P., Locally Toeplitz sequences: spectral properties and applications, Linear Algebra Appl., 278, 1/3, 91-120, (1998) · Zbl 0934.15009 |
| [32] | Serra-Capizzano, S., The GLT class as a generalized Fourier analysis and applications, Linear Algebra Appl., 419, 180-233, (2006) · Zbl 1109.65032 |
| [33] | Dorostkar, A.; Neytcheva, M.; Serra-Capizzano, S., Spectral analysis of coupled PDEs and of their Schur complements via the notion of generalized locally Toeplitz sequences, Comput. Methods Appl. Mech. Engrg., 309, 74-105, (2016) · Zbl 1439.65138 |
| [34] | Serra-Capizzano, S., Some theorems on linear positive operators and functionals and their applications, Comput. Math. Appl., 39, 7/8, 139-167, (2000) · Zbl 1003.47030 |
| [35] | 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 |
| [36] | Yousef Saad, Iterative methods for sparse linear systems, second ed., PWS Publishing, Boston, MA, SIAM. ISBN 978-0-89871-534-7.; Yousef Saad, Iterative methods for sparse linear systems, second ed., PWS Publishing, Boston, MA, SIAM. ISBN 978-0-89871-534-7. · Zbl 1031.65047 |
| [37] | Y. Notay, AGMG software. http://homepages.ulb.ac.be/ ynotay/AGMG/; Y. Notay, AGMG software. http://homepages.ulb.ac.be/ ynotay/AGMG/ |
| [38] | Notay, Y., An aggregation-based algebraic multigrid method, Electron. Trans. Numer. Anal., 37, 123-146, (2010) · Zbl 1206.65133 |
| [39] | Napov, A.; Notay, Y., An algebraic multigrid method with guaranteed convergence rate, SIAM J. Sci. Comput., 34, 1079-1109, (2012) · Zbl 1248.65037 |
| [40] | Notay, Y., Aggregation-based algebraic multigrid for convection-diffusion equations, SIAM J. Sci. Comput., 34, 2288-2316, (2012) · Zbl 1250.76139 |
| [41] | Muresan, A. C.; Notay, Y., Analysis of aggregation-based multigrid, SIAM J. Sci. Comput., 30, 1082-1103, (2008) · Zbl 1163.65092 |
| [42] | Heroux, M. A.; Bartlett, R. A.; Howle, V. E.; Hoekstra, R. J.; Hu, J. J.; Kolda, T. G.; Lehoucq, R. B.; Long, K. R.; Pawlowski, R. P.; Phipps, E. T.; Salinger, A. G.; Thornquist, H. K.; Tuminaro, R. S.; Willenbring, J. M.; Williams, A.; Stanley, K. S., An overview of the trilinos project, ACM Trans. Math. Software, 31, 397-423, (2005) · Zbl 1136.65354 |
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.
