CS 170: Computing for the Sciences and MathematicsAdministriviaN-Body Simulations IN BodiesN-Body Problems1-Body Problem2-Body Problem3-Body ProblemN-Body Problems (N > 3)Slide 10Force #1Force #2Force #3Force #4Force #5Force #6Force #N-1Slide 18Aside: Big-O NotationBig-O: Dropping the Low TermBig-O: Dropping the ConstantSlide 22O(N2) ForcesHow to Calculate?AlgorithmExample: GalaxSeeHOMEWORK!Algorithm – Parallel VersionParallelization of the Direct Force AlgorithmAmdahl's Law and optimal efficiencyParticle-Mesh and Particle-Particle Particle-MeshParticle Mesh AlgorithmSlide 33Step 1: Generate Density Distribution FunctionTranslate N bodies onto gridOverlay grid onto spaceSoften particlesMap density distribution onto gridSolve for potential of densityStep 2/3/4: Solving Poisson’s equation using Fourier TransformStep 5: Solve for the force using the potentialWin with PMPM IssuesOther Concerns when using PMImprovements for nearest neighborsTimingN-Body ICS 170:Computing for the Sciences and MathematicsAdministriviaTodayN-Body SimulationsHW #10 assignedOngoingProject!A Final Exam time solutionModeling the Interactions of Lots of ThingsN-Body Simulations IN Bodies4N-Body ProblemsAn N-body problem is a problem involving N “bodies” – that is, particles (stars, atoms) – each of which applies some force to all of the others.For example, if you have N stars, then each of the N stars exerts a force (gravity) on all of the other N–1 stars.Likewise, if you have N atoms, then every atom exerts a force (nuclear) on all of the other N–1 atoms.51-Body ProblemWhen N is 1, you have a simple 1-Body Problem: a single particle, with no forces acting on it.Given the particle’s position P and velocity V at some time t0, you can trivially calculate the particle’s position at time t0+Δt:P(t0+Δt) = P(t0) + VΔtV(t0+Δt) = V(t0)62-Body ProblemWhen N is 2, you have – surprise! – a 2-Body Problem: exactly 2 particles, each exerting a force that acts on the other.The relationship between the 2 particles can be expressed as a differential equation that can be solved analytically, producing a closed-form solution.So, given the particles’ initial positions and velocities, you can trivially calculate their positions and velocities at any later time.73-Body ProblemWhen N is 3, you have – surprise! – a 3-Body Problem: exactly 3 particles, each exerting a force that acts on the other.The relationship between the 3 particles can be expressed as a differential equation that can be solved using an infinite series, producing a closed-form solution, due to Karl Fritiof Sundman in 1912.However, in practice, the number of terms of the infinite series that you need to calculate to get a reasonable solution is so large that the infinite series is impractical, so you’re stuck with the generalized formulation.8N-Body Problems (N > 3)For N greater than 3 (and for N of 3 in practice), no one knows how to solve the equations to get a closed form solution.So, numerical simulation is pretty much the only way to study groups of 3 or more bodies.Popular applications of N-body codes include:astronomy (that is, galaxy formation, cosmology);chemistry (that is, protein folding, molecular dynamics).Note that, for N bodies, there are on the order of N2 forces, denoted O(N2).9N Bodies10Force #111AForce #212AForce #313AForce #414AForce #515AForce #616AForce #N-117AN-Body ProblemsGiven N bodies, each body exerts a force on all of the other N – 1 bodies.Therefore, there are N • (N – 1) forces in total.You can also think of this as (N • (N – 1)) / 2 forces, in the sense that the force from particle A to particle B is the same (except in the opposite direction) as the force from particle B to particle A.18Aside: Big-O NotationLet’s say that you have some task to perform on a certain number of things, and that the task takes a certain amount of time to complete.Let’s say that the amount of time can be expressed as a polynomial on the number of things to perform the task on.For example, the amount of time it takes to read a book might be proportional to the number of words, plus the amount of time it takes to settle into your favorite easy chair.C1•N + C219Big-O: Dropping the Low TermC1•N + C2When N is very large, the time spent settling into your easy chair becomes such a small proportion of the total time that it’s virtually zero.So from a practical perspective, for large N, the polynomial reduces to:C1•NIn fact, for any polynomial, if N is large, then all of the terms except the highest-order term are irrelevant.20Big-O: Dropping the ConstantC1•NComputers get faster and faster all the time. And there are many different flavors of computers, having many different speeds.So, computer scientists don’t care about the constant, only about the order of the highest-order term of the polynomialSeparates the cost of the fundamental algorithm from computer-specificsThey indicate this with Big-O notation:O(N)This is often said as: “of order N.”21N-Body ProblemsGiven N bodies, each body exerts a force on all of the other N – 1 bodies.Therefore, there are N • (N – 1) forces total.In Big-O notation, that’s O(N2) forces.So, calculating the forces takes O(N2) time to execute.But, there are only N particles, each taking up the same amount of memory, so we say that N-body codes are of:O(N) spatial complexity (memory)O(N2) time complexity22O(N2) Forces23Note that this picture shows only the forces between A and everyone else.AHow to Calculate?Whatever your physics is, you have some function, F(A,B), that expresses the force between two bodies A and B.For example, for stars and galaxies:F(A,B) = G·mA·mB / (dist(A,B)2)where G is the gravitational constant and m is the mass of the body in question.If you have all of the forces for every pair of particles, then you can calculate their sum, obtaining the force on every particle.From that, you can calculate every particle’s new velocity and position.24AlgorithmSet up initial positions and velocities of all particlesFOR time steps from 1 to TFOR each particle p from 1 to NInitialize force on p to 0.FOR each other particle q from 1 to Ncalculate force on p from qadd to p’s forcesCalculate the velocity of p based on forcesCalculate the position of p based on velocity25Example: