Surface Reconstruction of 3D Scattered Data with Radial Basis Functions

We use Radial Basis Functions （RBFs） to reconstruct smooth surfaces from 3D scattered data. An object＇s surface is defined implicitly as the zero set of an RBF fitted to the given surface data. We propose improvements on the methods of surface reconstruction with radial basis functions. A sparse approximation set of scattered data is constructed by reducing the number of interpolating points on the surface. We present an adaptive method for finding the off-surface normal points. The order of the equation decreases greatly as the number of the off-surface constraints reduces gradually. Experimental results are provided to illustrate that the proposed method is robust and may draw beautiful graphics.     

A stable local radial basis function method for option pricing problem under the Bates model

We propose a local mesh‐free method for the Bates–Scott option pricing model, a 2D partial integro‐differential equation (PIDE) arising in computational finance. A Wendland radial basis function (RBF) approach is used for the discretization of the spatial variables along with a linear interpolation technique for the integral operator. The resulting set of ordinary differential equations (ODEs) is tackled via a time integration method. A potential advantage of using RBFs is the small number of discrete equations that need to be solved. Computational experiments are presented to illustrate the performance of the contributed approach.     

Algorithm for Optimal Triangulations in Scattered Data Representation and Implementation

Scattered data collected at sample points may be used to determine simple functions to best fit the data. An ideal choice for these simple functions is bivariate splines. Triangulation of the sample points creates partitions over which the bivariate splines may be defined. But the optimality of the approximation is dependent on the choice of triangulation. An algorithm, referred to as an Edge Swapping Algorithm, has been developed to transform an arbitrary triangulation of the sample points into an optimal triangulation for representation of the scattered data. A Matlab package has been completed that implements this algorithm for any triangulation on a given set of sample points.     

On convergent numerical algorithms for unsymmetric collocation

In this paper, we are interested in some convergent formulations for the unsymmetric collocation method or the so-called Kansa’s method. We review some newly developed theories on solvability and convergence. The rates of convergence of these variations of Kansa’s method are examined and verified in arbitrary–precision computations. Numerical examples confirm with the theories that the modified Kansa’s method converges faster than the interpolant to the solution; that is, exponential convergence for the multiquadric and Gaussian radial basis functions (RBFs). Some numerical algorithms are proposed for efficiency and accuracy in practical applications of Kansa’s method. In double–precision, even for very large RBF shape parameters, we show that the modified Kansa’s method, through a subspace selection using a greedy algorithm, can produce acceptable approximate solutions. A benchmark algorithm is used to verify the optimality of the selection process.     

Accuracy of radial basis function interpolation and derivative approximations on 1-D infinite grids

Radial basis function (RBF) interpolation can be very effective for scattered data in any number of dimensions. As one of their many applications, RBFs can provide highly accurate collocation-type numerical solutions to several classes of PDEs. To better understand the accuracy that can be obtained, we survey here derivative approximations based on RBFs using a similar Fourier analysis approach that has become the standard way for assessing the accuracy of finite difference schemes. We find that the accuracy is directly linked to the decay rate, at large arguments, of the (generalized) Fourier transform of the radial function. Three different types of convergence rates can be distinguished as the node density increases – polynomial, spectral, and superspectral, as exemplified, for example, by thin plate splines, multiquadrics, and Gaussians respectively. Bengt Fornberg: The work was supported by NSF grants DMS-9810751 (VIGRE), DMS-0073048 and DMS-0309803.Natasha Flyer: The work was supported by the NSF grant DMS-9810751 (VIGRE).     

A general framework for frequentist model averaging In Celebration of Professor Lincheng Zhao's 75th Birthday

Model selection strategies have been routinely employed to determine a model for data analysis in statistics, and further study and inference then often proceed as though the selected model were the true model that were known a priori. Model averaging approaches, on the other hand, try to combine estimators for a set of candidate models. Specifically, instead of deciding which model is the 'right' one, a model averaging approach suggests to fit a set of candidate models and average over the estimators using data adaptive weights.In this paper we establish a general frequentist model averaging framework that does not set any restrictions on the set of candidate models. It broaden, the scope of the existing methodologies under the frequentist model averaging development. Assuming the data is from an unknown model, we derive the model averaging estimator and study its limiting distributions and related predictions while taking possible modeling biases into account.We propose a set of optimal weights to combine the individual estimators so that the expected mean squared error of the average estimator is minimized. Simulation studies are conducted to compare the performance of the estimator with that of the existing methods. The results show the benefits of the proposed approach over traditional model selection approaches as well as existing model averaging methods.     

