×

Parallel multigrid smoothing: Polynomial versus Gauss–Seidel. (English) Zbl 1022.65030

Summary: Gauss-Seidel is often the smoother of choice within multigrid applications. In the context of unstructured meshes, however, maintaining good parallel efficiency is difficult with multiplicative iterative methods such as Gauss–Seidel. This leads us to consider alternative smoothers. We discuss the computational advantages of polynomial smoothers within parallel multigrid algorithms for positive definite symmetric systems.
Two particular polynomials are considered: Chebyshev and a multilevel specific polynomial. The advantages of polynomial smoothing over traditional smoothers such as Gauss–Seidel are illustrated on several applications: Poisson’s equation, thin-body elasticity, and eddy current approximations to Maxwell’s equations.
While parallelizing the Gauss–Seidel method typically involves a compromise between a scalable convergence rate and maintaining high flop rates, polynomial smoothers achieve parallel scalable multigrid convergence rates without sacrificing flop rates. We show that, although parallel computers are the main motivation, polynomial smoothers are often surprisingly competitive with Gauss–Seidel smoothers on serial machines.

MSC:

65F10 Iterative numerical methods for linear systems
65Y05 Parallel numerical computation
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
35Q80 Applications of PDE in areas other than physics (MSC2000)
35Q72 Other PDE from mechanics (MSC2000)

Software:

