Parallel Multigrid Smoothing: Polynomial versus Gauss-Seidel

Mark Adams

MS 9217, Sandia National Laboratories, PO Box 969, Livermore, Ca 94551

Marian Brezina

Dept. of Applied Math., Univ. of Colorado at Boulder, Boulder, CO 80309-0526

Jonathan Hu

MS 9217, Sandia National Laboratories, PO Box 969, Livermore, Ca 94551

Ray Tuminaro

MS 9217, Sandia National Laboratories, PO Box 969, Livermore, Ca 94551


Abstract

We discuss the computational advantages of polynomial smoothers within parallel multigrid algorithms. Two specific polynomials are considered: Chebyshev and MLS. Both polynomials are described along with simple methods for estimating needed eigenvalues. The advantages of polynomial smoothing over traditional smoothers such as Gauss-Seidel (parallel multicolor Gauss-Seidel and processor based Gauss-Seidel) are illustrated on several applications: Poisson, elasticity, and eddy current approximations to Maxwell's Equations. While parallel computers are the main motivation, we also show that polynomial smoothers are often surprisingly competitive with Gauss-Seidel smoothers on serial machines.