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

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

[Jano]

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).

Thanks!

P.s: It will be programmed in Ada... just to ease the OT a bit :)

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

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 876 bytes --]


"Jano" <402450@cepsz.unizar.es> a �crit dans le message de news:5d6fdb61.0403120115.7c102e3c@posting.google.com...
> 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).
>
If I remember my Newton laws correctly, you just need to compute the force between an object and the center of mass of all other
objects.
Hmmm.... not sure that it won't be O(n^2) still, but it might ease a bit.

-- 
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

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

[Stuart Palin]

Jean-Pierre Rosen wrote:
> 
> "Jano" <402450@cepsz.unizar.es> a �crit dans le message de news:5d6fdb61.0403120115.7c102e3c@posting.google.com...
> > 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).
> >
> If I remember my Newton laws correctly, you just need to compute the force
> between an object and the center of mass of all other objects.

No!  It is quite a straight-forward proof to show that for a
point inside a uniformaly dense sphere the mass at a greater
distance from the centre (than the point) has no net
gravitational effect on the point.

Also a counter-example is very easy to construct.  Consider
two large equal masses separated by a large distance.  Their
centre of mass (which will be the sum of their masses) is at
the mid-point of the shortest line joining them.  Another
mass placed a little way from this mid-point will in fact
feel little gravitational effect because the masses are a
long way away.  However, a calculation based on the centre
of mass would suggest there is a very strong force acting!


No help to the OP - they might be better off posting in an
astronomical group as this is more likely to be where people
with knowledge of any special algorithms might hang out.

--
Stuart Palin

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

[Stuart Palin]

Jean-Pierre Rosen wrote:
> 
> "Jano" <402450@cepsz.unizar.es> a �crit dans le message de 
news:5d6fdb61.0403120115.7c102e3c@posting.google.com...
> > 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).
> >
> If I remember my Newton laws correctly, you just need to compute the force
> between an object and the center of mass of all other objects.

No!  It is quite a straight-forward proof to show that for a
point inside a uniformly dense sphere the mass at a greater
distance from the centre (than the point) has no net
gravitational effect on the point.

Also a counter-example is very easy to construct.  Consider
two large equal masses separated by a large distance.  Their
centre of mass (which will be the sum of their masses) is at
the mid-point of the shortest line joining them.  Another
mass placed a little way from this mid-point will in fact
feel little gravitational effect because the masses are a
long way away.  However, a calculation based on the centre
of mass would suggest there is a very strong force acting!


No help to the OP - they might be better off posting in an
astronomical group as this is more likely to be where people
with knowledge of any special algorithms might hang out.

--
Stuart Palin

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

[Dmitry A. Kazakov]

On Fri, 12 Mar 2004 12:55:19 +0000, Stuart Palin <stuart.palin@0.0>
wrote:

>Jean-Pierre Rosen wrote:
>> 
>> "Jano" <402450@cepsz.unizar.es> a �crit dans le message de 
>news:5d6fdb61.0403120115.7c102e3c@posting.google.com...
>> > 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).
>> >
>> If I remember my Newton laws correctly, you just need to compute the force
>> between an object and the center of mass of all other objects.
>
>No!  It is quite a straight-forward proof to show that for a
>point inside a uniformly dense sphere the mass at a greater
>distance from the centre (than the point) has no net
>gravitational effect on the point.
>
>Also a counter-example is very easy to construct.  Consider
>two large equal masses separated by a large distance.  Their
>centre of mass (which will be the sum of their masses) is at
>the mid-point of the shortest line joining them.  Another
>mass placed a little way from this mid-point will in fact
>feel little gravitational effect because the masses are a
>long way away.  However, a calculation based on the centre
>of mass would suggest there is a very strong force acting!

This is because the third object is within the sphere containing the
first two. If I correctly remember, that is a consequence of the Gauss
theorem. But if you arrange your objects in spheric clusters centered
in their mass centers, so that the interesting object will be outside
of any of them, then the result will hold. Whether that will be better
than O(n**2)  is another question.

>No help to the OP - they might be better off posting in an
>astronomical group as this is more likely to be where people
>with knowledge of any special algorithms might hang out.

--
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

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

[jtg]

