A greedy algorithm for partition of unity collocation method in pricing American options

A greedy algorithm in combination with radial basis functions partition of unity collocation (GRBF‐PUC) scheme is used as a locally meshless method for American option pricing. The radial basis function partition of unity method (RBF‐PUM) is a localization technique. Because of having interpolation matrices with large condition numbers, global approximants and some local ones suffer from instability. To overcome this, a greedy algorithm is added to RBF‐PUM. The greedy algorithm furnishes a subset of best nodes among the points X. Such nodes are then used as points of trial in a locally supported RBF approximant for each partition. Using of greedy selected points leads to decreasing the condition number of interpolation matrices and reducing the burdensome in pricing American options.     

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.     

Approximate solutions of partial differential equations by some Meshfree Greedy Algorithms

In this article, we use some greedy algorithms to avoid the ill‐conditioning of the final linear system in unsymmetric Kansa collocation method. The greedy schemes have the same background, but we use them in different settings. In the first algorithm, the optimal trial points for interpolation obtained among a huge set of initial points are used for numerical solution of partial differential equations (PDEs). In the second algorithm, based on the Kansa's method, the PDE is discretized to a finite number of test functional equations, and a greedy sparse discretization is applied for approximating the linear functionals. Each functional is stably approximated by some few trial points with an acceptable accuracy. The third greedy algorithm is used to generate the test points. This paper shows that the greedily selection of nodes yields a better conditioning in contrast with usual full meshless methods. Some well‐known PDE examples are solved and compared with the full unsymmetric Kansa's technique. © 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 1884–1899, 2017     

Domain decomposition for radial basis meshless methods

Both overlapping and nonoverlapping domain decomposition methods (DDM) on matching and nonmatching grid have been developed to couple with the meshless radial basis function (RBF) method. Example shows that overlapping DDM with RBF can achieve much better accuracy with less nodal points compared to FDM and FEM. Numerical results also show that nonmatching grid DDM can achieve almost the same accuracy within almost the same iteration steps as the matching grid case; hence our method is very attractive, because it is much easier to generate nonmatching grid just by putting blocks of grids together (for both overlapping and nonoverlapping), where each block grid can be generated independently. Also our methods are showed to be able to handle discontinuous coefficient. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 450–462, 2004.     

A meshless scaling iterative algorithm based on compactly supported radial basis functions for the numerical solution of Lane‐Emden‐Fowler equation

In this article, we combine the compactly supported radial basis function (RBF) collocation method and the scaling iterative algorithm to compute and visualize the multiple solutions of the Lane‐Emden‐Fowler equation on a bounded domain Ω ? R² with a homogeneous Dirichlet boundary condition. This novel method has the advantage over traditional methods, which approximate the spatial derivatives using either the finite difference method (FDM), the finite element method (FEM), or the boundary element method (BEM), because it does not require a mesh over the domain. As a result, it needs less computational time than the globally supported RBF collocation method. When compared with the reference solutions in (Chen, Zhou, and Ni, Int J Bifurcation Chaos 10 (2000), 565–1612), our numerical results demonstrate the accuracy and ease of implementation of this method. It is therefore much more suitable for dealing with the complex domains than the FEM, the FDM, and the BEM. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 554‐572, 2012     

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.     

Product Gauss quadrature rules vs. cubature rules in the meshless local Petrov–Galerkin method

A crucial point in the implementation of meshless methods such as the meshless local Petrov–Galerkin (MLPG) method is the evaluation of the domain integrals arising over circles in the discrete local weak form of the governing partial differential equation. In this paper we make a comparison between the product Gauss numerical quadrature rules, which are very popular in the MLPG literature, with cubature formulas specifically constructed for the approximation of an integral over the unit disk, but not yet applied in the MLPG method, namely the spherical, the circularly symmetrical and the symmetric cubature formulas. The same accuracy obtained with 64×64 points in the product Gauss rules may be obtained with symmetric quadrature formulas with very few points.     

Exponential convergence and H‐c multiquadric collocation method for partial differential equations

The radial basis function (RBF) collocation method uses global shape functions to interpolate and collocate the approximate solution of PDEs. It is a truly meshless method as compared to some of the so‐called meshless or element‐free finite element methods. For the multiquadric and Gaussian RBFs, there are two ways to make the solution converge—either by refining the mesh size h, or by increasing the shape parameter c. While the h‐scheme requires the increase of computational cost, the c‐scheme is performed without extra effort. In this paper we establish by numerical experiment the exponential error estimate ? ～ O(λ^√c?h) where 0 < λ < 1. We also propose the use of residual error as an error indicator to optimize the selection of c. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 571–594, 2003     

非对称稀疏线性方程组的快速外存解法及其在无网格法计算中的应用

