Computational strategies for surface fitting using thin plate spline finite element methods

Daryl Matthew Kempthorne, Ian W Turner, John A Belward

Abstract


Thin plate spline finite element methods are used to fit a surface to an irregularly scattered dataset. The computational bottleneck for this algorithm is the solution of large, ill-conditioned systems of linear equations at each step of a generalised cross validation algorithm. Preconditioning techniques are investigated to accelerate the convergence of the solution of these systems using Krylov subspace methods. The preconditioners under consideration are block diagonal, block triangular and constraint preconditioners. The effectiveness of each of these preconditioners is examined on a sample dataset taken from a known surface. From our numerical investigation, constraint preconditioners appear to provide improved convergence for this surface fitting problem compared to block preconditioners.

References
  • M. Benzi and A. J. Wathen. Some preconditioning techniques for saddle point problems. In Model Order Reduction: Theory, Research Aspects and Applications, volume 13 of Mathematics in Industry, pages 195--211. Springer Berlin Heidelberg, 2008. doi:10.1007/978-3-540-78841-6_10.
  • Michele Benzi, Gene H. Golub, and J. Liesen. Numerical solution of saddle point problems. Acta Numer., 14:1--137, 2005. doi:10.1017/S0962492904000212.
  • H. S. Dollar, N. I. M. Gould, M. Stoll, and A. J. Wathen. Preconditioning Saddle-point Systems with Applications in Optimisation. SIAM J. Sci. Comput., 31(1):249--270, 2010. doi:10.1137/080727129.
  • C. Greif, G. Golub, and J. Varah. Augmented Lagrangian Techniques for Solving Saddle Point Linear Systems. SIAM J. Matrix Anal. Appl., 2004. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.942.
  • C. Greif and D. Schotzau. Preconditioners for saddle point linear systems with highly singular (1,1) blocks. Electron. Trans. Numer. Anal., 22:114--121, 2006. http://www.emis.ams.org/journals/ETNA/vol.22.2006/pp114-121.dir/pp114-121.pdf.
  • Sabine Le Borne and Che Ngufor. An implicit approximate inverse preconditioner for saddle point problems. Electron. Trans. Numer. Anal., 37:173--188, 2012. http://www.emis.ams.org/journals/ETNA/vol.37.2010/pp173-188.dir/pp173-188.pdf.
  • Malcolm F. Murphy, Gene H. Golub, and Andrew J. Wathen. A note on preconditioning for indefinite linear systems. SIAM J. Sci. Comput., 21(6):1969--1972, December 1999. doi:10.1137/S1064827599355153.
  • C. C. Paige and M. A. Saunders. Solution of Sparse Indefinite Systems of Linear Equations. SIAM J. Numer. Anal., 12 (4):617--629, 1975. doi:10.1137/0712047.
  • S. Roberts, M. Hegland, and I. Altas. Approximation of a Thin Plate Spline Smoother using Continuous Piecewise Polynomial Functions. SIAM J. Numer. Anal., 1:208--234, 2003. doi:10.1137/S0036142901383296.
  • Y. Saad. Iterative Methods for Sparse Linear Systems. SIAM, 2nd edition, 2003.
  • Youcef Saad and Martin H Schultz. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., 7(3):856--869, July 1986. doi:10.1137/0907058.
  • Eric de Sturler and Jorg Liesen. Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems. part i: Theory. SIAM J. Sci. Comput., 26(5):1598--1619, May 2005. doi:10.1137/S1064827502411006.
  • G. Wahba. Spline Models for Observational Data. SIAM, 1990.
  • W. L. Winston. Operations Research: Applications and Algorithms. Thompson Brooks/Cole, 4th edition, 2004.

Keywords


preconditioning, krylov subspace, thin plate splines, surface fitting

Full Text:

PDF BIB


DOI: http://dx.doi.org/10.21914/anziamj.v54i0.6337



Remember, for most actions you have to record/upload into this online system
and then inform the editor/author via clicking on an email icon or Completion button.
ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.