Dmitry A. Kazakov wrote:
> On Fri, 12 Mar 2004 12:55:19 +0000, Stuart Palin <stuart.palin@0.0>
> wrote:
> 
> 
>>Jean-Pierre Rosen wrote:
>>
>>>"Jano" <402450@cepsz.unizar.es> a �crit dans le message de 
>>
>>news:5d6fdb61.0403120115.7c102e3c@posting.google.com...
>>
>>>>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).
>>>>
>>>
>>>If I remember my Newton laws correctly, you just need to compute the force
>>>between an object and the center of mass of all other objects.
>>
>>No!  It is quite a straight-forward proof to show that for a
>>point inside a uniformly dense sphere the mass at a greater
>>distance from the centre (than the point) has no net
>>gravitational effect on the point.
>>
>>Also a counter-example is very easy to construct.  Consider
>>two large equal masses separated by a large distance.  Their
>>centre of mass (which will be the sum of their masses) is at
>>the mid-point of the shortest line joining them.  Another
>>mass placed a little way from this mid-point will in fact
>>feel little gravitational effect because the masses are a
>>long way away.  However, a calculation based on the centre
>>of mass would suggest there is a very strong force acting!
> 
> 
> This is because the third object is within the sphere containing the
> first two. If I correctly remember, that is a consequence of the Gauss
> theorem. But if you arrange your objects in spheric clusters centered
> in their mass centers, so that the interesting object will be outside
> of any of them, then the result will hold. Whether that will be better
> than O(n**2)  is another question.

No! According to Newton laws the object can for instance orbit one of
the masses, but if you assume you can model the masses with one
mass between them, the object could instead only orbit the center
(which is actually empty) and could not orbit any of the masses!

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

[Björn Persson]

Jean-Pierre Rosen wrote:

> If I remember my Newton laws correctly, you just need to compute the force between an object and the center of mass of all other
> objects.

If that were true, the moon would orbit the sun and not the Earth (if we 
ignore the rest of the universe).

-- 
Björn Persson

jor ers @sv ge.
b n_p son eri nu

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

[James Rogers]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 280 bytes --]

Bj�rn Persson <spam-away@nowhere.nil> wrote in 
news:1Yi4c.85891$dP1.243229@newsc.telia.net:

> If that were true, the moon would orbit the sun and not the Earth (if we 
> ignore the rest of the universe).

The moon does orbit the Sun. It also orbits the Earth.

Jim Rogers 

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

[Robert I. Eachus]

Bj�rn Persson wrote:

> If that were true, the moon would orbit the sun and not the Earth (if we 
> ignore the rest of the universe).

Actually it does.  If you compute the gravitational force of the Earth 
on the Moon, and compare it to the gravitational force of the Sun, the 
Sun has a much greater effect.  In fact, the orbit of the Moon around 
the Sun is everywhere convex.

However, back to the OP's question.  The first thing you want to do is 
not use brute force, but use Runga-Kutta for each pair of objects.  This 
makes the calculation about ten times as complex, but gives a much 
better fit.  Second when two objects are "close" you should do the 
Runga-Kutta interpolation much more often.  This usually means 
calculating the effects of all gravitational attractions on the objects 
that are in close proximity more often as well.  (You don't have to do 
the reverse, because the effect of the two nearby objects on remote 
objects will be that of their center of mass.)  Of course you also have 
to allow for the possibility that there are several objects that are 
gravitationally close.  The normal way to do this is to, at the end of 
every major cycle look at the positions of all the objects, and decide 
which ones get the intermediate steps.  It is not worth the effort to 
work with two pairs instead of four 'close' objects.


-- 
                                           Robert I. Eachus

"The only thing necessary for the triumph of evil is for good men to do 
nothing." --Edmund Burke

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

[Björn Persson]

Robert I. Eachus wrote:

> Björn Persson wrote:
> 
>> If that were true, the moon would orbit the sun and not the Earth (if 
>> we ignore the rest of the universe).
> 
> 
> Actually it does.  If you compute the gravitational force of the Earth 
> on the Moon, and compare it to the gravitational force of the Sun, the 
> Sun has a much greater effect.  In fact, the orbit of the Moon around 
> the Sun is everywhere convex.

I didn't mean to say that the Sun doesn't affect the Moon. "If what J-P 
wrote were true, the Moon would not orbit both the Sun and the Earth, as 
it does, but only orbit the solar system's center of gravity (if we 
ignore the rest of the universe)." Is that better?