针对局部Petrov-Galerkin无网格法(MLPG)等无网格方法的计算所产生的大型非对称稀疏线性方程组,介绍了一种新的直接解法．与一般非对称求解过程不同,该解法从现有的对称正定解法中演变出来,其分解过程在矩阵的上、下三角阵中对称进行．新的矩阵分解算法可以通过修改对称矩阵分解算法的代码来实现,这提供了从对称解法到非对称解法的快捷转换．还针对MLGP法以及有限元法所产生的方程组开发了多块外存算法(multi-blocked out-of-core strategy)来扩大求解规模．测试结果证明该方法大幅度提高了大型非对称稀疏线性方程组的求解速度．     

A symmetric integrated radial basis function method for solving differential equations

In this article, integrated radial basis functions (IRBFs) are used for Hermite interpolation in the solution of differential equations, resulting in a new meshless symmetric RBF method. Both global and local approximation‐based schemes are derived. For the latter, the focus is on the construction of compact approximation stencils, where a sparse system matrix and a high‐order accuracy can be achieved together. Cartesian‐grid‐based stencils are possible for problems defined on nonrectangular domains. Furthermore, the effects of the RBF width on the solution accuracy for a given grid size are fully explored with a reasonable computational cost. The proposed schemes are numerically verified in some elliptic boundary‐value problems governed by the Poisson and convection‐diffusion equations. High levels of the solution accuracy are obtained using relatively coarse discretisations.     

A shift‐adaptive meshfree method for solving a class of initial‐boundary value problems with moving boundaries in one‐dimensional domain

A new shift‐adaptive meshfree method for solving a class of time‐dependent partial differential equations (PDEs) in a bounded domain (one‐dimensional domain) with moving boundaries and nonhomogeneous boundary conditions is introduced. The radial basis function (RBF) collocation method is combined with the finite difference scheme, because, unlike with Kansa's method, nonlinear PDEs can be converted to a system of linear equations. The grid‐free property of the RBF method is exploited, and a new adaptive algorithm is used to choose the location of the collocation points in the first time step only. In fact, instead of applying the adaptive algorithm on the entire domain of the problem (like with other existing adaptive algorithms), the new adaptive algorithm can be applied only on time steps. Furthermore, because of the radial property of the RBFs, the new adaptive strategy is applied only on the first time step; in the other time steps, the adaptive nodes (obtained in the first time step) are shifted. Thus, only one small system of linear equations must be solved (by LU decomposition method) rather than a large linear or nonlinear system of equations as in Kansa's method (adaptive strategy applied to entire domain), or a large number of small linear systems of equations in the adaptive strategy on each time step. This saves a lot in time and memory usage. Also, Stability analysis is obtained for our scheme, using Von Neumann stability analysis method. Results show that the new method is capable of reducing the number of nodes in the grid without compromising the accuracy of the solution, and the adaptive grading scheme is effective in localizing oscillations due to sharp gradients or discontinuities in the solution. The efficiency and effectiveness of the proposed procedure is examined by adaptively solving two difficult benchmark problems, including a regularized long‐wave equation and a Korteweg‐de Vries problem. © 2016Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 1622–1646, 2016     

A Petrov–Galerkin RBF method for diffusion equation on the unit sphere

This paper concerns a numerical solution for the diffusion equation on the unit sphere. The given method is based on the spherical basis function approximation and the Petrov–Galerkin test discretization. The method is meshless because spherical triangulation is not required neither for approximation nor for numerical integration. This feature is achieved through the spherical basis function approximation and the use of local weak forms instead of a global variational formulation. The local Petrov–Galerkin formulation allows to compute the integrals on small independent spherical caps without any dependence on a connected background mesh. Experimental results show the accuracy and the efficiency of the new method.     

Multilevel Interpolation and Approximation

Interpolation by translates of a given radial basis function (RBF) has become a well-recognized means of fitting functions sampled at scattered sites in ^d. A major drawback of these methods is their inability to interpolate very large data sets in a numerically stable way while maintaining a good fit. To circumvent this problem, a multilevel interpolation (ML) method for scattered data was presented by Floater and Iske. Their approach involves m levels of interpolation where at the jth level, the residual of the previous level is interpolated. On each level, the RBF is scaled to match the data density. In this paper, we provide some theoretical underpinnings to the ML method by establishing rates of approximation for a technique that deviates somewhat from the Floater–Iske setting. The final goal of the ML method will be to provide a numerically stable method for interpolating several thousand points rapidly.     

Adaptive radial basis function interpolation using an error indicator

In some approximation problems, sampling from the target function can be both expensive and time-consuming. It would be convenient to have a method for indicating where approximation quality is poor, so that generation of new data provides the user with greater accuracy where needed. In this paper, we propose a new adaptive algorithm for radial basis function (RBF) interpolation which aims to assess the local approximation quality, and add or remove points as required to improve the error in the specified region. For Gaussian and multiquadric approximation, we have the flexibility of a shape parameter which we can use to keep the condition number of interpolation matrix at a moderate size. Numerical results for test functions which appear in the literature are given for dimensions 1 and 2, to show that our method performs well. We also give a three-dimensional example from the finance world, since we would like to advertise RBF techniques as useful tools for approximation in the high-dimensional settings one often meets in finance.     

Sampling and multilevel coarsening algorithms for fast matrix approximations

