ANU Computer Science Technical Reports

TR-CS-97-20

M. Hegland, S. Roberts, and I. Altas.
Finite element thin plate splines for surface fitting.
November 1997.

[POSTSCRIPT (340274 bytes)] [PDF (679585 bytes)] [EPrints archive]

Abstract: Faster hardware in principle allows the solution of larger problems. The performance gain is reduced, however, if non-scalable algorithms are used. Thin plate smoothing splines have excellent mathematical properties, however, they do involve the solution of dense linear systems which requires at least O(n^2) operations as all the matrix elements have to be accessed where n is the number of data points. Thus in general thin plate smoothing splines are not scalable. Recent work by Beatson, Newsam and Powell have addressed this by using multipole methods. An alternative approach is given here which is based on non-conforming finite elements. This new method allows the application of standard finite elements and is scalable. It is seen that for a zero smoothing parameter one obtains finite element surface fitting and for nonzero smoothing parameter one gets good approximations of the thin plate smoothing spline. The finite element smoothing spline method is applied to data mining where it is essential that extremely large problems can be solved. We will also examine some algorithms to solve the saddle point problem arising from the non-conforming finite elements.

Technical Reports <Technical-DOT-Reports-AT-cs-DOT-anu.edu.au>

Last modified: Tue May 31 12:56:00 EST 2011