Locality properties of radial basis function expansion coefficients for equispaced interpolation

Natasha Flyer ^{Many types of radial basis functions (RBFs) are global in termsof having large magnitude across the entire domain. Yet, incontrast, e.g. with expansions in orthogonal polynomials, RBFexpansions exhibit a strong property of locality with regardto their coefficients. That is, changing a single data valuemainly affects the coefficients of the RBFs which are centredin the immediate vicinity of that data location. This localityfeature can be advantageous in the development of fast and well-conditionediterative RBF algorithms. With this motivation, we employ hereboth analytical and numerical techniques to derive the decayrates of the expansion coefficients for cardinal data, in both1D and 2D. Furthermore, we explore how these rates vary in theinteresting high-accuracy limit of increasingly flat RBFs.}     

Block preconditioners for linear systems arising from multiscale collocation with compactly supported RBFs

Symmetric collocation methods with RBFs allow approximation of the solution of a partial differential equation, even if the right‐hand side is only known at scattered data points, without needing to generate a grid. However, the benefit of a guaranteed symmetric positive definite block system comes at a high computational cost. This cost can be alleviated somewhat by considering compactly supported RBFs and a multiscale technique. But the condition number and sparsity will still deteriorate with the number of data points. Therefore, we study certain block diagonal and triangular preconditioners. We investigate ideal preconditioners and determine the spectra of the preconditioned matrices before proposing more practical preconditioners based on a restricted additive Schwarz method with coarse grid correction. Numerical results verify the effectiveness of the preconditioners. Copyright © 2015 John Wiley & Sons, Ltd.     

A modified method of approximate particular solutions for solving linear and nonlinear PDEs

The method of approximate particular solutions (MAPS) was first proposed by Chen et al. in Chen, Fan, and Wen, Numer Methods Partial Differential Equations, 28 (2012), 506–522. using multiquadric (MQ) and inverse multiquadric radial basis functions (RBFs). Since then, the closed form particular solutions for many commonly used RBFs and differential operators have been derived. As a result, MAPS was extended to Matérn and Gaussian RBFs. Polyharmonic splines (PS) has rarely been used in MAPS due to its conditional positive definiteness and low accuracy. One advantage of PS is that there is no shape parameter to be taken care of. In this article, MAPS is modified so PS can be used more effectively. In the original MAPS, integrated RBFs, so called particular solutions, are used. An additional integrated polynomial basis is added when PS is used. In the modified MAPS, an additional polynomial basis is directly added to the integrated RBFs without integration. The results from the modified MAPS with PS can be improved by increasing the order of PS to a certain degree or by increasing the number of collocation points. A polynomial of degree 15 or less appeared to be working well in most of our examples. Other RBFs such as MQ can be utilized in the modified MAPS as well. The performance of the proposed method is tested on a number of examples including linear and nonlinear problems in 2D and 3D. We demonstrate that the modified MAPS with PS is, in general, more accurate than other RBFs for solving general elliptic equations.© 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 1839–1858, 2017     

Dynamic analysis of plane elasticity with new complex Fourier radial basis functions in the dual reciprocity boundary element method

In this paper, dual reciprocity (DR) boundary element method (BEM) is reformulated using new radial basis function (RBF) to approximate the inhomogeneous term of Navier’s differential equation (i.e., inertia term). This new RBF, which is in the form of exp(iωr), is called complex Fourier RBF hereafter. The present RBF has simultaneously collected the properties of Gaussian and real Fourier RBF reported in literature together. Consequently, this promising feature has provided more robustness and potency of the proposed method. The required kernels for displacement and traction particular solutions are derived by employing the method of variation of parameters. As some terms of these kernels are singular, a new simple smoothing trick is employed to resolve the singularity problem. Moreover, the limiting values of relevant kernels are evaluated. The validity, accuracy, and strength of the present formulation are illustrated throughout several numerical examples. The numerical results show that the proposed complex Fourier RBF represents more accurate solutions, using less degree of freedom compared to other RBFs available in the literature.     

Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting

In this paper we discuss Sobolev bounds on functions that vanish at scattered points in a bounded, Lipschitz domain that satisfies a uniform interior cone condition. The Sobolev spaces involved may have fractional as well as integer order. We then apply these results to obtain estimates for continuous and discrete least squares surface fits via radial basis functions (RBFs). These estimates include situations in which the target function does not belong to the native space of the RBF.

     

Using genetic programming to evolve action selection rules in traversal-based automated software testing: results obtained with the TESTAR tool

Traversal-based automated software testing involves testing an application via its graphical user interface (GUI) and thereby taking the user’s point of view and executing actions in a human-like manner. These actions are decided on the fly, as the software under test (SUT) is being run, as opposed to being set up in the form of a sequence prior to the testing, a sequence that is then used to exercise the SUT. In practice, random choice is commonly used to decide which action to execute at each state (a procedure commonly referred to as monkey testing), but a number of alternative mechanisms have also been proposed in the literature. Here we propose using genetic programming (GP) to evolve such an action selection strategy, defined as a list of IF-THEN rules. Genetic programming has proved to be suited for evolving all sorts of programs, and rules in particular, provided adequate primitives (functions and terminals) are defined. These primitives must aim to extract the most relevant information from the SUT and the dynamics of the testing process. We introduce a number of such primitives suited to the problem at hand and evaluate their usefulness based on various metrics. We carry out experiments and compare the results with those obtained by random selection and also by Q-learning, a reinforcement learning technique. Three applications are used as Software Under Test (SUT) in the experiments. The analysis shows the potential of GP to evolve action selection strategies.     

On choosing “optimal” shape parameters for RBF approximation

Many radial basis function (RBF) methods contain a free shape parameter that plays an important role for the accuracy of the method. In most papers the authors end up choosing this shape parameter by trial and error or some other ad hoc means. The method of cross validation has long been used in the statistics literature, and the special case of leave-one-out cross validation forms the basis of the algorithm for choosing an optimal value of the shape parameter proposed by Rippa in the setting of scattered data interpolation with RBFs. We discuss extensions of this approach that can be applied in the setting of iterated approximate moving least squares approximation of function value data and for RBF pseudo-spectral methods for the solution of partial differential equations. The former method can be viewed as an efficient alternative to ridge regression or smoothing spline approximation, while the latter forms an extension of the classical polynomial pseudo-spectral approach. Numerical experiments illustrating the use of our algorithms are included.     

Optimizing radial basis functions by d.c. programming and its use in direct search for global derivative-free optimization

In this paper, we address the global optimization of functions subject to bound and linear constraints without using derivatives of the objective function. We investigate the use of derivative-free models based on radial basis functions (RBFs) in the search step of direct-search methods of directional type. We also study the application of algorithms based on difference of convex (d.c.) functions programming to solve the resulting subproblems which consist of the minimization of the RBF models subject to simple bounds on the variables. Extensive numerical results are reported with a test set of bound and linearly constrained problems.     

Sobolev Error Estimates and a Bernstein Inequality for Scattered Data Interpolation via Radial Basis Functions

Error estimates for scattered-data interpolation via radial basis functions (RBFs) for target functions in the associated reproducing kernel Hilbert space (RKHS) have been known for a long time. Recently, these estimates have been extended to apply to certain classes of target functions generating the data which are outside the associated RKHS. However, these classes of functions still were not "large" enough to be applicable to a number of practical situations. In this paper we obtain Sobolev-type error estimates on compact regions of Rⁿ when the RBFs have Fourier transforms that decay algebraically. In addition, we derive a Bernstein inequality for spaces of finite shifts of an RBF in terms of the minimal separation parameter.     

Radial basis function collocation method for the numerical solution of the two-dimensional transient nonlinear coupled Burgers’ equations

