×

zbMATH — the first resource for mathematics

PetRBF - A parallel \(O(N)\) algorithm for radial basis function interpolation with Gaussians. (English) Zbl 1231.65026
Summary: We have developed a parallel algorithm for radial basis function (RBF) interpolation that exhibits \(O(N)\) complexity, requires \(O(N)\) storage, and scales excellently up to a thousand processes. The algorithm uses a gmres iterative solver with a restricted additive Schwarz method (RASM) as a preconditioner and a fast matrix-vector algorithm. Previous fast rbf methods-achieving at most \(O(N\log N)\) complexity-were developed using multiquadric and polyharmonic basis functions. In contrast, the present method uses Gaussians with a small variance with respect to the domain, but with sufficient overlap. This is a common choice in particle methods for fluid simulation, our main target application. The fast decay of the Gaussian basis function allows rapid convergence of the iterative solver even when the subdomains in the rasm are very small. At the same time we show that the accuracy of the interpolation can achieve machine precision. The present method was implemented in parallel using the petsc library (developer version). Numerical experiments demonstrate its capability in problems of rbf interpolation with more than 50 million data points, timing at 106 s (19 iterations for an error tolerance of \(10^{ - 15}\)) on 1024 processors of a Blue Gene/L (700 MHz PowerPC processors). The parallel code is freely available in the open-source model.

