abaraba

2008-Oct-18, 10:02 AM

hello everyone,

this is about an algorithm,

time stepping function aka "iterative solver" - it is the one and the same algorithm no mater if you're simulating planets, moons, galaxies.. atoms, molecules, ping-pong balls or maybe even 'strange attractors' and chaos itself..

PLEASE,

can someone confirm or prove this wrong, im happy with either - THANK YOU!

summary:

- the 1st basic problem is that Wikipedia and the rest of the internet claim that there is some ERROR in "Euler method", but there is not. the error exist only with nonuniform rate of change in acceleration - this caused practical implementation of algorithm to perform "integration" even if there was no need for it, which in turn caused further multiple mistakes and errors in implementation

- the 2nd basic problem has to do with limiting of number of steps per main loop iteration, but this is not really important for non real-time applications, tho its one of the factors in producing the error under certain situation coupled with 1st problem

BOTH of these "bugs" are present in every single software package i came across, that include all of the commercial and Open Source physics libraries - Havok, PhysX, Bullet, ODE, Ogre, Newton.. but it also seem to include scientific simulators; "Software for molecular mechanics modeling": AGM, AMBER, Ascalaph, BOSS, CHARMM, GROMACS, LAMMPS, MCCCS, MOE, MOIL, MOLDY, NAB, QMOL, RasMol, TINKER, VMD + NAMD, YASARA, Zodiac... (from Wikipedia)

and who knows where else..

i hope, for example, at NASA they actually dont have this buggy algorithm, eh?

ok, let me now copy/paste the message that i hope explains all the subjects that i would like to discuss here, and of course i can go into more details depending on what turns out to be most interesting to public here...

+++COPY/PASTE:

//=== OVERTURE =======================================

Numerical Integration: RK4, Verlet.. WIKIPEDIA is WRONG!

KEYWORDS:

Constraint Algorithm, Iterative Solver, Interpolation, Extrapolation, Verlet, Runge Kutta, Taylor, Sampling, Multistep; Monte Carlo, SHAKE, RATTLE, SETTLE algorithms

do the search and you may find that:

- Wikipedia and every other info on the Internet regarding these matters is simply FALSE in the context of computer simulation, but no one seem to listen to me and im not allowed to make changes.. as 'unverified source'

So, there you go.. all these studies, books, papers, articles.. WRONG?!

//==================================================

//--- FUGUE..

to whom it may concern...

+++ i believe i found the heart of the whole problem:

"numerical integration",

as i suggested before, is completely misplaced in its practical implementation

--- the cause ---

before applying mathematics to physics, and before implementing the solution in computer simulation application there was a failure to recognize TWO very different types of "simulation", i'll call them 'FIELD FORCES' and 'CLASSIC' simulation

A.) 'FIELD FORCES simulation', i.e. NON-UNIFORM "external" ACCELERATION

- deals with oscillations, gravity fields, planet or atom orbits..

B.) 'CLASSIC simulation', i.e CONSTANT "external" ACCELERATION

- everything that is not in the first category.. majority of simulations that deal with objects under constant gravity (constant altitude)

--- the problem ---

1.) with constant acceleration - basic kinematic equations will actually give EXACT solution, i.e. the next POSITION is exact solution as function of time, previous position and acceleration/velocity

(what was measured as error was actually "bug" in implementation)

ergo,

we do not need any APPROXIMATION... no INTERPOLATION is necessary with constant acceleration - we do not need any fancy mathematics, we already have EXACT solution, and so addition of any other computation will only hinder precision and speed

2.) ..plus, if you have this popular implementation that uses MAX steps, as everyone does, then i hope everyone can see now where all the problems came from

--- the solution ---

huh.. this thing surely turned much deeper than i expected, and im still tumbling down the rabbit hole.. but i know this - there are many problems here and solutions that i already proposed do work.. tho, the general and complete solution has to do with defining the problems of the "FIELD FORCE simulation" and basically just define stuff more clearly - which is what im trying to do, and i would appreciate some help

--- the general and complete solution ---

"FIELD FORCE simulation" - NON-UNIFORM ACCELERATION

- so you doing simulation of planetary or maybe atomic orbits..

then, i think its important to realize this sort of simulation is to CLASSIC simulation what ray tracing is to vector graphics

basically, all of the objects are under COLLISION all the time, they all interacting with each and every other object 'ALL the time', in NON-UNIFORM acceleration topology

now we have two problems:

1.) physics libraries and all the spatial partitioning and speed-ups are of no use, the whole "constant collision" is a huge performance problem in its own and solution is to buy faster computer or build cluster of CPUs

2.) the solution to "constant collision" algorithm has actually to do with "n-body problem", "Kepler problem", maybe even "Coulomb's law" and stuff like that - basically, a problem is to find a position as function of time when given initial positions, masses and velocities

one of the ways to go about it is by ITERATIONS, i.e every time step we calculate new AVERAGE ACCELERATION, then calculate velocities and positions as usual

and so,

we finally arrive to the point where "numerical interpolation" makes sense - its nothing else but one of the ways too approximate that *AVERAGE ACCELERATION*, thats the whole point - to compensate for the rate of change in acceleration and try to estimate it given the elapsed time period (time step)

obviously, with enough small time step and maybe some "simple average" the error caused by this would probably be minimal compared to other numerical instabilities already present in computer hardware... and so, even in this case RK4, Verlet.. might be less than desirable solution

*ONLY* "EXTERNAL" NON-UNIFORM ACCELERATION "needs" some sort of APPROXIMATION, there is no need to interpolate position or velocity

of course,

exact solution is much better than some approximation... (to be concluded)

am i right or wrong?

//------------------------------------------------------------

