×
An, Chengtao; Su, Yangfeng

An aggregation-based two-grid method for multilevel block Toeplitz linear systems. (English) Zbl 1534.65053

J. Sci. Comput. 98, No. 3, Paper No. 54, 47 p. (2024).
Summary: This paper presents an aggregation-based two-grid method for solving a multilevel block Toeplitz system. Different from the existing multigrid methods for multilevel block Toeplitz systems, we aggregate a given multilevel block Toeplitz matrix to a new multilevel Toeplitz matrix in such a way that a very sparse coarse grid matrix is constructed in practice. Then, we give an asymptotically tight bound of the convergence rate and provide an algorithm for selecting the optimal prolongation vector and the relaxation factor for our method. Numerical experiments on artificial examples are provided for visualizing the correctness of our analysis, while experiments associated with practical examples show the efficiency of our method in terms of computing time.

MSC:

65F10 Iterative numerical methods for linear systems
15B05 Toeplitz, Cauchy, and related matrices

Keywords:

multilevel block Toeplitz systems; aggregation-based two-grid methods; convergence analysis; parameter selection

Software:

Optimization Toolbox
Cite Review PDF
Full Text: DOI

References:

[1] An, C., Li, C., Li, X., Su, Y., Yang, F., Zeng, X.: FPDsim: a structural simulator for power grid analysis of flat panel display. In: 60th ACM/IEEE Design Automation Conference (DAC), pp. 1-6 (2023)
[2] Audet, C.; Dennis, JE Jr, Analysis of generalized pattern searches, SIAM J. Optim., 13, 3, 889-903 (2002) · Zbl 1053.90118 · doi:10.1137/S1052623400378742
[3] Bolten, M.; Donatelli, M.; Ferrari, P.; Furci, I., A symbol-based analysis for multigrid methods for block-Circulant and block-Toeplitz systems, SIAM J. Matrix Anal. Appl., 43, 1, 405-438 (2022) · Zbl 1508.65025 · doi:10.1137/21M1390554
[4] Braess, D., Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics (2007), Cambridge: Cambridge University Press, Cambridge · Zbl 1118.65117 · doi:10.1017/CBO9780511618635
[5] Brandt, A., MacCormick, S., Ruge, J.: Algebraic Multigrid (AMG) for Automatic Multigrid Solution with Application to Geodetic Computations. Report, Institute for Computational Studies, Fort Collins, Colorado (1982)
[6] Chan, RH; Chang, QS; Sun, HW, Multigrid method for ill-conditioned symmetric Toeplitz systems, SIAM J. Sci. Comput., 19, 2, 516-529 (1998) · Zbl 0916.65029 · doi:10.1137/S1064827595293831
[7] Chan, RH; Jin, XQ, An Introduction to Iterative Toeplitz Solvers (2007), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 1146.65028 · doi:10.1137/1.9780898718850
[8] Chan, RH; Ng, MK, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 3, 427-482 (1996) · Zbl 0863.65013 · doi:10.1137/S0036144594276474
[9] Cheung, SW; Chung, E.; Kim, HH; Qian, Y., Staggered discontinuous Galerkin methods for the incompressible Navier-Stokes equations, J. Comput. Phys., 302, 251-266 (2015) · Zbl 1349.76189 · doi:10.1016/j.jcp.2015.08.024
[10] Chung, ET; Ciarlet, P. Jr; Yu, TF, Convergence and superconvergence of staggered discontinuous Galerkin methods for the three-dimensional Maxwell’s equations on Cartesian grids, J. Comput. Phys., 235, 14-31 (2013) · Zbl 1291.65278 · doi:10.1016/j.jcp.2012.10.019
[11] Donatelli, M.; Dorostkar, A.; Mazza, M.; Neytcheva, M.; Serra-Capizzano, S., Function-based block multigrid strategy for a two-dimensional linear elasticity-type problem, Comput. Math. Appl., 74, 5, 1015-1028 (2017) · Zbl 1390.74176 · doi:10.1016/j.camwa.2017.05.024
[12] Donatelli, M.; Ferrari, P.; Furci, I.; Serra-Capizzano, S.; Sesana, D., Multigrid methods for block-Toeplitz linear systems: convergence analysis and applications, Numer. Linear Algebra Appl., 28, 4 (2021) · Zbl 07396240 · doi:10.1002/nla.2356
[13] Dumbser, M.; Fambri, F.; Furci, I.; Mazza, M.; Serra-Capizzano, S.; Tavelli, M., Staggered discontinuous Galerkin methods for the incompressible Navier-Stokes equations: spectral analysis and computational results, Numer. Linear Algebra Appl., 25, 5 (2018) · Zbl 1513.65356 · doi:10.1002/nla.2151
[14] Ekström, SE; Furci, I.; Serra-Capizzano, S., Exact formulae and matrix-less eigensolvers for block banded symmetric Toeplitz matrices, BIT, 58, 4, 937-968 (2018) · Zbl 1405.65051 · doi:10.1007/s10543-018-0715-z
[15] Falgout, RD; Vassilevski, PS; Zikatanov, LT, On two-grid convergence estimates, Numer. Linear Algebra Appl., 12, 5-6, 471-494 (2005) · Zbl 1164.65343 · doi:10.1002/nla.437
[16] Fambri, F.; Dumbser, M., Spectral semi-implicit and space-time discontinuous Galerkin methods for the incompressible Navier-Stokes equations on staggered Cartesian grids, Appl. Numer. Math., 110, 41-74 (2016) · Zbl 1432.76157 · doi:10.1016/j.apnum.2016.07.014
[17] Ferrari, P.; Rahla, RI; Tablino-Possio, C.; Belhaj, S.; Serra-Capizzano, S., Multigrid for q k finite element matrices using a (block) Toeplitz symbol approach, Mathematics, 8, 1, 5 (2019) · doi:10.3390/math8010005
[18] Fiorentino, G.; Serra, S., Multigrid methods for Toeplitz matrices, Calcolo, 28, 3-4, 283-305 (1991) · Zbl 0778.65021 · doi:10.1007/BF02575816
[19] Fiorentino, G.; Serra, S., Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM J. Sci. Comput., 17, 5, 1068-1081 (1996) · Zbl 0858.65039 · doi:10.1137/S1064827594271512
[20] Garoni, C.: Structured matrices coming from PDE approximation theory: spectral analysis, spectral symbol and design of fast iterative solvers. Ph.D. thesis, Università degli Studi dell’Insubria (2015)
[21] Garoni, C.; Serra-Capizzano, S.; Sesana, D., Spectral analysis and spectral symbol of d-variate \(\mathbb{Q}_{\varvec{p}}\) Lagrangian FEM stiffness matrices, SIAM J. Matrix Anal. Appl., 36, 3, 1100-1128 (2015) · Zbl 1321.65173 · doi:10.1137/140976480
[22] Grenander, U.; Szegö, G., Toeplitz Forms and Their Applications (1958), Berkeley: University of California Press, Berkeley · Zbl 0080.09501 · doi:10.1525/9780520355408
[23] Hu, X.; Vassilevski, PS; Xu, J., A two-grid SA-AMG convergence bound that improves when increasing the polynomial degree, Numer. Linear Algebra Appl., 23, 4, 746-771 (2016) · Zbl 1413.65062 · doi:10.1002/nla.2053
[24] Huckle, T.; Staudacher, J., Multigrid methods for block Toeplitz matrices with small size blocks, BIT, 46, 1, 61-83 (2006) · Zbl 1103.65035 · doi:10.1007/s10543-006-0047-2
[25] Kailath, T.; Sayed, AH, Fast Reliable Algorithms for Matrices with Structure (1999), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 0931.65018 · doi:10.1137/1.9781611971354
[26] Kim, H.; Xu, J.; Zikatanov, L., A multigrid method based on graph matching for convection-diffusion equations, Numer. Linear Algebra Appl., 10, 1-2, 181-195 (2003) · Zbl 1071.65167 · doi:10.1002/nla.317
[27] MathWorks, I., Global Optimization Toolbox User’s Guide (2022), Natick: The Mathworks Inc., Natick
[28] Notay, Y., An aggregation-based algebraic multigrid method, Electron. Trans. Numer. Anal., 37, 6, 123-146 (2010) · Zbl 1206.65133
[29] Notay, Y., Algebraic theory of two-grid methods, Numer. Math. Theory Methods Appl., 8, 2, 168-198 (2015) · Zbl 1349.65681 · doi:10.4208/nmtma.2015.w04si
[30] Oosterlee, C., Washio, T.: On the use of multigrid as a preconditioner. In: Proceedings of Ninth International Conference on Domain Decomposition Methods, pp. 441-448 (1996)
[31] Ruge, J.W., Stüben, K.: Algebraic multigrid. In: Multigrid methods, pp. 73-130. SIAM, Philadelphia, PA (1987)
[32] Serra, S., Asymptotic results on the spectra of block Toeplitz preconditioned matrices, SIAM J. Matrix Anal. Appl., 20, 1, 31-44 (1998) · Zbl 0932.65037 · doi:10.1137/S0895479896310160
[33] Serra, S., Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions, BIT, 39, 152-175 (1999) · Zbl 0917.65031 · doi:10.1023/A:1022329526925
[34] Serra-Capizzano, S., Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear, Linear Algebra Appl., 343, 303-319 (2002) · Zbl 1001.65041 · doi:10.1016/S0024-3795(01)00361-5
[35] Serra-Capizzano, S.; Tablino-Possio, C., Multigrid methods for multilevel circulant matrices, SIAM J. Sci. Comput., 26, 1, 55-85 (2004) · Zbl 1079.65033 · doi:10.1137/S1064827501388509
[36] Serra Capizzano, S.; Tyrtyshnikov, E., How to prove that a preconditioner cannot be superlinear, Math. Comput., 72, 243, 1305-1316 (2003) · Zbl 1021.15005 · doi:10.1090/S0025-5718-03-01506-0
[37] Tilli, P., A note on the spectral distribution of Toeplitz matrices, Linear Multilinear Algebra, 45, 2-3, 147-159 (1998) · Zbl 0951.65033 · doi:10.1080/03081089808818584
[38] Trottenberg, U.; Oosterlee, CW; Schuller, A., Multigrid (2000), Amsterdam: Elsevier, Amsterdam
[39] Tyrtyshnikov, EE, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl., 232, 1-43 (1996) · Zbl 0841.15006 · doi:10.1016/0024-3795(94)00025-5
[40] Vaněk, P.; Mandel, J.; Brezina, M., Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, 3, 179-196 (1996) · Zbl 0851.65087 · doi:10.1007/BF02238511
[41] Xu, J.; Zikatanov, L., Algebraic multigrid methods, Acta Numer., 26, 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.