{"id":19409,"date":"2009-12-11T11:34:02","date_gmt":"2009-12-11T15:34:02","guid":{"rendered":"http:\/\/www.bu.edu\/tech\/?page_id=19409"},"modified":"2023-04-19T16:57:12","modified_gmt":"2023-04-19T20:57:12","slug":"petrbf","status":"publish","type":"page","link":"https:\/\/www.bu.edu\/tech\/support\/research\/whats-happening\/highlights\/petrbf\/","title":{"rendered":"PetRBF – A Parallel O(N) Algorithm for Radial Basis Function Interpolation"},"content":{"rendered":"

Rio Yokota, University of Bristol, U.K.
\nLorena A. Barba, Boston University
\nMatthew Knepley, University of Chicago<\/strong><\/p>\n

Many applications in computational science need to approximate a function based on ?nite data. When the data are in a certain sense \u201cscattered\u201d in their domain, one very powerful technique is radial basis function (RBF) interpolation. For many years, the wide applicability of RBF interpolation was hindered by its numerical difficulty and expense. Indeed, in their mathematical expression, RBF methods produce an ill-conditioned linear system, for which a direct solution becomes prohibitive for more than a few thousand data points.<\/p>\n

We have developed a parallel algorithm for RBF interpolation that exhibits O(N) complexity, requires O(N) storage, and scales excellently up to a thousand processes. The algorithm uses the GMRES iterative solver with a restricted additive Schwarz method (RASM) as a preconditioner and a fast matrix-vector algorithm. Previous fast RBF methods \u2014 achieving at most O(N log N) complexity \u2014 were developed using multiquadric and polyharmonic basis functions. In contrast, the present method uses Gaussians with a small variance. 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. The 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 seconds (19 iterations for an error tolerance of 10e\u221215) on 1024 processors of a Blue Gene\/L (700 MHz PowerPC processors).<\/p>\n

The parallel code is freely available in the open-source model. http:\/\/code.google.com\/p\/petrbf\/<\/a><\/p>\n

Radial Basis Function (RBF) Interpolation<\/h4>\n

Approximate a function by:
\n\"Image \"Image<\/p>\n

Domain Decomposition Methods<\/h4>\n

Domain decomposition methods can be used to solve the linear system on highly parallel architectures by distributing the problem.<\/p>\n

\"Image \"Image<\/p>\n

Mathematically it can be written as \u00a0\u00a0\u00a0 \t\"Image<\/p>\n

\"Image<\/p>\n

\"Small is the restriction operator, which maps the elements onto the overlapping subdomain.<\/p>\n

\"Small is the projection operator, which maps the elements onto the overlapping subdomain.<\/p>\n

 <\/div>\n

Restricted Additive Schwarz Method (RASM)<\/h4>\n

\"Image<\/p>\n

For Gaussian basis functions the RASM serves as a preconditioner and parallelization technique. This particular basis function is a perfect match for the RASM.<\/p>\n

Parameters in RASM<\/h4>\n

The size of the non-overlapping subdomain B, the overlapping subdomain D, and the domain to be considered in the matrix-vector multiplication T have a large impact on the calculation time. It is the relative size of these domains compared to s that makes the difference. This is independent of the number of elements and the number of processes.<\/p>\n

\n\"RASM<\/a> \"Graphs<\/a><\/div>\n

Complexity and Memory Usage<\/h4>\n

When the number of elements N is increased, the calculation time and memory usage of the present method increases as O(N). This is superior to other RBF interpolation methods which scale as O(N log N)<\/p>\n

\n\"Graphs<\/a><\/div>\n

Parallel Scalability<\/h4>\n

For the parallel calculations we used the Blue Gene\/L machine at Boston University.<\/p>\n

\n\"Four<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"

Rio Yokota, University of Bristol, U.K. Lorena A. Barba, Boston University Matthew Knepley, University of Chicago Many applications in computational science need to approximate a function based on ?nite data. When the data are in a certain sense \u201cscattered\u201d in their domain, one very powerful technique is radial basis function (RBF) interpolation. For many years,…<\/p>\n","protected":false},"author":1692,"featured_media":0,"parent":57322,"menu_order":19,"comment_status":"closed","ping_status":"open","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/www.bu.edu\/tech\/wp-json\/wp\/v2\/pages\/19409"}],"collection":[{"href":"https:\/\/www.bu.edu\/tech\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.bu.edu\/tech\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.bu.edu\/tech\/wp-json\/wp\/v2\/users\/1692"}],"replies":[{"embeddable":true,"href":"https:\/\/www.bu.edu\/tech\/wp-json\/wp\/v2\/comments?post=19409"}],"version-history":[{"count":13,"href":"https:\/\/www.bu.edu\/tech\/wp-json\/wp\/v2\/pages\/19409\/revisions"}],"predecessor-version":[{"id":145173,"href":"https:\/\/www.bu.edu\/tech\/wp-json\/wp\/v2\/pages\/19409\/revisions\/145173"}],"up":[{"embeddable":true,"href":"https:\/\/www.bu.edu\/tech\/wp-json\/wp\/v2\/pages\/57322"}],"wp:attachment":[{"href":"https:\/\/www.bu.edu\/tech\/wp-json\/wp\/v2\/media?parent=19409"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}