Radial basis functions for simulating PDEs

Overview

Finite differences remain useful because they are simple, direct,
flexible, easy done at high order, and effective.

Main limitation is restriction to (logically) rectangular grids.

Radial basis functions offer the possibility of a difference-based
method with no need for grids or meshes.

1. Background
2. 1-D analysis
3. Practical considerations for PDEs

Interpolation (1D)

In one dimension, data can be interpolated smoothly using splines.

Doesn't matter if nodes are scattered rather than equispaced.

Interpolation (2D)

On a regular 2-D grid, data can be interpolated smoothly by splines.

On scattered nodes, smooth splines are diffcult.

Radial basis functions

A radial basis function interpolant can be smooth and accurate on
any set of nodes in any dimension.

Definition

Given nodes x_i and data f_i, i = 1, . . . ,N, define

Use 2-norm for The are chosen for interpolation.

In matrix terms,

Basis functions

Piecewise smooth

Infinitely smooth

Basic properties

•For many smooth choices of , the RBF matrix A is guaranteed
to be invertible (Micchelli, 1986). Other cases are easily fixed.
•No grid required, only nodes.
•Effort is independent of spatial dimension.
•ore smoothness = higher accuracy = poorer conditioning of A.

Cubic splines

Consider 1-D,. Since and piecewise cubic,
RBF interpolant is a spline. The B-spline

can be used for analysis. For instance, Gibbs' phenomenon.

Overshoot is 10.78% (compared to 14.11% in trig interpolation).

Cubic RBFs from cubic splines

A cubic spline is determined by interpolation plus two boundary
conditions.

Suppose x ∈[−1, 1]. To recreate a cubic RBF interpolant, use

Conclude. Boundaries are coupled together in RBF interpolation.

Cubic splines from cubic RBFs

Natural spline. s''(−1) = s''(1) = 0.

RBF interpolant with linear asymptotic growth.

Not-a-knot spline. s''' continuous at x^2 and x_N−1.
Divorce nodes and RBF centers (knots).

Improves convergence at ends.

In nitely smooth RBFs

Most important in practice is . (MQ).

Use for analysis (IQ). Similar to MQ in practice.

Introduce scaling parameter as in

Decreasing tends to flatten the basis functions.

Fourier analysis

Discretize on in nite grid x_n = nh.
Interpolate, differentiate, and evaluate on grid.

Spectral di erentiation is
FD2 gives
RBFs using IQ with scaling parameter gives

Comparison on Fourier data

The flat-RBF society

As , two things seem to happen.
Better accuracy for interpolant
Worse (unbounded) conditioning for matrix A in
Practical computations strike a balance|often through brute force.
But even though the diverge, might have a limit?

Limit result

Theorem (Driscoll and Fornberg). Expand a smooth as

Define symmetric matrices by

If and are nonsingular, then on any set of N 1-D nodes,
converges to the Lagrange interpolating polynomial as

Spin

In the flat limit, RBFs give something familiar and useful.
Computing the RBF coefficients is an unstable step in a
well-conditioned process (polynomial interpolation).

In 2-D, still (usually) converges to an interpolating
polynomial. However, limit depends on

Work is underway on stable means of computing in the limit,
preferably by bypassing the coefficient computation.

RBF difference methods

Use RBF interpolant to compute spatial derivatives for a PDE at
grid points.

Already successful for elliptic and diffusive evolution equations.

Issues

condition of RBF matrix
size of RBF matrix
choice of
boundary conditions
variable resolution
grid generation

Strategies

preconditioners, multigrid
domain decomposition
many good options|still heuristic
symmetric Hermite method
adaptive, time-varying grids
NOT!

Nondissipative propagation

For example, Maxwell's equations with interfaces.

New challenge. Time stability at boundaries

Boundaries

From 1-D theory.
•coupling of boundaries (spline BC)
•loss of accuracy near boundaries (natural spline)
•convergence to polynomial (Runge phenomenon)
All suggest trouble at boundaries.

Suggestions

Without dissipation, instability is deadly.
Some options.
1. Change the basis, as in natural splines.
2. Change the implementation, as in not-a-knot.
3. Change the nodes, as in pseudospectral methods.

1. Change the basis

Reproduce polynomials exactly, or limit asymptotic growth.

V is Vandermonde

m = −1 gives standard RBF.
m = N − 1 gives polynomial interpolation.
Actually an old RBF idea. Easily generalizes to higher dimensions.

Effect of polynomial terms

Benefits for small m, but diminishing returns as degree increases.

2. Change the method

Not-a-knot. Separate two RBF centers from interpolation nodes.

Independent of the changed center locations. Improves cubic
spline accuracy from h² to h³.

"Super" not-a-knot. Do it again.

Independent of altered locations. Improves accuracy to h⁴ even
just outside the interval.

Not-a-knot example

May be special only for 1-D cubics.

3. Change the nodes

For 1-D polynomials, Chebyshev density

is optimal for stability.
Try distributing nodes according to

for (equispaced to Chebyshev).

Effects of node density

Most improvement for intermediate

Comparison in 2-D

Node/center distributions on the unit disk.

Observations

1. Adding polynomials to the basis
•Some improvement throughout.
•Little benefit in going past linear.
•Some theoretical justification.

2. Not-a-Knot/SNaK
•Dramatic improvement with SNaK.
•Locating centers to move may be tricky.
•Effects on RBF matrix not well known.

3. Boundary clustering
•Good improvement at boundary.
•May cause interior degradation.
•Distribution of nodes may be difficult in general.

These approaches may be combined freely.

Promise and problems

Radial basis functions offer the promise of difference methods that
are simple, user-friendly, easy at high order, and free of grids and
meshes.

Significant problems remain to be fully resolved.
•stable boundary strategies
•choice of scaling parameter/computing in the flat limit
•conditioning/size of RBF matrix
•theoretical underpinnings in realistic situations