Efficient solution techniques for a finite element thin plate spline formulation. (English) Zbl 1318.65074
Summary: We present a new technique for solving the saddle point problem arising from a finite element based thin plate spline formulation. The solver uses the Sherman-Morrison-Woodbury formula to divide the domain into different regions depending on the properties of the data projection matrix. We analyse the conditioning of the resulting system on certain data distributions and use the results to develop effective preconditioners. We show our approach is efficient for a wide range of parameters by testing it on a number of different examples. Numerical results are given in one, two and three dimensions.
MSC:
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 35J25 | Boundary value problems for second-order elliptic equations |
| 65D07 | Numerical computation using splines |
| 65F08 | Preconditioners for iterative methods |
Keywords:
mixed finite elements; thin plate splines; saddle point problems; conditioning of matrices; preconditioning; Sherman-Morrison-Woodbury formula; numerical resultReferences:
| [1] | Axelsson, O., Lindskog, G.: On the rate of convergence of the preconditioned conjugate gradient method. Numerische Mathematik 48(5), 499-523 (1986). doi:10.1007/BF01389448 · Zbl 0564.65017 · doi:10.1007/BF01389448 |
| [2] | Beatson, R., Greengard, L.: A short course on fast multipole methods. In: Wavelets, Multilevel Methods and Elliptic PDEs, pp. 1-37. Oxford University Press, Oxford (1997) · Zbl 0882.65106 |
| [3] | Beatson, R., Newsam, G.: Fast evaluation of radial basis functions: I. Computers & Mathematics with Applications 24(12), 7-19 (1992). doi:10.1016/0898-1221(92)90167-G. http://www.sciencedirect.com/science/article/pii/089812219290167G · Zbl 0765.65021 |
| [4] | Beatson, R.K., Light, W.A., Billings, S.: Fast solution of the radial basis function interpolation equations: Domain decomposition methods. SIAM J. Sci. Comput. 22(5), 1717-1740 (2000). doi:10.1137/S1064827599361771 · Zbl 0982.65015 · doi:10.1137/S1064827599361771 |
| [5] | Beatson, R.K., Newsam, G.N.: Fast evaluation of radial basis functions: moment-based methods. SIAM J. Sci. Comput. 19(5), 1428-1449 (1998). doi:10.1137/S1064827595293569 · Zbl 0914.65005 · doi:10.1137/S1064827595293569 |
| [6] | Beatson, R.K., Powell, M.J.D., Tan, A.M.: Fast evaluation of polyharmonic splines in three dimensions. IMA J. Numer. Anal. 27, 427-450 (2006). doi:10.1093/imanum/drl027 · Zbl 1127.65011 · doi:10.1093/imanum/drl027 |
| [7] | Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1-137 (2005) · Zbl 1115.65034 · doi:10.1017/S0962492904000212 |
| [8] | Benzi, M., Wathen, A.J.: Some preconditioning techniques for saddle point problems. In: Model order reduction: theory, research aspects and applications, Math. Ind., vol. 13, pp. 195-211. Springer, Berlin (2008). doi:10.1007/978-3-540-78841-6_10 · Zbl 1152.65425 |
| [9] | Cherrie, J.B., Beatson, R.K., Newsam, G.N.: Fast evaluation of radial basis functions: methods for generalized multiquadrics in \[\backslash \text{ rr }\,\hat{\,}\,\backslash \]\rr^\protectn. Siam J. Sci. Comput. 23(5), 1549-1571 (2002) · Zbl 1009.65007 · doi:10.1137/S1064827500367609 |
| [10] | Duchon, J.: Splines minimizing rotation-invariant semi-norms in Sobolev spaces. In: Constructive Theory of Functions of Several Variables, Lecture Notes in Mathematics, vol. 571, pp. 85-100. Springer, Berlin (1977). http://www.springerlink.com/content/g27671q701166031/ · Zbl 0342.41012 |
| [11] | Hackbusch, W.: Elliptic Differential Equations, Springer Series in Computational Mathematics: Theory and Numerical Treatment, vol. 18. Springer, Berlin (1992) · Zbl 1205.35060 · doi:10.1007/978-3-642-11490-8 |
| [12] | Hutchinson, M.F.: A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Commun. Stat. Simul. Comput. 18(3), 1059-1076 (1989). http://www.tandfonline.com/toc/lssp20/18/3 · Zbl 0695.62113 |
| [13] | Jennings, A.: Influence of the eigenvalue spectrum on the convergence rate of the conjugate gradient method. IMA J. Appl. Math. 20(1), 61-72 (1977). doi:10.1093/imamat/20.1.61. http://imamat.oxfordjournals.org/content/20/1/61.abstract · Zbl 0364.65028 |
| [14] | Lu, L.Z., Pearce, C.E.M.: Some new bounds for singular values and eigenvalues of matrix products. Ann. Oper. Res. 98, 141-148 (2000) · Zbl 0979.15017 · doi:10.1023/A:1019200322441 |
| [15] | Riedel, K.S.: A Sherman Morrison Woodbury identity for rank augmenting matrices with application to centering. SIAM J. Math. Anal. 12(1), 80-95 (1991) |
| [16] | Roberts, S., Hegland, M., Altas, I.: Approximation of a thin plate spline smoother using continuous piecewise polynomial functions. SIAM J. Numer. Anal. 41(1), 208-234 (2003). http://epubs.siam.org/sinum/resource/1/sjnaam/v41/i1 · Zbl 1041.65019 |
| [17] | Roberts, S., Stals, L.: Discrete thin plate spline smoothing in 3D. In: J. Crawford, A.J. Roberts (eds.) In: Proceedings of 11th Computational Techniques and Applications Conference CTAC-2003, vol. 45, pp. C646-C659 (2004). http://anziamj.austms.org.au/V45/CTAC2003/Rob2/home.html (July 18, 2004) · Zbl 1063.65525 |
| [18] | Stals, L., Roberts, S.: Verifying convergence rates of discrete thin-plate splines in 3D. In: R. May, A.J. Roberts (eds.) In: Proceedings of 12th Computational Techniques and Applications Conference CTAC-2002, vol. 46, pp. C515-C529 (2005). http://anziamj.austms.org.au/V46/CTAC2004/home.html · Zbl 1116.65309 |
| [19] | Stals, L., Roberts, S.: Smoothing large data sets using discrete thin plate splines. Comput. Vis. Sci. 9, 185-195 (2006) · Zbl 1512.65026 · doi:10.1007/s00791-006-0033-x |
| [20] | Stals, L.; Roberts, S.; Barth, T. (ed.); Griebel, M. (ed.); Keyes, D. (ed.); Nieminen, R. (ed.); Roose, D. (ed.); Schlick, T. (ed.), Preconditioners for low order thin plate spline approximations, No. 60, 639-646 (2008), Berlin · Zbl 1139.65302 · doi:10.1007/978-3-540-75199-1_80 |
| [21] | Trottenberg, U., Oosterlee, C., Schüller, A.: Multigrid. Academic Press, Waltham (2001) · Zbl 0976.65106 |
| [22] | Wahba, G.: Spline Models for Observational Data, Series in Applied Mathematics, vol. 59, 1st edn. SIAM, Philadelphia (1990) · Zbl 0813.62001 · doi:10.1137/1.9781611970128 |
| [23] | Wang, B., Xi, B.: Some inequalities for singular values of matrix products. Linear Algebra Appl. 264, 109-115 (1997) · Zbl 0885.15012 · doi:10.1016/S0024-3795(97)00020-7 |
| [24] | Wendland, H.: Computational aspects of radial basis function approximation. In: K. Jetter, M.D. Buhmann, W. Haussmann, R. Schaback, J. Stckler (eds.) In: Topics in Multivariate Approximation and Interpolation, Studies in Computational Mathematics, vol. 12, pp. 231-256. Elsevier (2006). doi:10.1016/S1570-579X(06)80010-8. http://www.sciencedirect.com/science/article/pii/S1570579X06800108 · Zbl 1205.65044 |
| [25] | Wendland, H.: Scattered Data Approximation. Cambridge University Press, Cambridge (2010) · Zbl 1185.65022 · doi:10.1017/CBO9780511617539 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
