Relaxation schemes for Chebyshev spectral multigrid methods

Yimin Kang and Scott R. Fulton

Department of Mathematics and Computer Science, Clarkson University, Potsdam, NY 13699-5815


For problems in bounded domains with nonperiodic boundary conditions, Chebyshev spectral discretizations give exponential convergence for smooth solutions. Although Chebyshev transforms can be computed quickly using FFTs, solving implicit Chebyshev equations efficiently is more difficult, since the matrices are full (due to the global dependence of the discretization). Chebyshev spectral multigrid (CSMG) methods have been proposed, but existing relaxation schemes are complicated, requiring the approximate inversion of a finite-difference approximation on the nonuniform Chebyshev-collocation grid for each relaxation sweep.

This paper will introduce two simpler relaxation schemes for CSMG methods. The first, based on pointwise preconditioned Richardson iteration, works well in one dimension; the second, based on line relaxation, works well in two dimensions. We will present two versions of the latter (using spectral and finite-difference approximations along the lines), both of which give multigrid smoothing factors of better than 0.5 per sweep for the problem $\lambda^2 u - \triangle u = f$ in two dimensions with Dirichlet boundary conditions. We will present results from smoothing, two-grid, and multigrid analyses, along with computational results and comparisons to existing CSMG and matrix diagonalization techniques. We also plan to discuss extensions to problems with Neumann and mixed boundary conditions and non-constant coefficients.