Home » Technology » Scientific Computing » Won't You Be My Neighbor?

Won't You Be My Neighbor?

© Adam Hughes

In our latest go around with the planetary simulation problem, we developed a way to calculate the force of interaction between two bodies in our imaginary solar system. In this instance, the pairwise forces boiled down to a pretty simple expression which was dependent on the distance between the planets. Along the way, however, we learned that evaluating all the forces in this model system can be quite computationally expensive. In this article, we'll look at one way that scientists commonly use to overcome this situation.

As you'll recall, the real expense involved in a force calculation comes from the fact that in a model system with N particles, there are N*(N-1)/2 total pairwise forces to be calculated at each time step. For a ten- particle system, the resulting 45 force calculations are no big deal. Bump that system to 100 particles, and we're talking about 4950 evaluations at each time step. By the time the system grows to 1000 particles (not unreasonable for a large solar system with lots of moons, meteors, and the like), the number of force calculations per step is a hefty 499,500! This can obviously be a big drag on computational resources, but there are, fortunately, some approximations that can be made to make this situation much more tenable.

Recall that the force between two planets is given by K/(r*r), where K is just some constant number, and r is the distance between the planets. The important thing here is that the force scales like 1/(r*r), which basically means that it gets small really fast as the distance between the planets gets large. For instance, increasing the distance between two planets by a factor of 10, DECREASES the force felt by one due to the other by a factor of 100!

This is a very fortuitous phenomenon for the computational scientist. It is pretty easy to imagine that the force between two planets who are 10 million miles apart will be very, very small compared to the force between planets who may be only 1 million or even several hundred thousand miles apart. It is possible, therefore, to ignore the interactions which take place outside of some sphere of importance without much loss in accuracy. This focus sphere can be though of as a "neighborhood" the planets inside of which the can interact with each other. A planet's neighbor list is said to consist of each planet that lies inside its sphere. The use of neighbor lists can result in significant computational savings and will be examined in some detail next week.

The copyright of the article Won't You Be My Neighbor? in Scientific Computing is owned by . Permission to republish Won't You Be My Neighbor? in print or online must be granted by the author in writing.