Preconditioning for radial basis functions with domain decomposition methods

In our previous work, an effective preconditioning scheme that is based upon constructing least-squares approximation cardinal basis functions (ACBFs) from linear combinations of the RBF-PDE matrix elements has shown very attractive numerical results. The preconditioner costs O(N²) flops to set up and O(N) storage. The preconditioning technique is sufficiently general that it can be applied to different types of different operators. This was applied to the 2D multiquadric method, with c~1/√N on the Poisson test problem, the preconditioned GMRES converges in tens of iterations. In this paper, we combine the RBF methods and the ACBF preconditioning technique with the domain decomposition method (DDM). We studied different implementations of the ACBF-DDM scheme and provide numerical results for N > 10,000 nodes. We shall demonstrate that the efficiency of the ACBF-DDM scheme improves dramatically as successively finer partitions of the domain are considered.     

Boundary integral equations on the sphere with radial basis functions: error analysis

Radial basis functions are used to define approximate solutions to boundary integral equations on the unit sphere. These equations arise from the integral reformulation of the Laplace equation in the exterior of the sphere, with given Dirichlet or Neumann data, and a vanishing condition at infinity. Error estimates are proved. Numerical results supporting the theoretical results are presented.     

Some issues on interpolation matrices of locally scaled radial basis functions

Radial basis function interpolation on a set of scattered data is constructed from the corresponding translates of a basis function, which is conditionally positive definite of order m ? 0, with the possible addition of a polynomial term. In many applications, the translates of a basis function are scaled differently, in order to match the local features of the data such as the flat region and the data density. Then, a fundamental question is the non-singularity of the perturbed interpolation (N × N) matrix. In this paper, we provide some counter examples of the matrices which become singular for N ? 3, although the matrix is always non-singular when N = 2. One interesting feature is that a perturbed matrix can be singular with rather small perturbation of the scaling parameter.     

Numerical solutions of KdV equation using radial basis functions

Numerical solution of the Korteweg-de Vries equation is obtained by using the meshless method based on the collocation with radial basis functions. Five standard radial basis functions are used in the method of the collocation. The results are compared for the numerical experiments of the propagation of solitons, interaction of two solitary waves and breakdown of initial conditions into a train of solitons.     

A low-cost-memory CUDA implementation of the conjugate gradient method applied to globally supported radial basis functions implicits

Hermitian radial basis functions implicits is a method capable of reconstructing implicit surfaces from first-order Hermitian data. When globally supported radial functions are used, a dense symmetric linear system must be solved. In this work, we aim at exploring and computing a matrix-free implementation of the Conjugate Gradients Method on the GPU in order to solve such linear system. The proposed method parallelly rebuilds the matrix on demand for each iteration. As a result, it is able to compute the Hermitian-based interpolant for datasets that otherwise could not be handled due to the high memory demanded by their linear systems.     

The regularizing properties of anisotropic radial basis functions

In the present work we consider the problem of interpolating scattered data using radial basis functions (RBF). In general, it is well known that this leads to a discrete linear inverse problem that needs to be regularized in order to provide a meaningful solution. The work focuses on a metric-regularization approach, based on a new class of RBF, called anisotropic RBF. The work provides theoretical justifications for the regularization approach and it considers a suitable proposal for the metric, supporting it by numerical examples.     

An analytic approximation to the cardinal functions of Gaussian radial basis functions on an infinite lattice

Gaussian radial basis functions (RBFs) have been very useful in computer graphics and for numerical solutions of partial differential equations where these RBFs are defined, on a grid with uniform spacing h, as translates of the “master” function (x;α,h)≡exp(-[α²/h²]x²) where α is a user-choosable constant. Unfortunately, computing the coefficients of (x-jh;α,h) requires solving a linear system with a dense matrix. It would be much more efficient to rearrange the basis functions into the equivalent “Lagrangian” or “cardinal” basis because the interpolation matrix in the new basis is the identity matrix; the cardinal basis C_j(x;α,h) is defined by the set of linear combinations of the Gaussians such that C_j(kh)=1 when k=j and C_j(kh)=0 for all integers . We show that the cardinal functions for the uniform grid are C_j(x;h,α)=C(x/h-j;α) where C(X;α)≈(α²/π)sin(πX)/sinh(α²X). The relative error is only about 4exp(-2π²/α²) as demonstrated by the explicit second order approximation. It has long been known that the error in a series of Gaussian RBFs does not converge to zero for fixed α as h→0, but only to an “error saturation” proportional to exp(-π²/α²). Because the error in our approximation to the master cardinal function C(X;α) is the square of the error saturation, there is no penalty for using our new approximations to obtain matrix-free interpolating RBF approximations to an arbitrary function f(x). The master cardinal function on a uniform grid in d dimensions is just the direct product of the one-dimensional cardinal functions. Thus in two dimensions . We show that the matrix-free interpolation can be extended to non-uniform grids by a smooth change of coordinates.     

