[ODE] Constraint theorizing

Henri Hakl henri at cs.sun.ac.za
Tue Feb 25 05:19:02 2003


Isn't ODE supposed to be O(N) as is anyway?


----- Original Message -----
From: "Gary R. Van Sickle" <g.r.vansickle@worldnet.att.net>
To: <ode@q12.org>
Sent: Tuesday, February 25, 2003 8:29 AM
Subject: RE: [ODE] Constraint theorizing


> > There were some discussion about such things in this list
> > (iterative schemes and the like) I have tested (succesfully)
> > a straighforward iterative  technique which solves *only*
> > 1 constraint at each step (thanks Antonio). That is, if you
> > have a system  of say C= 10 constraints, then you solve
> > every constraint separately without taking into account
> > the other constraints. The idea is that the time step is
> > subdivided into a sort of "microsimulations". Something
> > like that:
> >
> > parameter: N substeps, C constraints, Dt (ODE timestep)
> >
> > for i=0..N-1 do
> > for c = 0..C-1 do
> > Solve constraint c-th
> > Apply forces to constraint bodies
> > next
> > Integrate bodies by (Dt/N)
> > next
> >
> > The idea is that as N->inf the movement of the bodies is
> > very small so the effect of every constraint is very
> > localized and this approach becomes exact just in the limit.
> > In my tests a small number is iterations is enough to
> > get decent results.
> >
> > Please note that the core of this scheme is to solve a
> > very small (up to 6x6) LCP constraint system.  I think
> > this approach gives enough room to a lot of performance
> > improvements. The next step should be to find a fast
> > code able to solve the small system.  Also, note that
> > is no longer necessary to store a big matrix for the
> > constraint coefficients.
>
> This is like excellent to the third power!  And believe it or not, I
actually
> thought of just this scheme during my run this evening, not that I'd have
had
> the ability to pull it off.  So let me see if I can summarize.  ODE as-is
is
> O(C^3).  The new scheme is O(CN), with N a small integer.  That
improvement in
> scalability alone is fabulous.  PLUS, we lose the stack problems that have
been
> plagueing people.
>
> You are a GOD!
>
> --
> Gary R. Van Sickle
> Brewer.  Patriot.
>
>
> _______________________________________________
> ODE mailing list
> ODE@q12.org
> http://q12.org/mailman/listinfo/ode