Skip to main content
Top
Published in: BIT Numerical Mathematics 2/2015

01-06-2015

Generalized grid transfer operators for multigrid methods applied on Toeplitz matrices

Authors: Matthias Bolten, Marco Donatelli, Thomas Huckle, Christos Kravvaritis

Published in: BIT Numerical Mathematics | Issue 2/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Aricò, A., Donatelli, M.: A V-cycle multigrid for multilevel matrix algebras: proof of optimality. Numer. Math. 105, 511–547 (2007)CrossRefMATHMathSciNet Aricò, A., Donatelli, M.: A V-cycle multigrid for multilevel matrix algebras: proof of optimality. Numer. Math. 105, 511–547 (2007)CrossRefMATHMathSciNet
2.
go back to reference 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)CrossRefMATHMathSciNet 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)CrossRefMATHMathSciNet
3.
go back to reference Bakhvalov, N.S.: On the convergence of a relaxation method with natural constraints on the elliptic operator. USSR Comput. Math. Math. Phys. 6, 101–135 (1966)CrossRef Bakhvalov, N.S.: On the convergence of a relaxation method with natural constraints on the elliptic operator. USSR Comput. Math. Math. Phys. 6, 101–135 (1966)CrossRef
4.
go back to reference 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 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
7.
go back to reference Brandt, A.: Rigorous quantitative analysis of multigrid, I: constant coefficients two-level cycle with \(L_2\)-norm. SIAM J. Numer. Anal. 31, 1695–1730 (1994)CrossRefMATHMathSciNet Brandt, A.: Rigorous quantitative analysis of multigrid, I: constant coefficients two-level cycle with \(L_2\)-norm. SIAM J. Numer. Anal. 31, 1695–1730 (1994)CrossRefMATHMathSciNet
8.
go back to reference Chan, R.H., Chang, Q.S., Sun, H.W.: Multigrid method for ill-conditioned symmetric Toeplitz systems. SIAM J. Sci. Comput. 19(2), 516–529 (1998)CrossRefMATHMathSciNet Chan, R.H., Chang, Q.S., Sun, H.W.: Multigrid method for ill-conditioned symmetric Toeplitz systems. SIAM J. Sci. Comput. 19(2), 516–529 (1998)CrossRefMATHMathSciNet
10.
go back to reference 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–6), 793–804 (2003)CrossRefMATHMathSciNet 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–6), 793–804 (2003)CrossRefMATHMathSciNet
11.
go back to reference 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)MATHMathSciNet 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)MATHMathSciNet
12.
go back to reference Fedorenko, R.P.: The speed of convergence of one iterative process. USSR Compt. Math. Math. Phys. 4(3), 227–235 (1964)CrossRef Fedorenko, R.P.: The speed of convergence of one iterative process. USSR Compt. Math. Math. Phys. 4(3), 227–235 (1964)CrossRef
14.
go back to reference 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)CrossRefMATHMathSciNet 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)CrossRefMATHMathSciNet
15.
go back to reference Hackbusch, W.: Convergence of multi-grid iterations applied to difference equations. Math. Comp. 34, 425–440 (1980)MATHMathSciNet Hackbusch, W.: Convergence of multi-grid iterations applied to difference equations. Math. Comp. 34, 425–440 (1980)MATHMathSciNet
16.
go back to reference Hackbusch, W.: On the convergence of multi-grid iterations. Beiträge Numer. Math. 9, 213–239 (1981)MATH Hackbusch, W.: On the convergence of multi-grid iterations. Beiträge Numer. Math. 9, 213–239 (1981)MATH
17.
go back to reference Hackbusch, W.: Multi-grid convergence theory. In: Hackbusch, W., Trottenberg, U. (eds.) Multigrid methods. Lecture Notes in Mathematics, vol. 960, pp. 177–219. Springer, Berlin (1982)CrossRef Hackbusch, W.: Multi-grid convergence theory. In: Hackbusch, W., Trottenberg, U. (eds.) Multigrid methods. Lecture Notes in Mathematics, vol. 960, pp. 177–219. Springer, Berlin (1982)CrossRef
18.
19.
go back to reference Huckle, T., Staudacher, J.: Multigrid preconditioning and Toeplitz matrices. Electron. Trans. Numer. Anal. 13, 82–105 (2002)MathSciNet Huckle, T., Staudacher, J.: Multigrid preconditioning and Toeplitz matrices. Electron. Trans. Numer. Anal. 13, 82–105 (2002)MathSciNet
20.
go back to reference McCormick, S.F.: Multigrid methods for variational problems: general theory for the V-cycle. SIAM J. Numer. Anal. 22(4), 634–643 (1985)CrossRefMATHMathSciNet McCormick, S.F.: Multigrid methods for variational problems: general theory for the V-cycle. SIAM J. Numer. Anal. 22(4), 634–643 (1985)CrossRefMATHMathSciNet
22.
23.
go back to reference Ruge, J.W., Stüben, K.: Algebraic multigrid. In: McCormick, S.F. (ed.) Multigrid methods, Frontiers Appl. Math., vol. 3, pp. 73–130. SIAM, Philadelphia (1987) Ruge, J.W., Stüben, K.: Algebraic multigrid. In: McCormick, S.F. (ed.) Multigrid methods, Frontiers Appl. Math., vol. 3, pp. 73–130. SIAM, Philadelphia (1987)
25.
go back to reference Serra-Capizzano, S.: Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix sequences. Numer. Math. 92, 433–465 (2002)CrossRefMATHMathSciNet Serra-Capizzano, S.: Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix sequences. Numer. Math. 92, 433–465 (2002)CrossRefMATHMathSciNet
26.
go back to reference Serra-Capizzano, S., Tablino-Possio, C.: Multigrid methods for multilevel circulant matrices. SIAM J. Sci. Comput. 26(1), 55–85 (2004)CrossRefMATHMathSciNet Serra-Capizzano, S., Tablino-Possio, C.: Multigrid methods for multilevel circulant matrices. SIAM J. Sci. Comput. 26(1), 55–85 (2004)CrossRefMATHMathSciNet
27.
go back to reference Trottenberg, U., Oosterlee, C., Schüller, A.: Multigrid. Academic Press, San Diego (2001)MATH Trottenberg, U., Oosterlee, C., Schüller, A.: Multigrid. Academic Press, San Diego (2001)MATH
28.
go back to reference Tyrtyshnikov, E.: A unifying approach to some old and new theorems on preconditioning and clustering. Linear Algebra Appl. 232, 1–43 (1996)CrossRefMATHMathSciNet Tyrtyshnikov, E.: A unifying approach to some old and new theorems on preconditioning and clustering. Linear Algebra Appl. 232, 1–43 (1996)CrossRefMATHMathSciNet
29.
go back to reference Vanek, P., Mandel, J., Brezina, M.: Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing 56, 179–196 (1996)CrossRefMATHMathSciNet Vanek, P., Mandel, J., Brezina, M.: Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing 56, 179–196 (1996)CrossRefMATHMathSciNet
30.
go back to reference Wienands, R., Joppich, W.: Practical Fourier analysis for multigrid methods, Numerical Insights, vol. 4. Chapman & Hall/CRC, Boca Raton (2005) Wienands, R., Joppich, W.: Practical Fourier analysis for multigrid methods, Numerical Insights, vol. 4. Chapman & Hall/CRC, Boca Raton (2005)
31.
go back to reference Yavneh, I.: Coarse-grid correction for nonelliptic and singular pertubation problems. SIAM J. Sci. Comput. 19(5), 1682–1699 (1998)CrossRefMATHMathSciNet Yavneh, I.: Coarse-grid correction for nonelliptic and singular pertubation problems. SIAM J. Sci. Comput. 19(5), 1682–1699 (1998)CrossRefMATHMathSciNet
Metadata
Title
Generalized grid transfer operators for multigrid methods applied on Toeplitz matrices
Authors
Matthias Bolten
Marco Donatelli
Thomas Huckle
Christos Kravvaritis
Publication date
01-06-2015
Publisher
Springer Netherlands
Published in
BIT Numerical Mathematics / Issue 2/2015
Print ISSN: 0006-3835
Electronic ISSN: 1572-9125
DOI
https://doi.org/10.1007/s10543-014-0512-2

Other articles of this Issue 2/2015

BIT Numerical Mathematics 2/2015 Go to the issue

Premium Partner