This paper addresses matrix approximation problems for matrices that are large, sparse, and/or representations of large graphs. To tackle these problems, we consider algorithms that are based primarily on coarsening techniques, possibly combined with random sampling. A multilevel coarsening technique is proposed, which utilizes a hypergraph associated with the data matrix and a graph coarsening strategy based on column matching. We consider a number of standard applications of this technique as well as a few new ones. Among standard applications, we first consider the problem of computing partial singular value decomposition, for which a combination of sampling and coarsening yields significantly improved singular value decomposition results relative to sampling alone. We also consider the column subset selection problem, a popular low‐rank approximation method used in data‐related applications, and show how multilevel coarsening can be adapted for this problem. Similarly, we consider the problem of graph sparsification and show how coarsening techniques can be employed to solve it. We also establish theoretical results that characterize the approximation error obtained and the quality of the dimension reduction achieved by a coarsening step, when a proper column matching strategy is employed. Numerical experiments illustrate the performances of the methods in a few applications.     

The Method of Fundamental Solutions: A Weighted Least-Squares Approach

We investigate the Method of Fundamental Solutions (MFS) for the solution of certain elliptic boundary value problems. In particular, we study the case in which the number of collocation points exceeds the number of singularities, which leads to an over-determined linear system. In such a case, the resulting linear system is over-determined and the proposed algorithm chooses the approximate solution for which the error, when restricted to the boundary, minimizes a suitably defined discrete Sobolev norm. This is equivalent to a weighted least-squares treatment of the resulting over-determined system. We prove convergence of the method in the case of the Laplace’s equation with Dirichlet boundary data in the disk. We develop an alternative way of implementing the numerical algorithm, which avoids the inherent ill-conditioning of the MFS matrices. Finally, we present numerical experiments suggesting that introduction of Sobolev weights improves the approximation. AMS subject classification (2000) 35E05, 35J25, 65N12, 65N15, 65N35, 65T50     

A local hermitian RBF meshless numerical method for the solution of multi‐zone problems

The local Hermitian interpolation (LHI) method is a strong‐form meshless numerical technique in which the solution domain is covered by a series of small and heavily overlapping radial basis function (RBF) interpolation systems. Aside from its meshless nature and the ability to work on very large scattered datasets, the main strength of the LHI method lies in the formation of local interpolations, which themselves satisfy both boundary and governing PDE operators, leading to an accurate and stable reconstruction of partial derivatives without the need for artificial upwinding or adaptive stencil selection. In this work, an extension is proposed to the LHI formulation which allows the accurate capture of solution profiles across discontinuities in governing equation parameters. Continuity of solution value and mass flux is enforced between otherwise disconnected interpolation systems, at the location of the discontinuity. In contrast to other local meshless methods, due to the robustness of the Hermite RBF formulation, it is possible to impose both matching conditions simultaneously at the interface nodes. The procedure is demonstrated for 1D and 3D convection–diffusion problems, both steady and unsteady, with discontinuities in various PDE properties. The analytical solution profiles for these problems, which experience discontinuities in their first derivatives, are replicated to a high degree of accuracy. The technique has been developed as a tool for solving flow and transport problems around geological layers, as experienced in groundwater flow problems. The accuracy of the captured solution profiles, in scenarios where the local convective velocities exceed those typically encountered in such Darcy flow problems, suggests that the technique is indeed suitable for modeling discontinuities in porous media properties. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1201–1230, 2011     

The meshless local Petrov-Galerkin method for simulating unsteady incompressible fluid flow

This article presents a numerical algorithm using the Meshless Local Petrov-Galerkin (MLPG) method for the incompressible Navier–Stokes equations. To deal with time derivatives, the forward time differences are employed yielding the Poisson’s equation. The MLPG method with the moving least-square (MLS) approximation for trial function is chosen to solve the Poisson’s equation. In numerical examples, the local symmetric weak form (LSWF) and the local unsymmetric weak form (LUSWF) with a classical Gaussian weight and an improved Gaussian weight on both regular and irregular nodes are demonstrated. It is found that LSWF1 with a classical Gaussian weight order 2 gives the most accurate result.     

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.     

An efficient indirect RBFN‐based method for numerical solution of PDEs

This article presents an efficient indirect radial basis function network (RBFN) method for numerical solution of partial differential equations (PDEs). Previous findings showed that the RBFN method based on an integration process (IRBFN) is superior to the one based on a differentiation process (DRBFN) in terms of solution accuracy and convergence rate (Mai‐Duy and Tran‐Cong, Neural Networks 14(2) 2001, 185). However, when the problem dimensionality N is greater than 1, the size of the system of equations obtained in the former is about N times as big as that in the latter. In this article, prior conversions of the multiple spaces of network weights into the single space of function values are introduced in the IRBFN approach, thereby keeping the system matrix size small and comparable to that associated with the DRBFN approach. Furthermore, the nonlinear systems of equations obtained are solved with the use of trust region methods. The present approach yields very good results using relatively low numbers of data points. For example, in the simulation of driven cavity viscous flows, a high Reynolds number of 3200 is achieved using only 51 × 51 data points. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005