LAMMPS kspace_styles Ewald and PPPM both compute a structure factor (in parallel). The Ewald sum does this in the direct manner, and in fact does scale (non-optimally) as N^2. PPPM interpolates atoms to a mesh and uses FFTs, which gives it a N log(N) scaling. It probably wouldn’t be too hard to modify ewald.cpp or pppm.cpp to get what you want…
This (the method Carsten Svaneborg described to calculate the structure factor) is exactly what the Ewald sum in LAMMPS does…
Hi, Carsten. Sorry for the very belated reply. Thanks a lot for pointing this out! Unfortunately we require M^3 of order N, so I guess O(N^2) it is. But it is good to know, and if we ever can use a smaller M, we’ll put this info. to good use.
Thanks everyone for all the input!