This paper examines the numerical solution of the transient nonlinear coupled Burgers’ equations by a Local Radial Basis Functions Collocation Method (LRBFCM) for large values of Reynolds number (Re) up to 10³. The LRBFCM belongs to a class of truly meshless methods which do not need any underlying mesh but works on a set of uniform or random nodes without any a priori node to node connectivity. The time discretization is performed in an explicit way and collocation with the multiquadric radial basis functions (RBFs) are used to interpolate diffusion-convection variable and its spatial derivatives on decomposed domains. Five nodded domains of influence are used in the local support. Adaptive upwind technique [1] and [54] is used for stabilization of the method for large Re in the case of mixed boundary conditions. Accuracy of the method is assessed as a function of time and space discretizations. The method is tested on two benchmark problems having Dirichlet and mixed boundary conditions. The numerical solution obtained from the LRBFCM for different value of Re is compared with analytical solution as well as other numerical methods [15], [47] and [49]. It is shown that the proposed method is efficient, accurate and stable for flow with reasonably high Reynolds numbers.     

Interval uncertainty analysis for static response of structures using radial basis functions

This paper proposes a new interval uncertainty analysis method for static response of structures with unknown-but-bounded parameters by using radial basis functions (RBFs). Recently, collocation methods (CM) which apply orthogonal polynomials are proposed to solve interval uncertainty quantification problems with high accuracy. These methods overcome the drawback of Taylor expansion based methods, which are prone to overestimate the response bounds. However, the form of orthogonal basis functions is very complicated in higher dimensions, which may restrict their application when there exist relatively more interval parameters. In contrast to orthogonal basis function, the form of radial basis function (RBF) is simple and stays the same in whatever dimension. This study introduces RBFs into interval analysis of structures and provides a relatively simple approach to solve structural response bounds accurately. A surrogate model of real structural response with respect to interval parameters is constructed with the RBFs. The extrema of the surrogate model can be calculated by some auxiliary methods. The static response bounds can be obtained accordingly. Two numerical examples are used to verify the proposed method. The engineering application of the proposed method is performed by a center wing-box. The results prove the effectiveness of the proposed method.     

Regularized collocation method for Fredholm integral equations of the first kind

In this paper we consider a collocation method for solving Fredholm integral equations of the first kind, which is known to be an ill-posed problem. An “unregularized” use of this method can give reliable results in the case when the rate at which smallest singular values of the collocation matrices decrease is known a priori. In this case the number of collocation points plays the role of a regularization parameter. If the a priori information mentioned above is not available, then a combination of collocation with Tikhonov regularization can be the method of choice. We analyze such regularized collocation in a rather general setting, when a solution smoothness is given as a source condition with an operator monotone index function. This setting covers all types of smoothness studied so far in the theory of Tikhonov regularization. One more issue discussed in this paper is an a posteriori choice of the regularization parameter, which allows us to reach an optimal order of accuracy for deterministic noise model without any knowledge of solution smoothness.     

Approximate Interpolation with Applications to Selecting Smoothing Parameters

In this paper, we study the global behavior of a function that is known to be small at a given discrete data set. Such a function might be interpreted as the error function between an unknown function and a given approximant. We will show that a small error on the discrete data set leads under mild assumptions automatically to a small error on a larger region. We will apply these results to spline smoothing and show that a specific, a priori choice of the smoothing parameter is possible and leads to the same approximation order as the classical interpolant. This has also a surprising application in stabilizing the interpolation process by splines and positive definite kernels.     

Matrix-valued radial basis functions: stability estimates and applications

Radial basis functions (RBFs) have found important applications in areas such as signal processing, medical imaging, and neural networks since the early 1980s. Several applications require that certain physical properties are satisfied by the interpolant, for example, being divergence-free in case of incompressible data. In this paper we consider a class of customized (e.g., divergence-free) RBFs that are matrix-valued and have compact support; these are matrix-valued analogues of the well-known Wendland functions. We obtain stability estimates for a wide class of interpolants based on matrix-valued RBFs, also taking into account the size of the compact support of the generating RBF. We conclude with an application based on an incompressible Navier–Stokes equation, namely the driven-cavity problem, where we use divergence-free RBFs to solve the underlying partial differential equation numerically. We discuss the impact of the size of the support of the basis function on the stability of the solution. AMS subject classification 65D05