A Comparison of Numerical Algorithms for Fourier Extension of the First, Second, and Third Kinds

The range of Fourier methods can be significantly increased by extending a nonperiodic function f(x) to a periodic function f̃ on a larger interval. When f(x) is analytically known on the extended interval, the extension is straightforward. When f(x) is unknown outside the physical interval, there is no standard recipe. Worse still, like a radarless aircraft groping through fog, the algorithm may wreck on the “mountain-in-fog” problem: a function f(x) which is perfectly well behaved on the physical interval may very well have singularities in the extended domain. In this article, we compare several algorithms for successfully extending a function f(x) into the “fog” even when the analytic extension is singular. The best third-kind extension requires singular value decomposition with iterative refinement but achieves accuracy close to machine precision.