Multigrid and multilevel methods for orthogonal spline collocation problems

Bernard Bialecki

Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506, U.S.A.

Max Dryja
Faculty of Informatics, Warsaw University, Banacha 2, 02-097 Warsaw, Poland


Multigrid and multilevel methods are well-developed and thoroughly analyzed techniques for solving discrete problems resulting from the finite difference and finite element Galerkin approximations of elliptic boundary value problems. Typically these methods are discussed in the context of the second order finite difference approximation and the finite element Galerkin approximation with piecewise linear elements. In this paper, the applicability of the multigrid and multilevel approaches is examined for the solution of discrete problems arising when orthogonal spline collocation with piecewise Hermite bicubics is used to approximate the Dirichlet problem for Poisson's equation on a rectangle. Orthogonal spline collocation does not require the computation of any integrals and in the case of piecewise Hermite bicubics it produces an approximate solution which is fourth order accurate.

Throughout the paper, piecewise Hermite bicubic orthogonal spline collocation problem on a fine rectangular grid is considered along with a sequence of coarser rectangular grids, each of which is obtained by doubling the mesh size of the previous grid. In the first part of the paper, we study the classical V-cycle method in which a few iterations of the Richardson method are used on each grid to solve approximately the residual equation. Employing Fourier mode analysis, we show that the Richardson method damps the high-frequency error components by a smoothing factor that is independent of the grid mesh size. Suitable choices of interpolation and restriction operators transferring piecewise Hermite bicubics from coarse to fine and from fine to coarse grids are also examined.

In the second part of the paper we discuss the solution of piecewise Hermite bicubic orthogonal spline collocation problems by the method of Bramble Pasciak and Xu (PBX), in which a simple parallel multilevel preconditioner is used in conjunction with the conjugate gradient method. In contrast to the standard V-cycle method in which each iteration step is inherently sequential, the PBX method is well suited for parallel computation. The PBX method, which can be regarded as a variant of multilevel additive Schwarz algorithm, is analyzed using a variational framework developed by Dryja and Widlund. We show that the convergence factor of the PBX method for piecewise Hermite bicubic orthogonal spline collocation is independent of the grid mesh size and study its dependence on the number of levels.

Theoretical considerations for the classical V-cycle method as well as the PBX method are illustrated by numerical results. Implementation aspects of both methods are also discussed.