Fast Discrete Laplace Transforms

Discrete Laplace transforms (DLT) are useful in certain Monte Carlo data analysis algorithms [1]. The DLT with N inputs and N outputs has a nominal computational cost of O(N²). There exist fast approximate DLT algorithms with O(N) cost, but these algorithms do not satisfy appropriate accuracy criteria for Monte Carlo data analysis applications in which the inputs and outputs may range over 100 orders of magnitude. This work presents a fast DLT algorithm satisfying the necessary criteria. This algorithm combines a bottom-up strategy, based on the Taylor expansion of the Laplace transform kernel, with a top-down strategy that omits terms predetermined to be negligible. The overall effort is O(N) when the source and target points are very dense or very sparse, and appears to be O(N^1.5) in the intermediate regime. Our algorithm achieves the same accuracy as brute-force evaluation, and is typically 10–100 times faster.

[1] J. Ferkinghoff-Borg, Eur. Phys. J. B 29, 481-484 (2002)

[2] Y. L. Loh, Fast discrete Laplace transforms, J. Comput. Math. Data Sci. 8, 100082 (2023)