Wesseling; BoomerAMG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M.P. Adams, A distributed memory unstructured Gauss-Seidel algorithm for multigrid smoothers, in: ACM/IEEE Proceedings of SC01: High Performance Networking and Computing, 2001; M.P. Adams, A distributed memory unstructured Gauss-Seidel algorithm for multigrid smoothers, in: ACM/IEEE Proceedings of SC01: High Performance Networking and Computing, 2001
[2] M.F. Adams, J. Demmel, Parallel multigrid solver algorithms and implementations for 3D unstructured finite element problem, in: ACM/IEEE Proceedings of SC99: High Performance Networking and Computing, Portland, Oregon, November, 1999; M.F. Adams, J. Demmel, Parallel multigrid solver algorithms and implementations for 3D unstructured finite element problem, in: ACM/IEEE Proceedings of SC99: High Performance Networking and Computing, Portland, Oregon, November, 1999
[3] P. Bochev, C. Garasi, J. Hu, A. Robinson, R.T. Ro, An improved algebraic multigrid method for solving Maxwell’s equations, Sandia National Laboratories Technical Report # 2002-8222, 2003, to appear; P. Bochev, C. Garasi, J. Hu, A. Robinson, R.T. Ro, An improved algebraic multigrid method for solving Maxwell’s equations, Sandia National Laboratories Technical Report # 2002-8222, 2003, to appear
[4] Bochev, P.; Hu, J.; Robinson, A.; Tuminaro, R., Towards robust 3D Z-pinch simulations: discretization and fast solvers for magnetic diffusion in heterogeneous conductors, Elec. Trans. Numer. Anal., 15 (2003) · Zbl 1201.76041
[5] Brandt, A., Multi-level adaptive solutions to boundary-value problems, Math. Comput., 31, 333-390 (1977) · Zbl 0373.65054
[6] M. Brezina, Robust iterative solvers on unstructured meshes, Ph.D. Thesis, University of Colorado at Denver, Denver, CO, 1997, pp. 80217-83364; M. Brezina, Robust iterative solvers on unstructured meshes, Ph.D. Thesis, University of Colorado at Denver, Denver, CO, 1997, pp. 80217-83364
[7] M. Brezina, SAMISdat(AMG) version 0.98-User’s Guide, 2002; M. Brezina, SAMISdat(AMG) version 0.98-User’s Guide, 2002
[8] M. Brezina, C.I. Heberton, J. Mandel, P. Vaněk, An iterative method with convergence rate chosen a priori, UCD/CCM Report 140, Center for Computational Mathematics, University of Colorado at Denver, February 1999. Available from http://www-ath.cudenver.edu/ccmreports/repl40.ps.gz; M. Brezina, C.I. Heberton, J. Mandel, P. Vaněk, An iterative method with convergence rate chosen a priori, UCD/CCM Report 140, Center for Computational Mathematics, University of Colorado at Denver, February 1999. Available from http://www-ath.cudenver.edu/ccmreports/repl40.ps.gz
[9] Briggs, W. L.; Henson, V. E.; McCormick, S., A Multigrid Tutorial (2000), SIAM: SIAM Philadelphia · Zbl 0958.65128
[10] Golub, G. H.; Loan, C. F.V., Matrix Computations (1996), Johns Hopkins University Press: Johns Hopkins University Press Baltimore
[11] Hackbusch, W., Multigrid Methods and Applications, Computational Mathematics, vol. 4 (1985), Springer: Springer Berlin · Zbl 0577.65118
[12] Hackbusch, W., Iterative Solution of Large Sparse Systems of Equations (1994), Springer: Springer New York
[13] V. Henson, U. Yang, BoomerAMG: A parallel algebraic multigrid solver and preconditioner, Technical Report UCRL-JC-139098, Lawrence Livermore National Laboratory, 2000; V. Henson, U. Yang, BoomerAMG: A parallel algebraic multigrid solver and preconditioner, Technical Report UCRL-JC-139098, Lawrence Livermore National Laboratory, 2000 · Zbl 0995.65128
[14] Hiptmair, R., Multigrid method for Maxwell’s equations, SIAM J. Numer. Anal., 36, 204-225 (1998) · Zbl 0922.65081
[15] Isaacson, E.; Keller, H. B., Analysis of Numerical Methods (1966), Wiley: Wiley New York · Zbl 0168.13101
[16] A. Jameson, T.J. Baker, Multigrid solution of the Euler equations for aircraft configurations, AIAA Paper No. 84-0093, 1984; A. Jameson, T.J. Baker, Multigrid solution of the Euler equations for aircraft configurations, AIAA Paper No. 84-0093, 1984
[17] A. Jameson, W. Schmidt, E. Turkel, Numerical solution of the Euler equations by finite volume methods using Runge-Kutta time-stepping schemes, AIAA Paper No. 8I-1259, 1981; A. Jameson, W. Schmidt, E. Turkel, Numerical solution of the Euler equations by finite volume methods using Runge-Kutta time-stepping schemes, AIAA Paper No. 8I-1259, 1981
[18] Reitzinger, S.; Schöberl, J., An algebraic multigrid method for finite element discretizations with edge elements, Numer. Linear Algebra Appl., 9, 223-238 (2002) · Zbl 1071.65170
[19] Stüben, K.; Trottenberg, U., Multigrid methods: fundamental algorithms, model problem analysis and applications, (Hackbusch, W.; Trottenberg, U., Multigrid Methods. Multigrid Methods, Lecture Notes in Mathematics, vol. 960 (1982), Springer: Springer Berlin), 1-176
[20] Trottenberg, U.; Oosterlee, C.; Schüller, A., Multigrid (2001), Academic Press: Academic Press London
[21] Vaněk, P.; Brezina, M.; Mandel, J., Convergence of algebraic multigrid based on smoothed aggregation, Numerische Mathematik, 88, 559-579 (2001) · Zbl 0992.65139
[22] Vaněk, P.; Mandel, J.; Brezina, M., Algebraic multigrid based on smoothed aggregation for second and fourth order problems, Computing, 56, 179-196 (1996) · Zbl 0851.65087
[23] Vaněk, P.; Brezina, M.; Tezaur, R., Two-grid method for linear elasticity on unstructured meshes, SIAM J. Sci. Comput., 21, 900-923 (1999) · Zbl 0952.65099
[24] Vaněk, P.; Mandel, J.; Brezina, M., Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, 179-196 (1996) · Zbl 0851.65087
[25] Varga, R. S., Matrix Iterative Analysis (1962), Prentice-Hall: Prentice-Hall Englewood Hills, NJ · Zbl 0133.08602
[26] Wesseling, P., An Introduction to Multigrid Methods (1992), Wiley: Wiley Chichester, Reprinted by www.MGNet.org · Zbl 0760.65092
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.