[ODE] LCP solution methods
David Black
dblack at fastmail.fm
Wed Jan 5 21:21:31 MST 2005
Hi,
Look at the human hand paper at:
http://ode.org/cgi-bin/wiki.pl?OdeInternalsDocumentation and the ODE
user manual for what they mean by CFM(and ERP)....
David
Sergei Migdalskiy wrote:
> Reverse engineering isn't my strong side.. I tried to look through the
> code though and..
>
> Can someone explain, does SOR_LCP use the J_invM_JT matrix directly or
> does it precondition it to make the method converge faster?
>
> Also, can someone advice me how CFM is used, from the math standpoint?
> is it just the transformed right-hand-side of the LCP or some
> regularization vector, or something else?
>
> Anyway, quick step is supposed to be the newest version. It uses
> SOR_LCP (right?), which is essentially the projected Gauss-Seidel with
> overrelaxation parameter(is that correct?), which is what I'm also
> using. It's probably the simplest method ever to use for LCP. What's
> the trick to make SOR converge faster? In my experiments, when there
> are levers that make the off-diagonal elements of the LCP exceed the
> corresponding diagonal element magnitudes, SOR converges very slow,
> and the quality of the solution is not satisfactory. And the
> relaxation parameter may not be >= 2.
>
> As far as stepfast is looked at (please feel free to correct me
> anyone), stepfast uses Dantzig LCP solver that maintains the dense (?)
> LDL' factor of A[C,C] submatrix. I'm not sure about scalability : what
> if there are 5000 contacts and C is almost full? will it construct a
> 5000x5000 LDL' factor and maintain it? And how many steps does it
> perform to find the solution? Please let me know if I'm wrong and it
> doesn't maintain a multi-megabyte table. I see there are optimizations
> to maintain the factor with quick updates, though I'm not nearly good
> enough to understand the meaning of the source code within reasonable
> time.
>
> I'm sorry that I'm not familiar enough with ODE to make some tests and
> have to ask for explanations instead of looking for them in the code.
> But discussions may sparkle some ideas, which is mutually beneficial.
> Besides, I'm essentially interested in a better method than ODE has
> (that is, if there's no tricks I don't know about that ODE uses to
> make SOR converge faster)
>
> Thank you,
> Sergiy
>
> PS. Btw, how does one reply to the list? My "Reply" seems to reply
> only to the author, not to the ODE list..
>
> >From: "Vedran Klanac" <vedrank at croteam.com> >To: "Sergiy Migdalskiy"
> <migdalskiy at hotmail.com> >Subject: Re: [ODE] LCP solution methods
> >Date: Wed, 5 Jan 2005 09:49:31 -0000 > >Hi ! > >Have you tried with
> QuickStep method which exists in ODE ? > >Vedran Klanac >CROTEAM
> >Physics Department >vedrank at croteam.com > > >----- Original Message
> ----- >From: "Sergiy Migdalskiy" <migdalskiy at hotmail.com> >To:
> <ode at q12.org> >Sent: Wednesday, January 05, 2005 8:17 >Subject: [ODE]
> LCP solution methods > > > > Hello: > > > > I'm working on an LCP
> solver, using JM^-1J^T method in Baraff's >terminology > > (the LCP
> w=Mx+q, w,x>=0, wx=0 with matrix M being non singular and >strictly >
> > positive definite). I have some pretty good progress, but I'm still
> far >from > > a high-quality physics package. I wanted to ask for any
> suggestions how to > > implement iterative O(n) expected running time
> solver. >
>
> ------------------------------------------------------------------------
> FREE pop-up blocking with the new MSN Toolbar MSN Toolbar
> <http://g.msn.com/8HMAEN/2755??PS=47575> Get it now!
>
>------------------------------------------------------------------------
>
>_______________________________________________
>ODE mailing list
>ODE at q12.org
>http://q12.org/mailman/listinfo/ode
>
>
More information about the ODE
mailing list