Abstract
Solutions to boundary value problems in geoscience where the boundary is the Earth’s surface can be constructed in terms of harmonic splines. These are localizing trial functions that make use of a reproducing kernel. Splines allow regional modeling or the improvement of a global model in a part of the Earth’s surface.
For certain cases of the reproducing kernels a fast matrix-vector multiplication using the fast multipole method (FMM) is available. The main idea of the fast multipole algorithm consists of two parts: First, the hierarchical decomposition of the three-dimensional computational domain into cubes. Second, an approximation instead of the actual kernel is used for the more distant points which allows to consider many distant points at once. The numerical effort of the matrix-vector multiplication becomes linear in reference to the number of points for a prescribed accuracy of the approximation of the reproducing kernel.
This fast multiplication is used in spline approximation for the solution of the occurring linear systems which also allows the treatment of noisy data requires the choice of a smoothing parameter. Several methods are presented which ideally automatically choose this parameter with and without prior knowledge of the noise level. Using a fast solution algorithm we no longer have access to the whole matrix or its singular values whose computation requires a much larger numerical effort. This situation must be reflected by the parameter choice methods.
Zusammenfassung
Lösungen zu Randwertproblemen aus den Geowissenschaften, bei denen die Randfläche durch die Erdoberfläche gegeben ist, können mittels harmonischer Splines konstruiert werden. Diese Splines sind lokalisierende Testfunktionen, die aus einem reproduzierenden Kern hervorgehen. Sie erlauben regionale Modelle sowie die lokale Verbesserung globaler Modelle in Teilen der Erdoberfläche.
In bestimmten Fällen dieser reproduzierenden Kerne ist eine schnelle Matrix-Vektor Multiplikation durch das schnelle Multipolverfahren (FMM) verfügbar. Die Kernidee des schnellen Multipolalgorithmus’ besteht aus zwei Teilen: Zum einen die hierarchische Unterteilung des dreidimensionalen Berechnungsgebiets in geschachtelte Würfel. Zum anderen wird eine Approximation anstelle des Kerns für weiter entfernte Punkte benutzt, die es erlaubt viele entfernte Punkte auf ein Mal zu betrachten. Der numerische Aufwand der Matrix-Vektor Multiplikation wird so linear bzgl. der Punkteanzahl bei einer vorgeschriebenen Genauigkeit der Approximation des reproduzierenden Kerns.
Diese schnelle Multiplikation wird bei der Spline-Approximation benutzt, um die auftretenden linearen Gleichungssysteme effizient zu lösen. Spline-Approximation erlaubt es auch verrauschte Daten zu nutzen, erfordert allerdings die Wahl eines Glättungsparameters. Verschiedene Verfahren werden präsentiert, die idealerweise automatisch diesen Parameter wählen – manche mit und manche ohne Kenntnis des Rauschlevels. Da ein schneller Lösungsalgorithmus für die linearen Gleichungssysteme benutzt wird, stehen dabei die gesamte Matrix oder gar ihre Singulärwerte, deren Berechnung einen viel höheren numerischen Aufwand erfordert, nicht zur Verfügung. Die Parameterwahlverfahren müssen diese Situation adäquat widerspiegeln.
This chapter is part of the series Handbuch der Geodäsie, volume “Mathematical Geodasy/ Mathematische Geodäsie”, edited by Willi Freeden, Kaiserslautern.
Similar content being viewed by others
References
Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions. Dover Publications, Inc., New York (1972)
Akaike, H.: Information theory and an extension of the maximum likelihood principle. In: Second International Symposium on Information Theory (Tsahkadsor, 1971), pp. 267–281. Akadémiai Kiadó, Budapest (1973)
Aronszajn, N.: Theory of reproducing kernels. Trans. Am. Math. Soc. 68, 337–404 (1950)
Bakushinskii, A.B.: Remarks on choosing a regularization parameter using the quasi-optimality and ratio criterion. U.S.S.R. Comput. Math. Math. Phys. 24, 181–182 (1984)
Bauer, F.: Some considerations concerning regularization and parameter choice algorithms. Inverse Prob. 23(2), 837–858 (2007)
Bauer, F., Gutting, M., Lukas, M.A.: Evaluation of parameter choice methods for regularization of ill-posed problems in geomathematics. In: Freeden, W., Nashed, M.Z., Sonar, T. (eds.) Handbook of Geomathematics, 2nd edn., pp. 1713–1774. Springer, Heidelberg (2015)
Bauer, F., Hohage, T.: A Lepskij-type stopping rule for regularized Newton methods. Inverse Prob. 21, 1975–1991 (2005)
Bauer, F., Kindermann, S.: Recent results on the quasi-optimality principle. J. Inverse Ill-Posed Prob. 17(1), 5–18 (2009)
Bauer, F., Lukas, M.A.: Comparing parameter choice methods for regularization of ill-posed problems. Math. Comput. Simul. 81(9), 1795–1841 (2011)
Becker, S.M.A.: Regularization of statistical inverse problems and the Bakushinkii veto. Inverse Prob. 27, 115010, 22pp (2011)
Biedenharn, L.C., Louck, J.D.: Angular Momentum in Quantum Physics (Theory and Application). Encyclopedia of Mathematics and Its Applications. Addison-Wesley, Reading (1981)
Blanchard, G., Mathé, P.: Discrepancy principle for statistical inverse problems with application to conjugate gradient iteration. Inverse Prob. 28, 115011, 23pp (2012)
Carrier, J., Greengard, L., Rokhlin, V.: A fast adaptive multipole algorithm for particle simulations. SIAM J. Sci. Stat. Comput. 9(4), 669–686 (1988)
Cheng, H., Greengard, L., Rokhlin, V.: A fast adaptive multipole algorithm in three dimensions. J. Comput. Phys. 155, 468–498 (1999)
Choi, C.H., Ivanic, J., Gordon, M.S., Ruedenberg, K.: Rapid and staple determination of rotation matrices between spherical harmonics by direct recursion. J. Chem. Phys. 111(19), 8825–8831 (1999)
Cummins, D.J., Filloon, T.G., Nychka, D.: Confidence intervals for nonparametric curve estimates: toward more uniform pointwise coverage. J. Am. Statist. Assoc. 96(453), 233–246 (2001)
Driscoll, J.R., Healy, D.M.: Computing Fourier transforms and convolutions on the 2-sphere. Adv. Appl. Math. 15, 202–250 (1994)
Edmonds, A.R.: Drehimpulse in der Quantenmechanik. Bibliographisches Institut, Mannheim (1964)
Engl, H.W., Gfrerer, H.: A posteriori parameter choice for general regularization methods for solving linear ill-posed problems. Appl. Numer. Math. 4(5), 395–417 (1988)
Engl, H.W., Hanke, H., Neubauer, A.: Regularization of Inverse Problems. Kluwer, Dordrecht (1996)
Epton, M.A., Dembart, B.: Multipole translation theory for the three-dimensional Laplace and Helmholtz equations. SIAM J. Sci. Comput. 16(4), 865–897 (1995)
Fengler, M.J.: Vector spherical harmonic and vector wavelet based non-linear Galerkin schemes for solving the incompressile Navier–Stokes equation on the sphere. Ph.D. thesis, Geomathematics Group, Department of Mathematics, University of Kaiserslautern, Shaker, Aachen (2005)
Fischer, D., Michel, V.: Sparse regularization of inverse gravimetry – case study: spatial and temporal mass variation in South America. Inverse Prob. 28, 065012, 34pp (2012)
Freeden, W.: On approximation by harmonic splines. Manuscripta Geod. 6, 193–244 (1981)
Freeden, W.: On spherical spline interpolation and approximation. Math. Method. Appl. Sci. 3, 551–575 (1981)
Freeden, W.: Interpolation and best approximation by harmonic spline functions. Boll. Geod. Sci. Aff. 1, 105–120 (1982)
Freeden, W.: On spline methods in geodetic approximation problems. Math. Method. Appl. Sci. 4, 382–396 (1982)
Freeden, W.: Ein Konvergenzsatz in sphärischer Spline-Interpolation. Z. f. Vermes-sungswes.(ZfV) 109, 569–576 (1984)
Freeden, W.: Spherical spline interpolation: basic theory and computational aspects. J. Comput. Appl. Math. 11, 367–375 (1984)
Freeden, W.: Harmonic splines for solving boundary value problems of potential theory. In: Mason, J.C., Cox, M.G. (eds.) Algorithms for Approximation. The Institute of Mathematics and Its Applications, Conference Series, vol. 10, pp. 507–529. Clarendon Press, Oxford (1987)
Freeden, W.: A spline interpolation method for solving boundary value problems of potential theory from discretely given data. Numer. Methods Partial Differ. Equ. 3, 375–398 (1987)
Freeden, W.: Multiscale Modelling of Spaceborne Geodata. B.G. Teubner, Stuttgart/Leipzig (1999)
Freeden, W., Gerhards, C.: Geomathematically Oriented Potential Theory. Chapman & Hall/CRC, Boca Raton (2013)
Freeden, W., Gervens, T., Schreiner, M.: Constructive Approximation on the Sphere. Oxford University Press, Oxford (1998)
Freeden, W., Gervens, T., Schreiner, M.: Constructive Approximation on the Sphere (With Applications to Geomathematics). Oxford Science Publications, Clarendon (1998)
Freeden, W., Glockner, O., Schreiner, M.: Spherical panel clustering and its numerical aspects. J. Geodesy 72, 586–599 (1998)
Freeden, W., Gutting, M.: Special Functions of Mathematical (Geo-)Physics. Birkhäuser, Basel (2013)
Freeden, W., Gutting, M.: Integration and Cubature Methods: A Geomathematically Oriented Course. Chapman and Hall/CRC, Boca Raton (2017)
Freeden, W., Michel, V.: Multiscale Potential Theory (With Applications to Geoscience). Birkhäuser, Boston (2004)
Freeden, W., Nashed, M.Z. (eds.): Handbook of Mathematical Geodesy – Functional Analytic and Potential Theoretic Methods. Birkhäuser, Basel (2018)
Freeden, W., Nashed, M.Z., Sonar, T. (eds.): Handbook of Geomathematics, 2nd edn. Springer, Heidelberg (2015)
Freeden, W., Schreiner, M.: Special functions in mathematical geosciences: an attempt at a categorization. In: Freeden, W., Nashed, M.Z., Sonar, T. (eds.) Handbook of Geomathematics, 1st edn., pp. 925–948. Springer, Heidelberg (2010)
Freeden, W., Schreiner, M., Franke, R.: A survey on spherical spline approximation. Surv. Math. Ind. 7, 29–85 (1997)
Gfrerer, H.: An a posteriori parameter choice for ordinary and iterated Tikhonov regularization of ill-posed problems leading to optimal convergence rates. Math. Comput. 49(180), 507–522 (1987)
Girard, D.: A fast “Monte-Carlo cross-validation” procedure for large least squares problems with noisy data. Numer. Math. 56(1), 1–23 (1989)
Glockner, O.: On numerical aspects of gravitational field modelling from SST and SGG by harmonic splines and wavelets (with application to CHAMP data). Ph.D. thesis, Geomathematics Group, Department of Mathematics, University of Kaiserslautern. Shaker, Aachen (2002)
Greengard, L.: The Rapid Evaluation of Potential Fields in Particle Systems. MIT Press, Cambridge (1988)
Greengard, L., Rokhlin, V.: A fast algorithm for particle simulations. J. Comput. Phys. 73(1), 325–348 (1987)
Greengard, L., Rokhlin, V.: Rapid evaluation of potential fields in three dimensions. In: Anderson, C., Greengard, L. (eds.) Vortex Methods, pp. 121–141. Springer, Berlin/New York (1988)
Greengard, L., Rokhlin, V.: A new version of the fast multipole method for the Laplace equation in three dimensions. Acta Numer. 6 229–269 (1997)
Gutting, M.: Fast multipole methods for oblique derivative problems. Ph.D. thesis, Geomathematics Group, Department of Mathematics, University of Kaiserslautern. Shaker, Aachen (2007)
Gutting, M.: Fast multipole accelerated solution of the oblique derivative boundary value problem. GEM Int. J. Geom. 3(2), 223–252 (2012)
Gutting, M.: Fast spherical/harmonic spline modeling. In: Freeden, W., Nashed, M.Z., Sonar, T. (eds.) Handbook of Geomathematics, 2nd edn., pp. 2711–2746. Springer, Heidelberg (2015)
Gutting, M.: Parameter choices for fast harmonic spline approximation. In: Freeden, W., Nashed, M.Z. (eds.) Handbook of Mathematical Geodesy – Functional Analytic and Potential Theoretic Methods, pp. 605–639. Birkhäuser, Basel (2018)
Gutting, M., Kretz, B., Michel, V., Telschow, R.: Study on parameter choice methods for the RFMP with respect to downward continuation. Front. Appl. Math. Stat. 3, 1–17 (2017). https://doi.org/10.3389/fams.2017.00010
Hansen, P.C.: Analysis of discrete ill-posed problems by means of the L-curve. SIAM Rev. 34(4), 561–580 (1992)
Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems. SIAM, Philadelphia (1998)
Hobson, E.W.: The Theory of Spherical and Ellipsoidal Harmonics (Second Reprint). Chelsea Publishing Company, New York (1965)
Hutchinson, M.: A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Commun. Stat. Simul. Comput. 18(3), 1059–1076 (1989)
Keiner, J., Kunis, S., Potts, D.: Fast summation of radial functions on the sphere. Computing 78, 1–15 (2006)
Kellogg, O.D.: Foundation of Potential Theory. Springer, Berlin/Heidelberg/New York (1967)
Kindermann, S., Neubauer, A.: On the convergence of the quasioptimality criterion for (iterated) Tikhonov regularization. Inverse Probl. Imaging 2(2), 291–299 (2008)
Lepskij, O.: On a problem of adaptive estimation in Gaussian white noise. Theory Probab. Appl. 35(3), 454–466 (1990)
Lu, S., Mathé, P.: Heuristic parameter selection based on functional minimization: optimality and model function approach. Math. Comput. 82(283), 1609–1630 (2013)
Lu, S., Mathé, P.: Discrepancy based model selection in statistical inverse problems. J. Complex. 30(3), 290–308 (2014)
Lukas, M.A.: Convergence rates for regularized solutions. Math. Comput. 51(183), 107–131 (1988)
Lukas, M.A.: On the discrepancy principle and generalised maximum likelihood for regularisation. Bull. Aust. Math. Soc. 52(3), 399–424 (1995)
Lukas, M.A.: Comparisons of parameter choice methods for regularization with discrete noisy data. Inverse Prob. 14(1), 161–184 (1998)
Lukas, M.A.: Robust generalized cross-validation for choosing the regularization parameter. Inverse Prob. 22(5), 1883–1902 (2006)
Lukas, M.A.: Strong robust generalized cross-validation for choosing the regularization parameter. Inverse Prob. 24, 034006, 16pp (2008)
Magnus, W., Oberhettinger, F., Soni, R.P.: Formulas and Theorems for the Special Functions of Mathematical Physics. Die Grundlehren der mathematischen Wissenschaften, vol. 52, 3rd edn. Springer, New York (1966)
Mathé, P., Pereverzev, S.V.: Regularization of some linear ill-posed problems with discretized random noisy data. Math. Comput. 75(256), 1913–1929 (2006)
Michel, V.: Tomography: problems and multiscale solutions. In: Freeden, W., Nashed, M.Z., Sonar, T. (eds.) Handbook of Geomathematics. 1st edn., pp. 949–972. Springer, Heidelberg (2010)
Michel, V.: Lectures on Constructive Approximation – Fourier, Spline, and Wavelet Methods on the Real Line, the Sphere, and the Ball. Birkhäuser, Boston (2013)
Michel, V.: RFMP – an iterative best basis algorithm for inverse problems in the geosciences. In: Freeden, W., Nashed, M.Z., Sonar, T. (eds.) Handbook of Geomathematics, 2nd edn., pp. 2121–2147. Springer, Heidelberg (2015)
Moritz, H.: Classical physical geodesy. In: Freeden, W., Nashed, M.Z., Sonar, T. (eds.) Handbook of Geomathematics, 1st edn., pp. 127–158. Springer, Heidelberg (2010)
Morozov, V.A.: On the solution of functional equations by the method of regularization. Soviet Math. Dokl. 7, 414–417 (1966)
Phillips, D.: A technique for the numerical solution of certain integral equations of the first kind. J. Assoc. Comput. Mach. 9, 84–97 (1962)
Potts, D., Steidl, G.: Fast summation at nonequispaced knots by NFFTs. SIAM J. Sci. Comput. 24(6), 2013–2037 (2003)
Raus, T.: On the discrepancy principle for the solution of ill-posed problems. Uch. Zap. Tartu. Gos. Univ. 672, 16–26 (1984)
Raus, T.: An a posteriori choice of the regularization parameter in case of approximately given error bound of data. In: Pedas, A. (ed.) Collocation and Projection Methods for Integral Equations and Boundary Value Problems, pp. 73–87. Tartu University, Tartu (1990)
Raus, T.: About regularization parameter choice in case of approximately given error bounds of data. In: Vainikko, G. (ed.) Methods for Solution of Integral Equations and Ill-Posed Problems, pp. 77–89. Tartu University, Tartu (1992)
Robinson, T., Moyeed, R.: Making robust the cross-validatory choice of smoothing parameter in spline smoothing regression. Commun. Stat. Theory Methods 18(2), 523–539 (1989)
Rokhlin, V.: Rapid solution of integral equations of classical potential theory. J. Comput. Phys. 60, 187–207 (1985)
Shure, L., Parker, R.L., Backus, G.E.: Harmonic splines for geomagnetic modelling. Phys. Earth Planet. Inter. 28, 215–229 (1982)
Tikhonov, A., Arsenin, V.: Solutions of Ill-Posed Problems. Wiley, New York (1977)
Tikhonov, A., Glasko, V.: Use of the regularization method in non-linear problems. U.S.S.R. Comput. Math. Math. Phys. 5(3), 93–107 (1965)
Varshalovich, D.A., Moskalev, A.N., Chersonskij, V.K.: Quantum Theory of Angular Momentum. World Scientific, Singapore (1988)
Wahba, G.: Practical approximate solutions to linear operator equations when the data are noisy. SIAM J. Numer. Anal. 14(4), 651–667 (1977)
Wahba, G.: Spline interpolation and smoothing on the sphere. SIAM J. Sci. Stat. Comput. 2, 5–16. Also errata: SIAM J. Sci. Stat. Comput. 3, 385–386 (1981)
Wahba, G.: Spline Models for Observational Data. SIAM, Philadelphia (1990)
White, C.A., Head-Gordon, M.: Rotating around the quartic angular momentum barrier in fast multipole method calculations. J. Chem. Phys. 105(12), 5061–5067 (1996)
Yamabe, H.: On an extension of the Helly’s theorem. Osaka Math. J. 2(1), 15–17 (1950)
Yarvin, N., Rokhlin, V.: Generalized Gaussian quadratures and singular value decomposition of integral equations. SIAM J. Sci. Comput. 20(2), 699–718 (1998)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2018 Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature
About this entry
Cite this entry
Gutting, M. (2018). Fast Harmonic/Spherical Splines and Parameter Choice Methods. In: Freeden, W., Rummel, R. (eds) Handbuch der Geodäsie. Springer Reference Naturwissenschaften . Springer Spektrum, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46900-2_106-1
Download citation
DOI: https://doi.org/10.1007/978-3-662-46900-2_106-1
Published:
Publisher Name: Springer Spektrum, Berlin, Heidelberg
Print ISBN: 978-3-662-46900-2
Online ISBN: 978-3-662-46900-2
eBook Packages: Springer Referenz Naturwissenschaften