# Meshless collocation methods for the numerical solution of elliptic boundary valued problems the rotational shallow water equations on the sphere

Table of Contents L ist of Figures iv 1 Introduction 1 1.1 Historical Context and Motivations...................1 1.1.1 Why Meshless Collocation?...................2 1.2 Thesis Outline...............................5 2 The Meshless Collocation Method 10 2.1 Introduction................................10 2.2 Theory of Meshless Collocation.....................12 2.2.1 Preliminaries...........................12 2.2.2 Radial Functions.........................15 2.2.3 Reproducing Kernel Hilbert Spaces...............17 2.2.4 Native Spaces of Positive Deﬁnite Kernels...........21 2.2.5 Restriction and Extension....................33 2.2.6 Approximation in Native Spaces.................37 2.2.7 Lagrangian interpolant form...................40 2.2.8 Error estimate for derivatives of scattered data interpolation.41 2.3 Meshless Collocation Method for Elliptic PDEs in Native Spaces...53 2.3.1 Deriving an error bound for symmetric meshless collocation.65 2.4 Numerical Experiments of Meshless Collocation............72 2.4.1 Introduction............................72 2.4.2 Choice of Reproducing Kernels.................74 2.4.3 Implementation and numerical experiments for Elliptic Boundary- Valued Problems.........................76 2.4.3.1 Experiment 1......................78 2.4.3.2 Experiment 2......................84 2.4.3.3 Experiment 3......................88 2.4.4 Comparison with ﬁnite-element method.............91 2.4.4.1 Experiment 1......................93 2.4.4.2 Experiment 2......................96 2.4.5 Accuracy/Numerical Stability Trade-oﬀ.............99 3 A Meshless Collocation Method for the Rotational Shallow Water Equations on the Sphere 106 3.1 Introduction................................106 3.2 Theoretical issues of regional approximation in global models.....107 3.3 The Shallow Water model........................109 3.3.1 Implementation of the Cubed-Sphere..............110 3.3.2 Semi-Implicit Time Discretization................116 3.4 Meshless Collocation for the shallow-water equations.........118 3.4.1 Implementation of the shallow water model...........124 3.4.2 Complete Algorithm.......................129 ii

4 The High-Performance Parallel Computation of the Meshless Collocation Method for the Shallow-Water Equations on the Sphere 131 4.1 Introduction................................131 4.2 Parallel Algorithms............................132 4.2.1 Fast parallel computation of inverting a band matrix.....133 4.2.2 Parallel Conjugate Gradient Method..............139 4.3 Implementation of velocity and geopotential ﬁeld...........142 4.4 Numerical Experiments..........................147 4.4.1 Veriﬁcation and Validation....................147 4.4.2 Test Case 2:Global Steady State Nonlinear Zonal Geostrophic Flow................................150 4.4.2.1 Numerical Convergence................151 4.4.2.2 Scalability of Model..................152 4.4.3 Test Case 5:Flow over Mountain................160 4.4.3.1 Validity of Meshless Collocation Solution:Comput- ing Invariants......................161 4.4.3.2 Local Reﬁnement in Meshless Collocation......167 4.4.4 Test Case 6:Rossby-Haurwitz Waves..............174 4.4.4.1 Comparing with spectral-element solution......179 4.4.5 Test Case 8:Barotropic Instability...............180 4.4.5.1 Capturing Fast Gravity Waves............182 4.5 Conclusion.................................187 A Results from Functional Analysis 194 A.1 Banach and Hilbert Spaces........................194 A.2 Sobolev Spaces..............................198 B.3 Local Polynomial Reproduction.....................203 B.4 Cone condition and properties......................204 B.5 Norming sets...............................209 B.6 Local reproduction of derivatives of polynomials............219 C.7 Legendre Polynomials and Wendlend’s Kernels.............225 C.8 Legendre Polynomial Expansions....................225 C.9 Two-dimensional Legendre Expansions.................230 C.10 Wendland’s Compactly Supported Kernels...............232 Bibliography 236 iii

