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

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.