Comparison of nested grid and V-cycle multigrid for calculating finite difference smoothing splines.
by
Penny A. Hancock
Centre for Resource and Environmental Studies, Australian National University
Coauthors: M.F.Hutchinson (CRES, ANU)

Multigrid methods have often been viewed as ineffective in applications to the biharmonic equation, which arises in the solution of two dimensional finite difference smoothing splines, yet nested grid methods have been used successfully for some time (Hutchinson 1989a, Smith and Wessel 1990). This paper compares the computational efficiency of nested grid and V-cycle multigrid schemes when applied to a finite difference approximation to the thin plate smoothing spline equations in one dimension. The smoothing parameter for the corresponding analytic solution of the thin plate smoothing spline equations was used in this study, to allow assessment of the multigrid methods. Successive over-relaxation (SOR) was chosen as the underlying iterative method. Convergence for both schemes was dictated by a common tolerance, which was based on a comparison of the solution estimate with the analytic solution. The nested grid scheme converged to this tolerance in a total of 60 SOR iterations across six grid levels (10 iterations per grid level). This was significantly faster than the V-cycle scheme, which required a total of 6768 SOR iterations across 6 grid levels to converge to the same tolerance. Both methods yielded accurate estimates of the generalised cross-validation (GCV) and the trace of the influence matrix associated with the analytic solution, as estimated by the stochastic estimator of Hutchinson (1989b). The results from this study provide a sound basis for using the nested grid scheme in further investigation of the finite difference solution of the thin plate smoothing spline equations.

References:

Hutchinson, M.F. 1989a. A new method for gridding elevation and streamline data with automatic removal of spurious pits. Journal of Hydrology 106: 211-232.

Hutchinson, M.F. 1989b. A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Communications in Statistics - Simulation and Computation 18: 1059-1076.

Smith, W.H.F. and Wessel, P. 1990. Gridding with continuous curvature. Geophysics 55: 293-305.

Date received: August 17, 1999

Copyright © 1999 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cadr-16.