MSC:
65D05 Numerical interpolation
65Y05 Parallel numerical computation
Software:
Matlab; PetRBF; PETSc
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Atluri, S.N.; Zhu, T., A new meshless local Petrov-Galerkin (MLPG) approach in computational mechanics, Comput. mech., 22, 117-127, (1998) · Zbl 0932.76067
[2] Babuska, I.; Melenk, J.M., The partition of unity method, Int. J. numer. methods engrg., 40, 727-758, (1997) · Zbl 0949.65117
[3] Balay, S.; Buschelman, K.; Eijkhout, V.; Gropp, W.D.; Kaushik, D.; Knepley, M.; Curfman-McInnes, L.; Smith, B.F.; Zhang, H., ()
[4] Barba, L.A., Computing high-Reynolds number vortical flows: a highly accurate method with a fully meshless formulation, (), 305-312
[5] Barba, L.A.; Leonard, A., Emergence and evolution of tripole vortices from net-circulation initial conditions, Phys. fluids, 19, 1, 017101, (2007) · Zbl 1146.76319
[6] Barba, L.A.; Leonard, A.; Allen, C.B., Advances in viscous vortex methods — meshless spatial adaption based on radial basis function interpolation, Int. J. num. meth. fluids, 47, 5, 387-421, (2005) · Zbl 1085.76052
[7] Barba, L.A.; Rossi, L.F., Global field interpolation for particle methods, J. comp. phys., 229, 4, 1292-1310, (2010) · Zbl 1329.76282
[8] Beatson, R.K.; Cherrie, J.B.; Mouat, C.T., Fast Fitting of radial basis functions: methods based on preconditioned GMRES iteration, Adv. comp. math., 11, 2-3, 253-270, (November 1999)
[9] 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) · Zbl 0982.65015
[10] Beatson, R.K.; Newsam, G.N., Fast evaluation of radial basis functions: I, Comp. math. applic., 24, 12, 7-19, (1992) · Zbl 0765.65021
[11] Beatson, R.K.; Powell, M.J.D., An iterative method for thin plate spline interpolation that employs approximations to Lagrange functions, (), 17-39 · Zbl 0795.65004
[12] Belytschko, T.; Lu, Y.Y.; Gu, L., Element-free Galerkin methods, Int. J. numer. methods engrg., 37, 2, 229-256, (1994) · Zbl 0796.73077
[13] Billings, S.D.; Beatson, R.K.; Newsam, G.N., Interpolation of geophysical data using continuous global surfaces, Geophysics, 67, 6, 1810-1822, (2002)
[14] Buhmann, M.D., Radial basis functions. theory and implementations, (2003), Cambridge University Press · Zbl 1038.41001
[15] Cai, X.-C.; Sarkis, M., A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM J. sci. comput., 21, 792-797, (1997) · Zbl 0944.65031
[16] Carr, J.C.; Fright, W.R.; Beatson, R.K., Surface interpolation with radial basis functions for medical imaging, IEEE trans. med. imag., 16, 1, 96-107, (1997)
[17] Chen, W., New RBF collocation schemes and kernel RBFs with applications, Lect. notes comput. sci. engrg., 26, 75-86, (2002) · Zbl 1016.65094
[18] Cherrie, J.B.; Beatson, R.K.; Newsam, G.N., Fast evaluation of radial basis functions: methods for generalized multiquadrics in Rn, SIAM J. sci. comput., 23, 5, 1549-1571, (2002) · Zbl 1009.65007
[19] Duarte, C.A.; Tinsley Oden, J., An h-p adaptive method using clouds, Comput. methods appl. mech. engrg., 139, 1-4, 237-262, (1996) · Zbl 0918.73328
[20] Efstathiou, E.; Gander, M.J., Why restricted additive Schwarz converges faster than additive Schwarz, BIT numer. math., 43, 945-959, (2003) · Zbl 1045.65027
[21] Fasshauer, G.E., Solving partial differential equations by collocation with radial basis functions, (), 131-138 · Zbl 0938.65140
[22] Fasshauer, G.E., Meshfree approximation methods with MATLAB, (2007), World Scientific · Zbl 1123.65001
[23] Faul, A.C.; Goodsell, G.; Powell, M.J.D., A Krylov subspace algorithm for multiquadric interpolation in many dimensions, IMA J. numer. anal., 25, 1-24, (2005) · Zbl 1070.65006
[24] Franke, R., Scattered data interpolation: tests of some methods, Math. comp., 38, 157, 181-200, (1982) · Zbl 0476.65005
[25] Greengard, L.; Strain, J., The fast Gauss transform, SIAM J. sci. statist. comput., 12, 1, 79-94, (January 1991)
[26] Gumerov, N.A.; Duraiswami, R., Fast multipole method for the biharmonic equation, () · Zbl 1103.65122
[27] Gumerov, N.A.; Duraiswami, R., Fast radial basis function interpolation via preconditioned Krylov iteration, SIAM J. sci. comput., 29, 5, 1876-1899, (2007) · Zbl 1154.65303
[28] Hardy, R.L., Theory and applications of the multiquadric-biharmonic method, Comput. math. appl., 19, 8/9, 163-208, (1990) · Zbl 0692.65003
[29] Hughes, T.J.R.; Cottrell, J.A.; Bazilevs, Y., Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement, Comput. methods appl. mech. engrg., 194, 39-41, 4135-4195, (2005) · Zbl 1151.74419
[30] Ingber, M.S.; Chen, C.S.; Tanski, J.A., A mesh free approach using radial basis functions and parallel domain decomposition for solving three-dimensional diffusion equations, Int. J. numer. methods engrg., 60, 2183-2201, (2004) · Zbl 1178.76276
[31] Kansa, E.J., Multiquadrics — a scattered data approximation scheme with applications to computational fluid-dynamics, I. surface approximations and partial derivative estimates, Comput. math. appl., 19, 8/9, 127-145, (1990) · Zbl 0692.76003
[32] Kansa, E.J., Multiquadrics — a scattered data approximation scheme with applications to computational fluid-dynamics, II. solutions to parabolic, hyperbolic and elliptic partial differential equations, Comput. math. appl., 19, 8/9, 147-161, (1990) · Zbl 0850.76048
[33] Kansa, E.J.; Hon, Y.C., Circumventing the ill-conditioning problem with multiquadric radial basis functions: applications to elliptic partial differential equations, Comput. math. appl., 39, 123-137, (2000) · Zbl 0955.65086
[34] Leonard, A., Vortex methods for flow simulation, J. comp. phys., 37, 289-335, (1980) · Zbl 0438.76009
[35] Li, J.; Chen, Y.; Pepper, D., Radial basis function method for 1-D and 2-D groundwater contaminant transport modeling, Comput. mech., 23, 10-15, (2003) · Zbl 1045.76548
[36] Li, J.; Hon, Y.C., Domain decomposition for radial basis meshless methods, Numer. methods partial differ. equ., 20, 3, 450-462, (2004) · Zbl 1048.65124
[37] Ling, L.; Kansa, E.J., Preconditioning for radial basis functions with domain decomposition methods, Math. comput. model., 40, 1413-1427, (2004) · Zbl 1077.41008
[38] Ling, L.; Kansa, E.J., A least-squares preconditioner for radial basis functions collocation methods, Adv. comput. math., 23, 31-54, (2005) · Zbl 1067.65136
[39] Liu, W.K.; Jun, S.; Li, S.; Adee, J.; Belytschko, T., Reproducing kernel particle methods for structural dynamics, Int. J. numer. methods engrg., 38, 10, 1655-1679, (1995) · Zbl 0840.73078
[40] Madych, W.R.; Nelson, S.A., Multivariate interpolation and conditionally positive definite functions: II, Math. comp., 54, 189, 211-230, (1990) · Zbl 0859.41004
[41] Mai-Duy, N.; Tran-Cong, T., Indirect RBFN method with thin plate splines for numerical solution of differential equations, Comput. model. engrg. sci., 4, 1, 85-102, (2003) · Zbl 1148.76351
[42] Micchelli, C.A., Interpolation of scattered data: distance matrices and conditionally positive definite functions, Constr. approx., 2, 11-22, (1986) · Zbl 0625.41005
[43] Powell, M.J.D., Truncated Laurent expansions for the fast evaluation of thin plate splines, Numer. algorithms, 5, 99-120, (1993) · Zbl 0790.65010
[44] Roussos, G.; Baxter, B.J.C., Rapid evaluation of radial basis functions, J. comput. appl. math., 180, 1, 51-70, (2005) · Zbl 1069.65008
[45] Saad, Y., Iterative methods for sparse linear systems, (2003), SIAM · Zbl 1002.65042
[46] Smith, B.F.; Bjorstad, P.E.; Gropp, W.D., Domain decomposition, parallel multilevel methods for elliptic partial differential equations, (1996), Cambridge University Press · Zbl 0857.65126
[47] Torres, C.E.; Barba, L.A., Fast radial basis function interpolation with gaussians by localization and iteration, J. comp. phys., 228, 4976-4999, (2009) · Zbl 1168.65318
[48] Wong, S.M.; Hon, Y.C.; Li, T.S.; Chung, S.L., Multi-zone decomposition for simulation of time-dependent problems using the multiquadric scheme, Comput. math. appl., 37, 23-43, (1999) · Zbl 0951.76066
[49] Yokota, R.; Sheel, T.K.; Obi, S., Calculation of isotropic turbulence using a pure Lagrangian vortex method, J. comp. phys., 226, 1589-1606, (2007) · Zbl 1121.76046
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.