List of Figures 2 .1 Examples of diﬀerent node distributions (Gaussian,random,uniform).80 2.2 Pointwise error and approximation u h using 25 randomly scattered points in Ω.................................82 2.3 Pointwise error of 1089 collocation nodes for random (left) and uni- form (right) distribution..........................82 2.4 L-shaped domain with two diﬀerent node conﬁgurations..........85 2.5 L-shaped domain approximation with N = 100...............86 2.6 L-shaped domain pointwise error plot in two diﬀerent node conﬁgurations with N = 25 and N = 100..........................86 2.7 L-shaped domain with 30 interior nodes and 18 (left) and 54 (right) bound- ary nodes..................................89 2.8 Collocation solution with N = 286 random nodes..............90 2.9 Pointwise error for N = 9 (left) and N = 25 (right) collocation nodes in Ω.91 2.10 Piecewise-linear Finite element solution with 153 (left) and 310 (right) nodes from mesh...............................94 2.11 Piecewise-linear Finite element solution with 577 (left) and 789 (right) nodes from mesh...............................94 2.12 Meshless collocation solution with 153 (left) and 310 (right) collocation nodes in Ω..................................95 2.13 Finite element solution with 50 and 150 triangle discretizion Ω.......97 2.14 Finite element solution with 913 nodes from mesh in Ω...........98 2.15 (Left) L ∞ norm of the power function as N increases for uniform random grids.(Right) Condition number of A X on uniform and random grids...102 2.16 Power function on Ω for 4 diﬀerent sets X with N = 100,200,300,400. Two diﬀerent angles shown.........................103 2.17 Condition numbers (top) and power function norm (bottom) for the three diﬀerent kernels deﬁned by ψ 1 ,ψ 2 ,ψ 3 ....................105 iv

3.1 Discretized Cubed-Sphere........................115 4 .1 Example of 6 ×6 matrix with bandwidth 5 and its 3 ×3 block tridiagonal matrix representation............................135 4.2 Diagram of of the forward inverse process on a simple 3 ×3 block matrix.136 4.3 Example of the back inverse process on a 3 ×3 block matrix........136 4.4 Example of the outside inverse computations on a 3 ×3 block matrix...137 4.5 Mesh arrangements for the meshless collocation approximation on the sphere.The cube is tiled using 24 regions and Gauss Lobatto Legen- dre collocation nodes are distributed on each region (top) along with two additional reﬁnements (middle) and (bottom)................153 4.6 L ∞ error of the three mesh conﬁgurations.We use a time step ∆t of 1/288, namely 288 time steps per rotation of the sphere..............154 4.7 Scalability factors for the spectral element (SE) and meshless collocation (MC) solutions.Left 9600 nodes;right 18816 nodes.............159 4.8 Geopotential height isolines of days 1 and 3 of model integration.The model used 1560 uniform collocation nodes over entire cubed-sphere.As clearly seen,steady state ﬂow from test case 2 becomes nonlinear due to the obstructive mountain..........................162 4.9 Geopotential height isolines of days 5 and 8 of model integration.Flow is clearly nonlinear at this point and large gradients form near the mountain.163 4.10 Collocation node arrangements I,II,and III.The grid of nodes is reﬁned locally on II and then reﬁned again on III..................165 4.11 Invariants of the MC solution over 200 days of integration for diﬀerent node sets.(Red) Collocation node set I,(Green) Collocation node set II, (Blue) Collocation node set III.......................166 4.12 Initial condition of cubed-sphere layout at two diﬀerent angles with 900 nodes allocated to face 2...........................168 4.13 Plots of the geopotential meshless collocation approximation after 44 and 100 days...................................169 4.14 Plots and contours of the geopotential approximation after 44 and 100 days170 4.15 A zoom-in on the regional meshless approximation at 44 and 100 days..171 v