+++END COPY/PASTE

thank you all

this is about an algorithm,

time stepping function aka "iterative solver" - it is the one and the same algorithm no mater if you're simulating planets, moons, galaxies.. atoms, molecules, ping-pong balls or maybe even 'strange attractors' and chaos itself..

PLEASE,

can someone confirm or prove this wrong, im happy with either - THANK YOU!

summary:

- the 1st basic problem is that Wikipedia and the rest of the internet claim that there is some ERROR in "Euler method", but there is not. the error exist only with nonuniform rate of change in acceleration - this caused practical implementation of algorithm to perform "integration" even if there was no need for it, which in turn caused further multiple mistakes and errors in implementation

- the 2nd basic problem has to do with limiting of number of steps per main loop iteration, but this is not really important for non real-time applications, tho its one of the factors in producing the error under certain situation coupled with 1st problem

BOTH of these "bugs" are present in every single software package i came across, that include all of the commercial and Open Source physics libraries - Havok, PhysX, Bullet, ODE, Ogre, Newton.. but it also seem to include scientific simulators; "Software for molecular mechanics modeling": AGM, AMBER, Ascalaph, BOSS, CHARMM, GROMACS, LAMMPS, MCCCS, MOE, MOIL, MOLDY, NAB, QMOL, RasMol, TINKER, VMD + NAMD, YASARA, Zodiac... (from Wikipedia)

and who knows where else..

i hope, for example, at NASA they actually dont have this buggy algorithm, eh?

ok, let me now copy/paste the message that i hope explains all the subjects that i would like to discuss here, and of course i can go into more details depending on what turns out to be most interesting to public here...

+++COPY/PASTE:

//=== OVERTURE =======================================

Numerical Integration: RK4, Verlet.. WIKIPEDIA is WRONG!

KEYWORDS:

Constraint Algorithm, Iterative Solver, Interpolation, Extrapolation, Verlet, Runge Kutta, Taylor, Sampling, Multistep; Monte Carlo, SHAKE, RATTLE, SETTLE algorithms

do the search and you may find that:

- Wikipedia and every other info on the Internet regarding these matters is simply FALSE in the context of computer simulation, but no one seem to listen to me and im not allowed to make changes.. as 'unverified source'

So, there you go.. all these studies, books, papers, articles.. WRONG?!

//==================================================

//--- FUGUE..

to whom it may concern...

+++ i believe i found the heart of the whole problem:

"numerical integration",

as i suggested before, is completely misplaced in its practical implementation

--- the cause ---

before applying mathematics to physics, and before implementing the solution in computer simulation application there was a failure to recognize TWO very different types of "simulation", i'll call them 'FIELD FORCES' and 'CLASSIC' simulation

A.) 'FIELD FORCES simulation', i.e. NON-UNIFORM "external" ACCELERATION

- deals with oscillations, gravity fields, planet or atom orbits..

B.) 'CLASSIC simulation', i.e CONSTANT "external" ACCELERATION

- everything that is not in the first category.. majority of simulations that deal with objects under constant gravity (constant altitude)

--- the problem ---

1.) with constant acceleration - basic kinematic equations will actually give EXACT solution, i.e. the next POSITION is exact solution as function of time, previous position and acceleration/velocity

(what was measured as error was actually "bug" in implementation)

ergo,

we do not need any APPROXIMATION... no INTERPOLATION is necessary with constant acceleration - we do not need any fancy mathematics, we already have EXACT solution, and so addition of any other computation will only hinder precision and speed

2.) ..plus, if you have this popular implementation that uses MAX steps, as everyone does, then i hope everyone can see now where all the problems came from

--- the solution ---

huh.. this thing surely turned much deeper than i expected, and im still tumbling down the rabbit hole.. but i know this - there are many problems here and solutions that i already proposed do work.. tho, the general and complete solution has to do with defining the problems of the "FIELD FORCE simulation" and basically just define stuff more clearly - which is what im trying to do, and i would appreciate some help

--- the general and complete solution ---

"FIELD FORCE simulation" - NON-UNIFORM ACCELERATION

- so you doing simulation of planetary or maybe atomic orbits..

then, i think its important to realize this sort of simulation is to CLASSIC simulation what ray tracing is to vector graphics

basically, all of the objects are under COLLISION all the time, they all interacting with each and every other object 'ALL the time', in NON-UNIFORM acceleration topology

now we have two problems:

1.) physics libraries and all the spatial partitioning and speed-ups are of no use, the whole "constant collision" is a huge performance problem in its own and solution is to buy faster computer or build cluster of CPUs

2.) the solution to "constant collision" algorithm has actually to do with "n-body problem", "Kepler problem", maybe even "Coulomb's law" and stuff like that - basically, a problem is to find a position as function of time when given initial positions, masses and velocities

one of the ways to go about it is by ITERATIONS, i.e every time step we calculate new AVERAGE ACCELERATION, then calculate velocities and positions as usual

and so,

we finally arrive to the point where "numerical interpolation" makes sense - its nothing else but one of the ways too approximate that *AVERAGE ACCELERATION*, thats the whole point - to compensate for the rate of change in acceleration and try to estimate it given the elapsed time period (time step)

obviously, with enough small time step and maybe some "simple average" the error caused by this would probably be minimal compared to other numerical instabilities already present in computer hardware... and so, even in this case RK4, Verlet.. might be less than desirable solution

*ONLY* "EXTERNAL" NON-UNIFORM ACCELERATION "needs" some sort of APPROXIMATION, there is no need to interpolate position or velocity

of course,

exact solution is much better than some approximation... (to be concluded)

am i right or wrong?

//------------------------------------------------------------

+++END COPY/PASTE

thank you all