Generalized grid transfer operators for multigrid methods applied on Toeplitz matrices

详细信息    查看全文

• 作者：Matthias Bolten ; Marco Donatelli ; Thomas Huckle…
• 关键词：Multigrid methods ; Toeplitz matrices ; Grid transfer operators ; 15B05 ; 65F10 ; 65N22 ; 65N55
• 刊名：BIT Numerical Mathematics
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：55
• 期：2
• 页码：341-366
• 全文大小：783 KB
• 参考文献：1.Aric貌, A., Donatelli, M.: A V-cycle multigrid for multilevel matrix algebras: proof of optimality. Numer. Math. 105, 511鈥?47 (2007)View Article MATH MathSciNet
  2.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鈥?14 (2004)View Article MATH MathSciNet
  3.Bakhvalov, N.S.: On the convergence of a relaxation method with natural constraints on the elliptic operator. USSR Comput. Math. Math. Phys. 6, 101鈥?35 (1966)View Article
  4.Bolten, M., Donatelli, M., Huckle, T.: Analysis of smoothed aggregation multigrid methods based on Toeplitz matrices. Preprint BUW-IMACM 13/10, Bergische Universit盲t Wuppertal
  5.Braess, D.: Towards algebraic multigrid for elliptic problems of second order. Computing 55, 379鈥?93 (1995)View Article MATH MathSciNet
  6.Brandt, A.: Multi-level adaptive solutions to boundary-value problems. Math. Comp. 31(138), 333鈥?90 (1977)View Article MATH MathSciNet
  7.Brandt, A.: Rigorous quantitative analysis of multigrid, I: constant coefficients two-level cycle with \(L_2\) -norm. SIAM J. Numer. Anal. 31, 1695鈥?730 (1994)View Article MATH MathSciNet
  8.Chan, R.H., Chang, Q.S., Sun, H.W.: Multigrid method for ill-conditioned symmetric Toeplitz systems. SIAM J. Sci. Comput. 19(2), 516鈥?29 (1998)View Article MATH MathSciNet
  9.Chan, R.H., Ng, M.K.: Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38(3), 427鈥?82 (1996)View Article MATH MathSciNet
  10.Cheng, L., Wang, H., Zhang, Z.: The solution of ill-conditioned symmetric Toeplitz systems via two-grid and wavelet methods. Comput. Math. Appl. 46(5鈥?), 793鈥?04 (2003)View Article MATH MathSciNet
  11.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鈥?97 (2010)MATH MathSciNet
  12.Fedorenko, R.P.: The speed of convergence of one iterative process. USSR Compt. Math. Math. Phys. 4(3), 227鈥?35 (1964)View Article
  13.Fiorentino, G., Serra, S.: Multigrid methods for Toeplitz matrices. Calcolo 28, 238鈥?05 (1991)View Article MathSciNet
  14.Fiorentino, G., Serra, S.: Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions. SIAM J. Sci. Comput. 17(5), 1068鈥?081 (1996)View Article MATH MathSciNet
  15.Hackbusch, W.: Convergence of multi-grid iterations applied to difference equations. Math. Comp. 34, 425鈥?40 (1980)MATH MathSciNet
  16.Hackbusch, W.: On the convergence of multi-grid iterations. Beitr盲ge Numer. Math. 9, 213鈥?39 (1981)MATH
  17.Hackbusch, W.: Multi-grid convergence theory. In: Hackbusch, W., Trottenberg, U. (eds.) Multigrid methods. Lecture Notes in Mathematics, vol. 960, pp. 177鈥?19. Springer, Berlin (1982)View Article
  18.Hemker, P.W.: On the order of prolongations and restrictions in multigrid procedures. J. Comput. Appl. Math. 32, 423鈥?29 (1990)View Article MATH MathSciNet
  19.Huckle, T., Staudacher, J.: Multigrid preconditioning and Toeplitz matrices. Electron. Trans. Numer. Anal. 13, 82鈥?05 (2002)MathSciNet
  20.McCormick, S.F.: Multigrid methods for variational problems: general theory for the V-cycle. SIAM J. Numer. Anal. 22(4), 634鈥?43 (1985)View Article MATH MathSciNet
  21.McCormick, S.F., Ruge, J.W.: Multigrid methods for variational problems. SIAM J. Numer. Anal. 19(5), 924鈥?29 (1982)View Article MATH MathSciNet
  22.Napov, A., Notay, Y.: Smoothing factor, order of prolongation and actual multigrid convergence. Numer. Math. 118, 457鈥?83 (2011)View Article MATH MathSciNet
  23.Ruge, J.W., St眉ben, K.: Algebraic multigrid. In: McCormick, S.F. (ed.) Multigrid methods, Frontiers Appl. Math., vol. 3, pp. 73鈥?30. SIAM, Philadelphia (1987)
  24.Serra, S.: Multi-iterative methods. Comput. Math. Appl. 26(4), 65鈥?7 (1993)View Article MATH MathSciNet
  25.Serra-Capizzano, S.: Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix sequences. Numer. Math. 92, 433鈥?65 (2002)View Article MATH MathSciNet
  26.Serra-Capizzano, S., Tablino-Possio, C.: Multigrid methods for multilevel circulant matrices. SIAM J. Sci. Comput. 26(1), 55鈥?5 (2004)View Article MATH MathSciNet
  27.Trottenberg, U., Oosterlee, C., Sch眉ller, A.: Multigrid. Academic Press, San Diego (2001)MATH
  28.Tyrtyshnikov, E.: A unifying approach to some old and new theorems on preconditioning and clustering. Linear Algebra Appl. 232, 1鈥?3 (1996)View Article MATH MathSciNet
  29.Vanek, P., Mandel, J., Brezina, M.: Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing 56, 179鈥?96 (1996)View Article MATH MathSciNet
  30.Wienands, R., Joppich, W.: Practical Fourier analysis for multigrid methods, Numerical Insights, vol. 4. Chapman & Hall/CRC, Boca Raton (2005)
  31.Yavneh, I.: Coarse-grid correction for nonelliptic and singular pertubation problems. SIAM J. Sci. Comput. 19(5), 1682鈥?699 (1998)View Article MATH MathSciNet
  