4.16 L1 diﬀerences of regional meshless approximation with 400,900,1200 nodes to high-order 64 element solution (top).L1 diﬀerences of SE ap- proximation with 4,9,and 16 elements to high-order 64 element solution (bottom)..................................173 4.17 Plot of the geopotential at 90 days and then at 120 days.The collocation solution was computed using 9 regions per face with GLL nodes on all faces except face 4,where a random distribution was given.........176 4.18 Plot of the geopotential at 200 days.....................177 4.19 Plot of the contours of the geopotential at 90,120,and 200 days......178 4.20 Plot of L1 diﬀerences between the meshless approximation on the face 2 and the high-order 64-element spectral element solution in the same region.180 4.21 Initial conditions of the problem.Zonal proﬁle of the initial zonal wind and initial balanced height ﬁeld with a superimposed perturbation.....183 4.22 Divergence ﬁeld illustrating gravity wave propagation from the initial per- turbation at 4 and 6 hours.Results from meshless collocation approxima- tion with time step 15 seconds........................184 4.23 Divergence ﬁeld illustrating gravity wave propagation from the initial per- turbation at 8 and 10 hours.Results from meshless collocation approxi- mation with time step 15 seconds......................185 4.24 Height ﬁeld illustrating gravity wave propagation from the initial pertur- bation at 8 and 10 hours.Results frommeshless collocation approximation with time step 15 seconds..........................186 4.25 Meshless collocation solution of vorticity ﬁeld with nearly 15,000 colloca- tion nodes and a time step of 15 seconds.Plot of ﬁeld after 48 and 72 hours.....................................188 4.26 Meshless collocation solution of vorticity ﬁeld with nearly 15,000 colloca- tion nodes and a time step of 15 seconds.Plot of ﬁeld after 80 and 90 hours.....................................189 vi

Chapter 1 I ntroduction 1.1 Historical Context and Motivations The meshless collocation method for approximating solutions to partial diﬀer- ential equations (PDEs) is a recent and fast growing research area that spans many diﬀerent ﬁelds in applied mathematics,science and engineering.As the name sug- gests,it deals with computing the numerical solution of a PDE on a set of given data locations that are scattered throughout the domain of interest,all without the use of a computational mesh which are traditionally required in standard spectral,ﬁnite element,and ﬁnite diﬀerence methods.Instead,the method uses collocation in the sense that it poses the approximation to be satisﬁed exactly on a set of collocation points,or nodes,in the domain of interest and on the boundary. Historically,collocation methods for the solution of PDEs have been centered mathematically on a fairly simple approach to approximation.The methods typi- cally choose a ﬁnite dimensional approximation space of candidate solutions along with a ﬁnite collection of points in the domain and boundary (called collocation points or node) and aim at selecting the solution that satisﬁes the given PDE ex- actly at those points.A popular choice in the literature for the ﬁnite dimensional approximation space of candidate solutions are (orthogonal) polynomials up to a certain degree.While these methods have generally shown great success using such 1

polynomial spaces as Chebychev or Legendre polynomials (see Boyd [13]),adapting them to nontrivial domains which are either nonconvex,nonsmooth,or both has been a limiting drawback to the method due to the fact that the collocation points are required to be Gaussian-type quadrature points.While the method has been shown to converge ([13]),this type of collocation limits the method geometrically. 1.1.1 Why Meshless Collocation? Freedom to choose the collocation points is of course a highly desirable feature in collocation and hasn’t been available until the recent mathematical innovations of meshless collocation.In chapter 2,we investigate these innovations,which include the so-called Native Space theory of symmetric positive deﬁnite kernels,developed in the seminal paper by Schaback [44],and their connection with reproducing kernel Hilbert spaces.We will try to demonstrate why and how the theory of native spaces work in the context of scattered data approximation and,more generally,collocation for PDEs. As we will show,this approach to collocation enables the choice of a collection of collocation points that can be a rather general set of scattered data points satisfy- ing mild restrictions to ensure convergence.The ﬁnite dimensional space is the span of functions of the form Ψ(,x 1 ),...,Ψ(,x N ) where x 1 ,...,x N are the collocation nodes and Ψ:Ω ×Ω → R will be chosen to be a compactly supported symmetric positive deﬁnite kernel which satisﬁes high-order smoothness and algebraic spectral decay. 2

