Exact augmented RBF-FD weights for a local differential functional

The exact augmented RBF finite-difference weight procedure has the following inputs: a dimension $d\ge 1$; an integer polynomial degree $r\ge 0$; a finite ordered stencil $Y=(y_1,\dots ,y_N)\subset {\mathbb{R}}^d$ of distinct sites that is $(r+1)$-unisolvent for ${\mathrm{\Pi }}_r({\mathbb{R}}^d)$; a real kernel $K$ strictly conditionally positive definite of order $r+1$; an ordered basis $p_1,\dots ,p_J$ of ${\mathrm{\Pi }}_r({\mathbb{R}}^d)$; a center $x\in {\mathbb{R}}^d$; a homogeneous constant-coefficient differential functional $L={\sum }_{\mathrm{\mid }\alpha \mathrm{\mid }=t}{c}_{\alpha }{D}^{\alpha }$ with $0\le t\le r$; and a neighborhood of $x$ on which every section $z\mapsto K(z,y_i)$ has continuous derivatives through order $t$. Here $\alpha \in {\mathbb{N}}_0^d$, $\mathrm{\mid }\alpha \mathrm{\mid }={\sum }_j{\alpha }_j$, and $D^{\alpha }$ is the corresponding partial derivative. All arithmetic in this procedure is exact real arithmetic.

The input is supplied with total, correct oracles for admissibility and exact evaluation. The admissibility oracle returns whether all the stated input conditions hold, including the polynomial-basis condition, global strict conditional positive definiteness, and continuous section differentiability on the supplied neighborhood. On an affirmative answer, the evaluation oracles return the exact real values $K(y_i,y_j)$, $p_j(y_i)$, $(L_{z}K(z,y_i)){\mathrm{\mid }}_{z=x}$, and $(L{p}_j)(x)$ for the finitely many requested indices. Oracle calls are primitive operations in this model; neither global kernel admissibility nor differentiation is claimed to be decidable by real arithmetic alone.

Query the admissibility oracle. If it returns false, return inadmissible-input. Otherwise use the evaluation oracles to form $P_{ij}=p_j(y_i)$, $b_i=(L_{z}K(z,y_i)){\mathrm{\mid }}_{z=x}$, ${\mathrm{\ell }}_j=(L{p}_j)(x)$, and $M=\left[\begin{array}{cc}{K}_Y& P\\ P^{\mathsf{T}}& 0\end{array}\right],g=\left[\begin{array}{c}b\\ ell\end{array}\right]\mathrm{.}$ Solve $Mz=g$ by exact Gaussian elimination with deterministic nonzero-pivot row selection: set $A=M$, $c=g$, and $n=N+J$. For $k=1,\dots ,n$, choose the least $i\ge k$ with $A_{ik}\mathrm{\ne }0$; if none exists, return singular-system. Swap rows $i$ and $k$ in both $A$ and $c$. For each $j=k+1,\dots ,n$ in increasing order, set $\mu =A_{jk}\mathrm{/}{A}_{kk}$, replace row $j$ by row $j-\mu {\mathrm{r}\mathrm{o}\mathrm{w}}_k$ in $A$ and $c$, and set $A_{jk}=0$. After all pivots, set $z_n=c_n\mathrm{/}{A}_{nn}$; then, for $k=n-1,n-2,\dots ,1$ in decreasing order, set $z_k=(c_k-{\sum }_{j=k+1}^n{A}_{kj}{z}_j)\mathrm{/}{A}_{kk}$. Return success with the first $N$ coordinates $w$ of $z$ and the remaining $J$ polynomial multipliers. The stated strict hypotheses imply that singular-system is unreachable, as proved by Strict positive and conditionally positive augmented interpolation systems are invertible.

The returned $w$ is an exact mathematical weight vector. The nonsingularity lemma Strict positive and conditionally positive augmented interpolation systems are invertible makes singular-system unreachable for every input that passes the stated strict hypotheses. This definition makes no floating-point stability or solver-error claim.