×

A symbol-based analysis for multigrid methods for block-circulant and block-Toeplitz systems. (English) Zbl 1508.65025

Summary: In the literature, there exist several studies on symbol-based multigrid methods for the solution of linear systems having structured coefficient matrices. In particular, the convergence analysis for such methods has been obtained in an elegant form in the case of Toeplitz matrices generated by a scalar-valued function. In the block-Toeplitz setting, that is, in the case where the matrix entries are small generic matrices instead of scalars, some algorithms have already been proposed regarding specific applications, and a first rigorous convergence analysis has been performed in [M. Donatelli et al., Numer. Linear Algebra Appl. 28, No. 4, e2356, 20 p. (2021; Zbl 07396240)]. However, with the existent symbol-based theoretical tools, it is still not possible to prove the convergence of many multigrid methods known in the literature. This paper aims to generalize the previous results, giving more general sufficient conditions on the symbol of the grid transfer operators. In particular, we treat matrix-valued trigonometric polynomials which can be nondiagonalizable and singular at all points, and we express the new conditions in terms of the eigenvectors associated with the ill-conditioned subspace. Moreover, we extend the analysis to the V-cycle method, proving a linear convergence rate under stronger conditions, which resemble those given in the scalar case. In order to validate our theoretical findings, we present a classical block structured problem stemming from an FEM approximation of a second order differential problem. We focus on two multigrid strategies that use the geometric and the standard bisection grid transfer operators and prove that both fall into the category of projectors satisfying the proposed conditions. In addition, using a tensor product argument, we provide a strategy to construct efficient V-cycle procedures in the block multilevel setting.

MSC:

65F10 Iterative numerical methods for linear systems
15B05 Toeplitz, Cauchy, and related matrices
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs

Citations:

Zbl 07396240

References:

[1] A. Aricò and M. Donatelli, A \(V\)-cycle multigrid for multilevel matrix algebras: Proof of optimality, Numer. Math., 105 (2007), pp. 511-547. · Zbl 1114.65033
[2] A. Aricò, M. Donatelli, and S. Serra-Capizzano, V-cycle optimal convergence for certain (multilevel) structured linear systems, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 186-214, https://doi.org/10.1137/S0895479803421987. · Zbl 1105.65322
[3] R. Bhatia, Matrix Analysis, Grad. Texts in Math. 169, Springer-Verlag, New York, 1997.
[4] D. Braess, Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory, 3rd ed., Cambridge University Press, Cambridge, UK, 2007; translated from the German by L. L. Schumaker. · Zbl 1180.65146
[5] D. Braess, Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics, Cambridge University Press, Cambridge, UK, 2007. · Zbl 1118.65117
[6] A. Brandt, Rigorous quantitative analysis of multigrid, I. Constant coefficients two-level cycle with \(L_2\)-norm, SIAM J. Numer. Anal., 31 (1994), pp. 1695-1730, https://doi.org/10.1137/0731087. · Zbl 0817.65126
[7] W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, 2nd ed., SIAM, Philadelphia, 2000, https://doi.org/10.1137/1.9780898719505. · Zbl 0958.65128
[8] R. H. Chan, Q.-S. Chang, and H.-W. Sun, Multigrid method for ill-conditioned symmetric Toeplitz systems, SIAM J. Sci. Comput., 19 (1998), pp. 516-529, https://doi.org/10.1137/S1064827595293831. · Zbl 0916.65029
[9] V. Del Prete, F. Di Benedetto, M. Donatelli, and S. Serra-Capizzano, Symbol approach in a signal-restoration problem involving block Toeplitz matrices, J. Comput. Appl. Math., 272 (2014), pp. 399-416. · Zbl 1294.15020
[10] M. Donatelli, A multigrid for image deblurring with Tikhonov regularization, Numer. Linear Algebra Appl., 12 (2005), pp. 715-729. · Zbl 1164.68445
[11] M. Donatelli, An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 179-197. · Zbl 1240.65353
[12] M. Donatelli, P. Ferrari, I. Furci, D. Sesana, and S. Serra-Capizzano, Multigrid methods for block-Toeplitz linear systems: Convergence analysis and applications, Numer. Linear Algebra Appl., 28 (2021) e2356. · Zbl 07396240
[13] P. Ferrari, Toeplitz and Block-Toeplitz Structures with Variants: From the Spectral Analysis to Preconditioning and Multigrid Methods Using a Symbol Approach, Ph.D. Thesis, Insubria University, 2020.
[14] P. Ferrari, R. I. Rahla, C. Tablino-Possio, S. Belhaj, and S. Serra-Capizzano, Multigrid for \(\mathbb{Q}_k\) finite element matrices using a (block) Toeplitz symbol approach, Mathematics, 8 (2020), 5.
[15] G. Fiorentino and S. Serra, Multigrid methods for Toeplitz matrices, Calcolo, 28 (1991), pp. 283-305 (1992). · Zbl 0778.65021
[16] G. Fiorentino and S. Serra, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM J. Sci. Comput., 17 (1996), pp. 1068-1081, https://doi.org/10.1137/S1064827594271512. · Zbl 0858.65039
[17] C. Garoni and S. Serra-Capizzano, Generalized Locally Toeplitz Sequences: Theory and Applications. Vol. II, Springer, Cham, 2018. · Zbl 1448.47004
[18] C. Garoni, S. Serra-Capizzano, and D. Sesana, Spectral analysis and spectral symbol of \(d\)-variate \(\Bbb{Q}_p\) Lagrangian FEM stiffness matrices, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1100-1128, https://doi.org/10.1137/140976480. · Zbl 1321.65173
[19] G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins Ser. Math. Sci. 3, Johns Hopkins University Press, Baltimore, MD, 1983. · Zbl 0559.65011
[20] W. Hackbusch, Multigrid Methods and Applications, Springer Ser. Comput. Math. 4, Springer-Verlag, Berlin, 1985. · Zbl 0595.65106
[21] P. Hemker, On the order of prolongations and restrictions in multigrid procedures, J. Comput. Appl. Math., 32 (1990), pp. 423-429. · Zbl 0717.65098
[22] T. Huckle and J. Staudacher, Multigrid methods for block Toeplitz matrices with small size blocks, BIT, 46 (2006), pp. 61-83. · Zbl 1103.65035
[23] T. K. Huckle, Compact Fourier analysis for designing multigrid methods, SIAM J. Sci. Comput., 31 (2008), pp. 644-666, https://doi.org/10.1137/070702564. · Zbl 1186.65037
[24] T. Kato, Perturbation Theory for Linear Operators, 2nd ed., Grundlehren Math. Wiss. 132, Springer-Verlag, Berlin, New York, 1976. · Zbl 0342.47009
[25] A. Napov and Y. Notay, When does two-grid optimality carry over to the V-cycle?, Numer. Linear Algebra Appl., 17 (2010), pp. 273-290. · Zbl 1240.65357
[26] A. Napov and Y. Notay, Smoothing factor, order of prolongation and actual multigrid convergence, Numer. Math., 118 (2011), pp. 457-483. · Zbl 1227.65122
[27] R. I. Rahla, S. Serra-Capizzano, and C. Tablino-Possio, Spectral analysis of \(\mathbb{P}_k\) finite element matrices in the case of Friedrichs-Keller triangulations via generalized locally Toeplitz technology, Numer. Linear Algebra Appl., 27 (2020), e2302. · Zbl 1538.65545
[28] F. Rellich, Perturbation Theory of Eigenvalue Problems, Gordon and Breach Science, New York, London, Paris, 1969. · Zbl 0181.42002
[29] J. W. Ruge and K. Stüben, Algebraic multigrid, in Multigrid Methods, Frontiers Appl. Math. 3, SIAM, Philadelphia, 1987, pp. 73-130, https://doi.org/10.1137/1.9781611971057.ch4.
[30] S. Serra-Capizzano, Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences, Numer. Math., 92 (2002), pp. 433-465. · Zbl 1013.65026
[31] S. Serra-Capizzano, Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear, Linear Algebra Appl., 343 (2002), pp. 303-319. · Zbl 1001.65041
[32] S. Serra-Capizzano and C. Tablino-Possio, Multigrid methods for multilevel circulant matrices, SIAM J. Sci. Comput., 26 (2004), pp. 55-85, https://doi.org/10.1137/S1064827501388509. · Zbl 1079.65033
[33] H.-W. Sun, X.-Q. Jin, and Q.-S. Chang, Convergence of the multigrid method for ill-conditioned block Toeplitz systems, BIT, 41 (2001), pp. 179-190. · Zbl 0991.65033
[34] U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, San Diego, CA, 2001. · Zbl 0976.65106
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.