Kernel based approximation in Sobolev spaces with radial basis functions

In this paper, we study several radial basis function approximation schemes in Sobolev spaces. We obtain an optional error estimate by using a class of smoothing operators. We also discussed sufficient conditions for the smoothing operators to attain the desired approximation order. We then construct the smoothing operators by some compactly supported radial kernels, and use them to approximate Sobolev space functions with optimal convergence order. These kernels can be simply constructed and readily applied to practical problems. The results show that the approximation power depends on the precision of the sampling instrument and the density of the available data.     

Unsteady seepage analysis using local radial basis function-based differential quadrature method

Numerical simulation of two-dimensional transient seepage is developed using radial basis function-based differential quadrature method (RBF-DQ). To the best of the authors’ knowledge, this is the first application of this method to seepage analysis. For the general case of irregular geometry and unstructured node distribution, the local form of RBF-DQ was used. The multiquadric type of radial basis functions was selected for the computations, and the results were compared with analytical, finite element method, and existing numerical solutions from the literature. Results of this study show that localized RBF-DQ can produce accurate results for the analysis of seepage. The method is meshfree and easy to program, but as with previous applications of RBFs, requires careful selection of suitable shape parameters. A practical method for estimating suitable shape parameters is discussed. For time integration, Crank–Nicolson, Galerkin and finite difference methods were applied, leading to stable results.     

Numerical analyses of the boundary effect of radial basis functions in 3D surface reconstruction

Surface reconstruction is very important for surface characterization and graph processing. Radial basis function has now become a popular method to reconstruct 3D surfaces from scattered data. However, it is relatively inaccurate at the boundary region. To solve this problem, a circle of new centres are added outside the domain of interest. The factors that influence the boundary behaviour are analyzed quantitatively via numerical experiments. It is demonstrated that if the new centres are properly located, the boundary problem can be effectively overcome whilst not reducing the accuracy at the interior area. A modified Graham scan technique is introduced to obtain the boundary points from a scattered point set. These boundary points are extended outside with an appropriate distance, and then uniformized to form the new auxiliary centres.      

An overlapping additive Schwarz preconditioner for interpolation on the unit sphere with spherical radial basis functions

The problem of interpolation of scattered data on the unit sphere has many applications in geodesy and Earth science in which the sphere is taken as a model for the Earth. Spherical radial basis functions provide a convenient tool for constructing the interpolant. However, the underlying linear systems tend to be ill-conditioned. In this paper, we present an additive Schwarz preconditioner for accelerating the solution process. An estimate for the condition number of the preconditioned system will be discussed. Numerical experiments using MAGSAT satellite data will be presented.     

On the solution of the non-local parabolic partial differential equations via radial basis functions

In this paper, the problem of solving the one-dimensional parabolic partial differential equation subject to given initial and non-local boundary conditions is considered. The approximate solution is found using the radial basis functions collocation method. There are some difficulties in computing the solution of the time dependent partial differential equations using radial basis functions. If time and space are discretized using radial basis functions, the resulted coefficient matrix will be very ill-conditioned and so the corresponding linear system cannot be solved easily. As an alternative method for solution, we can use finite-difference methods for discretization of time and radial basis functions for discretization of space. Although this method is easy to use but an accurate solution cannot be provided. In this work an efficient collocation method is proposed for solving non-local parabolic partial differential equations using radial basis functions. Numerical results are presented and are compared with some existing methods.     

Approximation on the sphere using radial basis functions plus polynomials

In this paper we analyse a hybrid approximation of functions on the sphere by radial basis functions combined with polynomials, with the radial basis functions assumed to be generated by a (strictly) positive definite kernel. The approximation is determined by interpolation at scattered data points, supplemented by side conditions on the coefficients to ensure a square linear system. The analysis is first carried out in the native space associated with the kernel (with no explicit polynomial component, and no side conditions). A more refined error estimate is obtained for functions in a still smaller space. Numerical calculations support the utility of this hybrid approximation.      

Parallel radial basis function methods for the global optimization of expensive functions

