Couldn't we use a fast Fourier transform to do the same computation with O(n lg n) work?
kayvonf
@cacay: Yes, I believe there are frequency-space methods for such computations (but I'm far from an expert on their use in this domain). Could you elaborate further with an example for the class?
cacay
A Fourier transform is a fast way to do n^2 multiplications similar to what we need here. However, it generates a different output and there is the problem of dividing by the radius squared. So this is not as immediate as I initially though.
ak47
These notes from 15-451 describe how to use an FFT to multiply two n-degree polynomials in n log n time.
I agree that this problem seems very similar but naively it seems like no matter what you do an exact calculation will rely on knowing n^2 distance values.
pmassey
If anyone's interested, I did research in the cosmology department here studying the formation of dark matter halos, and we intensely used nbody simulations. A very interesting application of second-order Lagrangian Perturbation theory leads to an algorithm that runs INCREDIBLY fast while giving results ~70% accurate of a true FFT nbody simulation. It's called PINOCCHIO (PINpointing Orbit-Crossing Collapsed HIerarchical Objects), and it's done on simulation sizes of (512-1024)^3 particles.
Couldn't we use a fast Fourier transform to do the same computation with O(n lg n) work?
@cacay: Yes, I believe there are frequency-space methods for such computations (but I'm far from an expert on their use in this domain). Could you elaborate further with an example for the class?
A Fourier transform is a fast way to do n^2 multiplications similar to what we need here. However, it generates a different output and there is the problem of dividing by the radius squared. So this is not as immediate as I initially though.
These notes from 15-451 describe how to use an FFT to multiply two n-degree polynomials in n log n time.
http://www.cs.cmu.edu/~15451/lectures/lec27/fft-notes.pdf
I agree that this problem seems very similar but naively it seems like no matter what you do an exact calculation will rely on knowing n^2 distance values.
If anyone's interested, I did research in the cosmology department here studying the formation of dark matter halos, and we intensely used nbody simulations. A very interesting application of second-order Lagrangian Perturbation theory leads to an algorithm that runs INCREDIBLY fast while giving results ~70% accurate of a true FFT nbody simulation. It's called PINOCCHIO (PINpointing Orbit-Crossing Collapsed HIerarchical Objects), and it's done on simulation sizes of (512-1024)^3 particles.
source
Very cool @pmassey. Thanks for sharing!