The Fast and Free Memory Method for the efficient computation of convolution kernels

Understand

We introduce the Fast Free Memory method (FFM), a new fast method for the numerical evaluation of convolution products.

• Inheriting from the Fast Multipole Method, the FFM is a descent-only and kernel-independent algorithm.
• We give the complete algorithm and the relevant complexity analysis.
• While dense matrices arise normally in such computations, the linear storage complexity and the quasi-linear computational complexity enable the evaluation of convolution products featuring up to one billion entries.