[ODE] LCP solution methods

[David Black]

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