Fast evaluation of real and complex exponential sums
For researchers in computational mathematics, this provides a faster method for evaluating oscillatory integral transforms and polynomials in the complex unit disk.
The paper proposes a fast Fourier-Laplace transform for efficient evaluation of real and complex exponential sums, combining butterfly and hierarchical approximations. Numerical experiments validate the theoretical results.
Recently, the butterfly approximation scheme and hierarchical approximations have been proposed for the efficient computation of integral transforms with oscillatory and with asymptotically smooth kernels. Combining both approaches, we propose a certain fast Fourier-Laplace transform, which in particular allows for the fast evaluation of polynomials at nodes in the complex unit disk. All theoretical results are illustrated by numerical experiments.