So why would one want to use meshless collocation for numerically solving PDEs in the ﬁrst place?Aren’t ﬁnite element and diﬀerence methods (FEM,FDM) powerful enough?After all,the theory of both methods reach back through the 1950s,with thousands of research papers and a slew of books on the subject.Fur- thermore,new innovations for FE solution and reﬁnement techniques are making way into many commercial software packages (FEMlab,FEMpack,etc.) for tackling large-scale/high-performance problems in all engineering ﬁelds,atmospheric science, physics,and so on. Motivations for employing meshless collocation might stem from the desire to approximate solutions to PDEs where boundaries to the domain of interest have either very complicated geometric structures or even move in time dependent prob- lems.As we hope to demonstrate in this thesis,another desirable feature of meshless collocation is its approximation robustness and fast convergence rates for smooth problems,as well as overall ease of implementation.One of the major advantages of meshless collocation over traditional and generalized ﬁnite element methods (see [7] for example) that we stress to communicate in this thesis is that meshless collo- cation does not require numerical quadrature for integration since integration is not performed in the collocation method. A grand challenge in the current trend of generalized ﬁnite element methods comes in selecting optimal quadrature points and weights for the numerical integra- tion over supports of the underlying basis functions.The introduction of quadrature then of course leads to additional numerical errors which can propagate throughout the global approximation.The fact that no integration is done in collocation greatly 3

simpliﬁes the implementation of the method and allows much freedom in selecting the basis kernels and the placement of collocation nodes.Furthermore,since no triangularization or rectangularization of the domain is required,collocation can be used on much more general smooth manifolds without the problem of domain discretization errors. The ﬁnal goal for this thesis will be to demonstrate numerically how and why meshless collocation can compete with standard computational methods for large- scale numerical solutions to nonlinear PDEs.For this,we tackle the problem of applying meshless collocation to a large-scale geophysical dynamics model. Two fundamental problems in numerically simulating Global Climate Mod- els (GCM) which have challenged researchers during the past few decades are the long-term stability requirements in the underlying numerical approximations of the climate model along with the sensitivity to small changes in regional scales of the model.Most GCMs in the past have had diﬃculty being able to simulate regional meteorological phenomena such as tropical storms,which play an important part in the latitudinal transfer of energy and momentum.This is partly due to the fact that climate models have traditionally employed spectral methods using spherical harmonics which are global and require excessively large resolution in order to in- herit any properties which can be used to study regional scale phenomenon (see Baer et al.[6]).This is a massive computational burden since the increase in reso- lution must be done globally due to the nature of the numerical method.In order to tackle these two problems in a computationally eﬃcient manner,the high-order convergence and approximation properties of global spectral methods would ulti- 4

mately need to be coupled with the ability to locally reﬁne approximation results of the model in certain regions of the global domain. In the ﬁnal part of the thesis,we propose,implement,and experiment with a meshless collocation paradigm for use in the parallel high-performance simulation of nonlinear geophysical models while keeping these two problems that have chal- lenged researchers in computational geophysics and climatology in mind.Due to its simplicity while still retaining some of the nonlinear challenges of larger,more complex geophysical models,our geophysical model of choice will be the rotational shallow-water equations on the sphere. Ultimately,we wish to show that our proposed meshless collocation method can compete with the many models and benchmarks published in today’s high- performance scientiﬁc computing industries,and can also provide an attractive al- ternative to standard ﬁnite-element techniques for regional and global modeling of geophysical ﬂuid dynamics. 1.2 Thesis Outline This dissertation thesis has three main goals:1) To explore the anatomy of meshless collocation approximation methods that have recently gained attention in the numerical analysis community;2) Numerically demonstrate why the mesh- less collocation method should clearly become an attractive alternative to standard ﬁnite-element methods due to the simplicity of its implementation and its high- order convergence properties;3) Propose a meshless collocation method for large 5

