Summation of zonal functions on the sphere

Given $M,N \in \ensuremath{\mathbb{N}}$ , arbitrary source nodes $\ensuremath{\boldsymbol{\eta}}_k \in \S^2$ and real coefficients $\alpha_k\in\ensuremath{\mathbb{R}}$ , evaluate the sum

$$g\left(\ensuremath{\boldsymbol{\xi}}\right) := \sum_{k = 1}^N \al... ...eft(\ensuremath{\boldsymbol{\eta}}_k \cdot \ensuremath{\boldsymbol{\xi}}\right)$$

at the target nodes $\ensuremath{\boldsymbol{\xi}}_j\in\S^2$ , $j=1,\hdots,M$ . The naive approach for evaluating this sum takes ${\cal O}(MN)$ floating point operations if we assume that the zonal function $K$ can be evaluated in constant time or that all values $K(\ensuremath{\boldsymbol{\eta}}_k \cdot \ensuremath{\boldsymbol{\xi}}_j)$ can be stored in advance.

In contrast, our scheme is based on the nonequispaced fast spherical Fourier transform, has arithmetic complexity ${\cal O}(M+N)$ , and can be easily adapted to such different kernels $K$ as

1. the Poisson kernel $Q_{h}:[-1,1] \rightarrow \ensuremath{\mathbb{R}}$ with $h \in (0,1)$ given by
   $$Q_{h}(x) := \frac{1}{4\pi} \frac{1-h^2}{\left(1-2 h x+h^2\right)^{3/2}},$$

2. the singularity kernel $S_{h}:[-1,1] \rightarrow \ensuremath{\mathbb{R}}$ with $h \in (0,1)$ given by
   $$S_{h}(x) := \frac{1}{2\pi} \frac{1}{\left(1-2 h x +h^2\right)^{1/2}},$$

3. the locally supported kernel $L_{h,\lambda}:[-1,1] \rightarrow \ensuremath{\mathbb{R}}$ with $h \in (-1,1)$ and $\lambda \in \mathbb{N}_0$ given by
   $$L_{h,\lambda}(x) := \left\{\begin{array}{l@{\quad \text{if} \quad... ...h)^{\lambda+1}}\left(x-h\right)^{\lambda} & h & < x \le& 1, \end{array}\right.$$
   or
4. the spherical Gaussian kernel $G_{\sigma}:[-1,1] \rightarrow \ensuremath{\mathbb{R}}$ with $\sigma>0$
   $$G_{\sigma}(x) := {\,\rm {e}}^{2\sigma x-2\sigma}\,.$$

For details see [31], all corresponding numerical examples can be found in applications /fastsumS2.