Plans on Implementing FastSum

[chaithyagr]

Hello
Thank you so much for your interesting project. I was curious if there are plans to implement NUFFT based fast sum from https://madoc.bib.uni-mannheim.de/1734/1/276_2003_bearb.pdf

Implementations already exists in nfft3 (https://github.com/NFFT/nfft/tree/develop/applications/fastsum) for this and I was curious if you had same plans and if I could help in getting it up as it has wide applications.

[ahbarnett]

Dear chaithyagr,
I moved you over to a Discussion, since it's about applications. I just lost what I wrote. The point was this: I checked out that paper (also by the same group as nfft3), and the algorithm is standard, also known as spectral Ewald.
It splits the kernel into local (direct) plus Fourier (done by a pair of NUFFTs, or their equivalent).
It is used in groups of E Lindahl (GROMACS), other MD groups, A-K Tornberg and A. Donev in Stokes hydrodynamics, etc.
The local part is only O(N) if there is not much clustering, but if the nodes are clustered the cost can approach O(N^2).
In contrast the FMM remains O(N) for arbitrary clustering.
The problem is there are too many kernels (GP covar, RBF, PDE kernels) to implement in software.
I suggest you take the nfft3 fastsum C codes and swap out nfft3 calls with FINUFFT C-interface calls, for now.
They have set up plenty of kernels in their code. All you need to know is their Fourier transforms.

Maybe you can make a tutorial on how to do this, and we'll add it to our tutorials? Best, Alex

[chaithyagr]

Seems good, I had done this with gpuNUFFT backend. Ill see if I can move it to cufinufft.

[ahbarnett]

If you end up writing this application of cufinufft, let us know. We are tweaking the cufinufft interfaces to improve consistency with finufft.