scale computational geophysical ﬂuid dynamics models. I n chapter 2 of the thesis,we give a tour of some of the theoretical highlights of meshless collocation that we hope will demonstrate the robust approximation power of the method.Much of the theory of meshless collocation that is featured in this thesis was developed by Schaback and Wendland the past decade in a combination of papers.We summarize the important aspects of the theory and give detailed proofs for the main results. In the second part of chapter 2,we will explore implementational issues of meshless collocation and give a suite of numerical experiments for the approximation method which will aim at verifying and validating many of the theoretical claims and results discussed in the ﬁrst part of the chapter.We hope to demonstrate the computational robustness of meshless collocation for diﬀerent types of domains which are convex,nonconvex,smooth,and nonsmooth where we focus primarily on determining numerical convergence rates for the method while using diﬀerent collocation node distributions. In the ﬁnal part of the second chapter,we provide a computational comparison between the meshless collocation method and the standard ﬁnite-element method with piecewise linear elements on a few diﬀerent test problems to assess the diﬀer- ences in numerical convergence and stability issues.As already mentioned,one of the major advantages of meshless collocation over traditional and generalized ﬁnite element methods that we will continue to highlight in this thesis is that meshless collocation does not require numerical quadrature for integration since integration is not performed in the collocation method.Clearly,this is one desirable feature 6

since it renders implementational issues much easier to handle computationally. In an eﬀort to demonstrate that meshless collocation can compete with spectral/ﬁnite- element methods in regards to numerical robustness and computational speed for solving large-scale problems in geophysical dynamics problems on the sphere,in the last two chapters of the thesis,we introduce a new meshless collocation method for solving the rotational shallow-water equations on the sphere.The method we pro- pose is quite versatile in that it can be constructed using any set of collocation points in the domain.Being roughly based on the theory of pseudospectral approximation, this meshless collocation method seeks to approximate pointwise values and their derivatives by using a diﬀerentiation matrix construction similar to pseudospectral methods.One of the advantages that we attempt to demonstrate is that the method is not only fast and easy to implement,but also that the matrices resulting from the linear systems in conjuction with the semi-implicit time stepping scheme that we propose are symmetric and positive deﬁnite.This enables fast parallel conjugate gradient solvers for obtaining the solution at each collocation node. We begin chapter 3 by ﬁrst discussing the geophysical model that we will use,namely the rotational shallow-water equations on the sphere,and then give its discretization on the so-called cubed-sphere followed by a semi-implicit time stepping scheme to integrate the geophysical model in time.Lastly,we discuss in detail the construction of the meshless collocation approach using compactly supported radial basis functions.We show how to apply the method at each semi-implicit time step to yield a symmetric positive deﬁnite system that can be solved using conjugate gradient. 7

In the ﬁnal part of the thesis,we provide numerical veriﬁcation and validation of the meshless collocation scheme applied to the rotational shallow-water equa- tions on the sphere introduced in chapter 3.Our goal is to show computationally that this proposed model can compete with existing high performance methods for approximating the shallow-water equations such as the SEAM(spectral-element at- mospheric model) developed at NCAR all while highlighting the advantages and disadvantages of the method.A detailed analysis of the parallel implementation of the model,along with the introduction of parallel algorithmic routines for the high-performance simulation of the model will be given.We analyze the program- ming and computational aspects of the model using Fortran 90 and the message passing interface (mpi) library along with software and hardware speciﬁcations and performance tests.Details from many aspects of the implementation in regards to performance,optimization,and stabilization will be given. A theoretical discussion of regional modeling in geophysical systems will then introduce the ﬁnal numerical experiments section of the thesis.In order to verify the mathematical correctness of the algorithms presented and to validate the per- formance of the meshless collocation shallow-water model,we conclude the thesis with numerical experiments on some standardized test cases for the shallow-water equations on the sphere using the proposed method.These test cases,introduced by Williamson et al.in [71],are now considered the standard test suite for analyzing the performance of newly proposed numerical schemes for the spherical SWEs. We end the thesis with a conclusion summarizing the numerical and theoret- ical eﬀorts of this project including a discussion on some of the advantages and 8

disadvantages that we have experienced using meshless collocation as a method for solving large-scale PDEs.Directions into further ongoing developments and future research in the ﬁeld of meshless collocation will also be given. 9

