Re: [OT] Hints for an algorithm - avoiding O(n^2)

[jtg <jtg77@poczta.onet.pl>]

Jano wrote:

> Sorry for the off-topic, but this is the only group I read frequently
> that I'm sure is packed with knowledgeable people.
> 
> The problem is a simple one: I'm planning to write a simulator of
> sideral-like objects using the Newton laws (precision is not a top
> priority). The obvious way is to compute the force interactions
> between each pair of objects, sum them all, and iterate over... but
> this is O(n^2). To be precise, there are n(n-1)/2 forces to be
> computed if I'm right (n the number of objects).
> 
> I was wondering if you know of another approach more efficient. A
> simple hint is enough, I'll look further as necessary once in the
> right path.
> 
> I'm having some thoughts about making a discrete division of the space
> and compute the potential field, but the idea is not mature enough...
> I'm not sure if the loss of precision will be too big, or if the
> results will not be similar in time (I'm planning to manage about
> 1000-2000 objects simultaneously).
> 

Two ideas

1. You can assign groups of objects. For every group you can calculate
its mass and the center of the mass. Then you calculate acceleration
between all the objects in the same group, and then acceleration
between all the groups. Of course you apply group acceleration to
every object in that group. For instance you can assign sqrt(N) groups
of sqrt(N) objects, and then you have
    O(sqrt(N)^2) + sqrt(N)*O(sqrt(N)^2) = O(N*sqrt(N))
But there are still some problems to solve for instance group
boundary can divide two masses which are close to each other.
You can use for instance more intelligent clustering algs,
skip group interaction between adjacent groups (calculating
object interactions instead) or even apply more levels
of complexity (objects, small groups, bigger groups etc.)

2. You are going to make a simulation, but you think only
about static calculation of gravity forces. Wrong! It is possible
to do the calculations between objects much less frequently,
while mantaining accuracy and fluent object movement, if you
use some tricks. For instance you can adaptively change
time step, making it small when needed (if two masses come very
close, you calculate their paths more precisely). This will protect
your simulation when two masses go very close. You can also
make some asynchronous calculations (not in time steps),
i.e. calculate gravitational pull for every object, in every time
  step just integrate it, and from time to time update it - more
frequently for close objects, less frequently for distant objects.
However it is memory intensive.

Connecting these two ideas would be VERY effective. Of course
you can calculate group interactions less frequently than
object-in-group interactions. And since you can treat each group
as single object, asynchronous calculations do not demand
much memory in this case.

If you find these ideas helpful, please e-mail me, I'm curious
about the results. :-)