You can't choose your words too carefully when there are Ada language 
lawyers in the audience. :-)

-- 
Björn Persson

jor ers @sv ge.
b n_p son eri nu

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

[Robert I. Eachus]

Bj�rn Persson wrote:

> I didn't mean to say that the Sun doesn't affect the Moon. "If what J-P 
> wrote were true, the Moon would not orbit both the Sun and the Earth, as 
> it does, but only orbit the solar system's center of gravity (if we 
> ignore the rest of the universe)." Is that better?
> 
> You can't choose your words too carefully when there are Ada language 
> lawyers in the audience. :-)

I think you missed my point.  Earth's moon is unique in the solar 
system.  It is the only moon whose path around the Sun doesn't cross 
itself.  In fact, the effect of the Earth's gravity is so slight that if 
you are calculating the Moon's orbit, it is better to compute it the 
same way as other planets.  (Treat it as orbiting the sun, with 
perturbations by the gravity from other planets.  For all other moons, 
you are better off calculating them as orbiting some planet, with the 
Sun's gravitational effect as a perturbation.)

In a discussion of how to calculate the positions in a complex 
gravitational environment, that is a point worth knowing.


-- 
                                           Robert I. Eachus

"The only thing necessary for the triumph of evil is for good men to do 
nothing." --Edmund Burke

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

[Jano]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1204 bytes --]

Robert I. Eachus dice...
> Bj�rn Persson wrote:
> 
> > I didn't mean to say that the Sun doesn't affect the Moon. "If what J-P 
> > wrote were true, the Moon would not orbit both the Sun and the Earth, as 
> > it does, but only orbit the solar system's center of gravity (if we 
> > ignore the rest of the universe)." Is that better?
> > 
> > You can't choose your words too carefully when there are Ada language 
> > lawyers in the audience. :-)
> 
> I think you missed my point.  Earth's moon is unique in the solar 
> system.  It is the only moon whose path around the Sun doesn't cross 
> itself.  In fact, the effect of the Earth's gravity is so slight that if 
> you are calculating the Moon's orbit, it is better to compute it the 
> same way as other planets.  (Treat it as orbiting the sun, with 
> perturbations by the gravity from other planets.  For all other moons, 
> you are better off calculating them as orbiting some planet, with the 
> Sun's gravitational effect as a perturbation.)

I had never stopped to think about it, but if I understand you 
correctly, that means that the Moon's orbit has a zig-zag path. Nice :)

I'll look further into your Runge-Kutta suggestion, thanks.

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

[Robert I. Eachus]

Jano wrote:

> I had never stopped to think about it, but if I understand you 
> correctly, that means that the Moon's orbit has a zig-zag path. Nice :)

Not even that.  No zigs, no zags.  If you draw a set of lines 
perpendicular to the Moon's path around the Sun (from a heliocentric 
view), at any point in its orbit, the points where the lines cross will 
be inside the Sun or very near.  It is only from a geocentric point of 
view that the Moon and Earth seem to orbit a common point.  (And that 
point is actually about one Earth radius from the Earth...)

> I'll look further into your Runge-Kutta suggestion, thanks.

I wish I could recommend a good book on how to implement Runge-Kutta, 
but your choice is probably a book about how the algorithm works, or one 
about how to use some math library that implements it.  It isn't that 
hard to implement, but be sure to use double precision unless you are 
really careful.

-- 
                                           Robert I. Eachus

"The only thing necessary for the triumph of evil is for good men to do 
nothing." --Edmund Burke

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

[Jano]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 828 bytes --]

Jean-Pierre Rosen dice...
> 
> "Jano" <402450@cepsz.unizar.es> a �crit dans le message de news:5d6fdb61.0403120115.7c102e3c@posting.google.com...
> > 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).
> >
> If I remember my Newton laws correctly, you just need to compute the force between an object and the center of mass of all other
> objects.

I discussed this too with a colleague, but it's equivalent (apart from 
the subtleties noted by other posters) in computing time.

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

[Wes Groleau]

Jano wrote:
> 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 would think that one could locate software already
being used to compute/predict trajectories of real astronomical
bodies (or unmanned spacecraft that fly near them) and if
you want Ada (who wouldn't?) just translate.

-- 
Wes Groleau
Alive and Well
http://freepages.religions.rootsweb.com/~wgroleau/

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

[jtg]

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. :-)