Chapter 2 T he Meshless Collocation Method 2.1 Introduction The meshless collocation method for approximating solutions to partial dif- ferential equations (PDEs) is a recent and fast growing research area that spans many diﬀerent ﬁelds in applied mathematics,science and engineering.As the name suggests,it deals with computing the numerical solution of a PDE on a set of given data locations that are scattered throughout the domain of interest,all without the use of a computational mesh as in the classical ﬁnite element and diﬀerence meth- ods.The method uses collocation in the sense that it poses the approximation to be satisﬁed exactly on a set of collocation points,or nodes,in the domain of interest and on the boundary. Motivations for employing meshless collocation might stem from the desire to approximate solutions to PDEs where boundaries to the domain of interest have either very complicated geometric structures or even move in time dependent prob- lems.As we hope to demonstrate,we take interest in meshless collocation namely due to its approximation robustness and ease of implementation,and also to the fact that approximation reﬁnement with collocation is rather simple to implement as we will see;simply increase the number of collocation nodes in the domain,no need to reﬁne a mesh. 10

The theory behind the meshless collocation method that we use in this the- sis actually stems from the theory of scattered data approximation (an excellent resource to the ﬁeld of scattered data approximation is provided by H.Wendland in [66].) Scattered data approximation heavily relies on the theory of reproducing kernel Hilbert spaces and so-called native spaces of positive deﬁnite functions.The notion of native spaces of positive deﬁnite functions was initially introduced by Sch- aback in [46] to provide a framework for the approximation of functions u from a certain Hilbert space H.The approximation was assumed to be done on scattered samples of the function u and thus an interpolant was created out of positive deﬁnite kernels to interpolate the scattered data.The idea of the native spaces of the kernel was to show equivalence with the Hilbert space in regards to the normof the Hilbert space.This way,analysis of error estimates and stability could be done directly in the native space. In this chapter,we wish to investigate the symmetric meshless collocation method as an attractive alternative to standard ﬁnite element methods by highlight- ing some of the main features which makes this collocation method such a numerical success.In the ﬁrst part of the chapter,we review results from reproducing kernel Hilbert spaces and the notion of native spaces for positive deﬁnite functions and discuss their properties which provide much of the theoretical backbone of meshless collocation.We then give a fairly detailed analysis of the main fundamental error estimate for scattered data approximation in native spaces which is the underly- ing prerequisite to understanding the success of meshless collocation.The third part of the chapter then discusses the symmetric meshless collocation method for 11

boundary-valued elliptic partial diﬀerential using the theory derived from scattered data approximation in native spaces of positive deﬁnite kernels.Deriving the main error estimate for meshless collocation will then conclude the theoretical portion of the chapter.For the ﬁnal part of the chapter,we take an in-depth numerical tour of symmetric meshless collocation which will aim at providing further insight into the numerical robustness of the collocation method.We will give an explicit example of how the collocation method is constructed computationally and applied to a simple elliptic PDE.The numerical convergence rate for a few example problems will then be given along with a section dedicated to comparing the performance of the ﬁnite element method and the meshless collocation method for a couple elliptic problems on both smooth and nonsmooth nonconvex domains.We conclude the numerical section with a study on the numerical stability of the collocation method. 2.2 Theory of Meshless Collocation 2.2.1 Preliminaries Before we begin the discussing the tools needed for the meshless collocation method,we must mention some notation that will be used for the domain Ω on which we work.Unless otherwise stated,we will deﬁne Ω to be an open bounded connected set in R 2 (which we will frequently call a domain) and assume in addition that Ω satisﬁes an interior cone condition and has a Lipschitz boundary ∂Ω.We will use the following deﬁnition of the cone condition. Deﬁnition The set Ω satisﬁes an interior cone condition if there exists an angle 12

θ ∈ (0,π/2) and a radius r > 0 such that for every x ∈ Ω a unit vector ξ(x) exists such that the cone C(x,ξ(x),θ,r):= {x +λy:y ∈ R 2 ,y 2 = 1,y T ξ(x) ≥ cos(θ),λ ∈ [0,r]} (2.1) is contained in Ω. As we will see,the cone condition property will become important in the analysis of the meshless collocation method as it allows for diﬀerent approximation results to hold which we will discuss later in the thesis. Fundamental to the concept of the meshless collocation method is the set of collocation nodes on which approximations are computed.To this end,we deﬁne a set of N pairwise distinct points (or simply nodes as we will sometimes call them) as X N = {x N 1 ,...,x N N } ⊆ Ω,where the superscript on each point x N j ∈ X N denotes the dependence on N.For a given integer N,we associate with the set X N a measure h X N ,Ω deﬁned by h X N ,Ω = sup x∈Ω min x N j ∈X N x −x N j

