[ODE] Constraint theorizing

[Sergio Valverde]

No, ODE is O(C ^3) (in space and in time) where C is proportional to 
the number of constraints. That is, the performance is getting worse
(in an exponential manner) as the number of constraints is increased.
This is why ODE in its present form can't handle physical 
configurations with medium to large number of constraints.

Sergi

-----Original Message-----
From: Henri Hakl [mailto:henri@cs.sun.ac.za]
Sent: martes, 25 de febrero de 2003 13:10
To: ode@q12.org
Subject: Re: [ODE] Constraint theorizing


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

_______________________________________________
ODE mailing list
ODE@q12.org
http://q12.org/mailman/listinfo/ode