• 作者单位：Matthias Bolten (1)
  Marco Donatelli (2)
  Thomas Huckle (3)
  Christos Kravvaritis (4)
  
  1. Department of Mathematics and Science, University of Wuppertal, 42097聽, Wuppertal, Germany
  2. Dipartimento di Scienza e Alta Tecnologia, Universit脿 dell鈥橧nsubria, Via Valleggio 11, 22100聽, Como, Italy
  3. Department of Informatics, Technical University of Munich, Boltzmannstr. 3, 85748聽, Garching, Germany
  4. Department of Mathematics, University of Athens, Panepistimioupolis, 157 84聽, Athens, Greece
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Computational Mathematics and Numerical Analysis
  Numeric Computing
  Mathematics
  
• 出版者：Springer Netherlands
• ISSN：1572-9125

文摘

In this paper we discuss classical sufficient conditions to be satisfied from the grid transfer operators in order to obtain optimal two-grid and V-cycle multigrid methods utilizing the theory for Toeplitz matrices. We derive relaxed conditions that allow the construction of special grid transfer operators that are computationally less expensive while preserving optimality. This is particularly useful when the generating symbol of the system matrix has a zero of higher order, like in the case of higher order PDEs. These newly derived conditions allow the use of rank deficient grid transfer operators. In this case the use of a pre-relaxation iteration that is lacking the smoothing property is proposed. Combining these pre-relaxations with the new rank deficient grid transfer operators yields a substantial reduction of the convergence rate and of the computational cost at each iteration compared with the classical choice for Toeplitz matrices. The proposed strategy, i.e. a rank deficient grid transfer operator plus a specific pre-relaxation, is applied to linear systems whose system matrix is a Toeplitz matrix where the generating symbol is a high-order polynomial. The necessity of using high-order polynomials as generating symbols for the grid transfer operators usually destroys the Toeplitz structure on the coarser levels. Therefore, we discuss some effective and computational cheap coarsening strategies found in the literature. In particular, we present numerical results showing near-optimal behavior while keeping the Toeplitz structure on the coarser levels.