2 .(2.2) We will call this the point saturation measure or ﬁll distance of X N and it can be interpreted as follows:for any x ∈ Ω,there is a node x N j ∈ X N within a distance at most h X N ,Ω . It is natural for convergence of approximations to require that the distribution of points X N has the property that as N →∞,then h X N ,Ω →0.In other words the distribution of points in X N ⊆ Ω should “cover” Ω rather well.In order to help us in determining if the domain Ω is “covered” suﬃciently well,we introduce another useful quantity associated with the point distribution X N .This is the separation 13

distance deﬁned as q X N := 1 2 m in j=k x N j −x N k

2 ,(2.3) which is half the shortest distance between any two distinct points in X N .Using q X N and h X N ,Ω ,we can deﬁne the notion of quasi-uniform for a family of sets X N . Deﬁnition We say that the family of sets X N ⊆ Ω is quasi-uniform with respect to a constant c > 0 if q X N ≤ h X N ,Ω ≤ cq X N (2.4) for any N > 1. The quasi-uniform property for the family of sets X N ensures that the separation distance q X N and the ﬁll distance h X N ,Ω are equivalent in that their ratio h X N ,Ω /q X N can be bounded below by 1 and above by a constant c for any N > 1. To see the importance of the quasi-uniformproperty,let us ﬁrst consider a uni- formfamily of centers X N in the following example.Let Ω = (0,1) 2 and deﬁne X N := (1/N)Z 2 ∩Ωfor N ≥ 2 (for example X 3 := {(1/3,1/3),(1/3,2/3),(2/3,1/3),(2/3,2/3)}. Then the separation distance is q X N = 1 2N w hile the ﬁll distance is h X N ,Ω = √ 2 N a nd thus the quasi-uniform constant is c = 2 √ 2.Obviously in the uniform case,the n odes in X N “cover” Ω arbitrarily well in that no point x ∈ (0,1) 2 is greater than a distance of √ 2q X N to its nearest neighboring node in X N .In the quasi-uniform case,we would thus like for the constant c to be as close to 2 √ 2 as possible;the c loser c is to 2 √ 2,the closer X N is to being purely uniform.This ensures that the nodes in X N are not too close together and at the same time “cover” Ω rather well as N →∞. 14

We note that the left-hand side of the inequality in (2.4) is not only a restriction on X N ,but also on Ω.There are instances in which the left-hand inequality does not hold true for an open bounded set Ω and a given X N .However,if Ω satisﬁes the interior cone condition with radius r > 0 and q X N < r,then it can be shown that q X N ≤ h X N ,Ω holds (see page 232 of Wendland [66]).Another instance in which the inequality holds is in the case Ω is convex. Without any chance of misunderstanding,we will often use throughout the remainder of this thesis an abbreviated notation for the point saturation and sep- aration distances by suppressing the notation of the dependence on X N and Ω by simply letting h:= h X N ,Ω and q:= q X N .We will also occasionally denote the set of nodes X N by X:= {x 1 ,...,x N }. 2.2.2 Radial Functions Before we deﬁne the notion of reproducing kernels and native spaces,we discuss radial functions which will be used to derive the reproducing kernels we are interested in.In this thesis,we will consider classes of reproducing kernels that are radial functions. Deﬁnition A function Ψ 0 :R 2 → R is said to be radial if there exists a function ψ:[0,∞) →R such that Ψ 0 (x) = ψ(x 2 ),for all x ∈ R 2 . Speciﬁcally,we are interested in radial functions Ψ 0 ∈ L 1 (R 2 ) ∩C(R 2 ) possessing a multivariate Fourier transform deﬁned as