A basic N-body code was developed with the particle-particle (PP) method and simple Euler time stepping. The code's time complexity was analyzed as below:
Being a PP code, its time complexity is O(N^2) and based on the runtimes recorded this code would take about 65 years to run for a million particles (10^6) and about 230 days to run for 10^5 particles which is our required threshold for good impression. So, a lot of work has to be done.
The ways to reduce runtime are:
1. Use a more accurate time-stepping method which allows for larger time steps with tolerable numerical diffusion
2. Change the time complexity to Nlog(N) using Particle-Mesh method instead of particle-particle. This method uses FFT and iFFT. With Nlog(N) complexity, assuming that it does not increase the time for each calculation very significantly, the current MATLAB code could complete a simulation for a million particles in 9.5 days! Using FFT might increase the time for every calculation upto 5-10 times, so may be 90 days.
3. Rewriting the Code in FORTRAN. Unknown speed up. I would expect it to be at least 5 times? May be.
4. Parallelization: Speed up of at least 2-3 times.
If we are able to implement all of these steps (which is unlikely since we only have about 45 days and we also have to factor in time for studying for finals, homeworks and doing science with this code) we could reduce the runtime to 90/15=6 days for a million particles! This corresponds to 12 hours for 10^5 particles.
These numbers might be revised once we get the hang of the actual amount of speed up FORTRAN can provide.
Oh yes, and how can I forget some other stuff we have to include:
1. Variable time-stepping depending on the velocities and separations of particles
2. Collisions - Inelastic?
Lets go about implementing these improvements step by step.
The ways to reduce runtime are:
1. Use a more accurate time-stepping method which allows for larger time steps with tolerable numerical diffusion
2. Change the time complexity to Nlog(N) using Particle-Mesh method instead of particle-particle. This method uses FFT and iFFT. With Nlog(N) complexity, assuming that it does not increase the time for each calculation very significantly, the current MATLAB code could complete a simulation for a million particles in 9.5 days! Using FFT might increase the time for every calculation upto 5-10 times, so may be 90 days.
3. Rewriting the Code in FORTRAN. Unknown speed up. I would expect it to be at least 5 times? May be.
4. Parallelization: Speed up of at least 2-3 times.
If we are able to implement all of these steps (which is unlikely since we only have about 45 days and we also have to factor in time for studying for finals, homeworks and doing science with this code) we could reduce the runtime to 90/15=6 days for a million particles! This corresponds to 12 hours for 10^5 particles.
These numbers might be revised once we get the hang of the actual amount of speed up FORTRAN can provide.
Oh yes, and how can I forget some other stuff we have to include:
1. Variable time-stepping depending on the velocities and separations of particles
2. Collisions - Inelastic?
Lets go about implementing these improvements step by step.
No comments:
Post a Comment