The fast Gauss transform with complex parameters (Q706837)

For given coefficients \(q_k \in {\mathbb C}\) and source knots \(s_k \in [-1/2,\,1/2]\) \((k=1,\dots,N)\), the authors evaluate approximately the sum \[ G(x)=\sum_{k=1}^N q_k \, \exp(-\alpha | x-s_k| ^2) \] at the target knots \(x_j \in [-1/2,\, 1/2]\) \((j=1,\dots, M)\), where \(\alpha = a - \text{ i}b\) \((a>0,\, b\in {\mathbb R})\) is a complex parameter. Such sums appear in numerical computation of integrals \[ Q(x)=\int q(s)\, \exp(-\alpha | x-s| ^2)\, \text{ d}s. \] Using a fast algorithm of discrete Fourier transform for nonequally spaced knots, this paper presents a fast Gauss transform with \({\mathcal O}(N\,\log N + M)\) flops. Remark of the reviewer: The general fast summation algorithm developed by \textit{D. Potts, G. Steidl} and \textit{A. Nieslony} [Numer. Math. 98, 329--351 (2004; Zbl 1056.65146)] can be specified for the Gaussian kernel with complex parameter \(\alpha\) to obtain a fast Gauss transform with \({\mathcal O}(N+M)\) flops.