We introduce a master–worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by Gutmann [Gutmann, H.M., 2001a. A radial basis function method for global optimization. Journal of Global Optimization 19(3), 201–227] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [Regis, R.G., Shoemaker, C.A., 2005. Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization 31, 153–171] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors.     

Numerical experiments on the condition number of the interpolation matrices for radial basis functions

Through numerical experiments, we examine the condition numbers of the interpolation matrix for many species of radial basis functions (RBFs), mostly on uniform grids. For most RBF species that give infinite order accuracy when interpolating smooth f(x)—Gaussians, sech's and Inverse Quadratics—the condition number κ(α,N) rapidly asymptotes to a limit κasymp(α) that is independent of N and depends only on α, the inverse width relative to the grid spacing. Multiquadrics are an exception in that the condition number for fixed α grows as N². For all four, there is growth proportional to an exponential of 1/α (1/α² for Gaussians). For splines and thin-plate splines, which contain no width parameter, the condition numbers grows asymptotically as a power of N—a large power as the order of the RBF increases. Random grids typically increase the condition number (for fixed RBF width) by orders of magnitude. The quasi-random, low discrepancy Halton grid may, however, have a lower condition number than a uniform grid of the same size.     

Direct solution of Navier–Stokes equations by radial basis functions

The pressure–velocity formulation of the Navier–Stokes (N–S) equation is solved using the radial basis functions (RBF) collocation method. The non-linear collocated equations are solved using the Levenberg–Marquardt method. The primary novelty of this approach is that the N–S equation is solved directly, instead of using an iterative algorithm for the primitive variables. Two flow situations are considered: Couette flow with and without pressure gradient, and 2D laminar flow in a duct with and without flow obstruction. The approach is validated by comparing the Couette flow results with the analytical solution and the 2D results with those obtained using the well-validated CFD-ACE™ commercial package.     

Determination of a control parameter in a one-dimensional parabolic equation using the method of radial basis functions

In this work, the method of radial basis functions is used for finding the solution of an inverse problem with source control parameter. Because a much wider range of physical phenomena are modelled by nonclassical parabolic initial-boundary value problems, theoretical behavior and numerical approximation of these problems have been active areas of research. The radial basis functions (RBF) method is an efficient mesh free technique for the numerical solution of partial differential equations. The main advantage of numerical methods which use radial basis functions over traditional techniques is the meshless property of these methods. In a meshless method, a set of scattered nodes are used instead of meshing the domain of the problem. The results of numerical experiments are presented and some comparisons are made with several well-known finite difference schemes.     

Rational radial basis function interpolation with applications to antenna design

Functions with poles occur in many branches of applied mathematics which involve resonance phenomena. Such functions are challenging to interpolate, in particular in higher dimensions. In this paper we develop a technique for interpolation with quotients of two radial basis function (RBF) expansions to approximate such functions as an alternative to rational approximation. Since the quotient is not uniquely determined we introduce an additional constraint, the sum of the RBF-norms of the numerator and denominator squared should be minimal subjected to a norm condition on the function values. The method was designed for antenna design applications and we show by examples that the scattering matrix for a patch antenna as a function of some design parameters can be approximated accurately with the new method. In many cases, e.g. in antenna optimization, the function evaluations are time consuming, and therefore it is important to reduce the number of evaluations but still obtain a good approximation. A sensitivity analysis of the new interpolation technique is carried out and it gives indications how efficient adaptation methods could be devised. A family of such methods are evaluated on antenna data and the results show that much performance can be gained by choosing the right method.     

On the selection of the most adequate radial basis function

Radial basis function (RBF) methods can provide excellent interpolants for a large number of poorly distributed data points. For any finite data set in any Euclidean space, one can construct an interpolation of the data by using RBFs. However, RBF interpolant trends between and beyond the data points depend on the RBF used and may exhibit undesirable trends using some RBFs while the trends may be desirable using other RBFs. The fact that a certain RBF is commonly used for the class of problems at hand, previous good behavior in that (or other) class of problems, and bibliography, are just some of the many valid reasons given to justify a priori selection of RBF. Even assuming that the justified choice of the RBF is most likely the correct choice, one should nonetheless confirm numerically that, in fact, the most adequate RBF for the problem at hand is the RBF chosen a priori. The main goal of this paper is to alert the analyst as to the danger of a priori selection of RBF and to present a strategy to numerically choose the most adequate RBF that better captures the trends of the given data set. The wing weight data fitting problem is used to illustrate the benefits of an adequate choice of RBF for each given data set.