[ODE] LCP solution methods

[Frederic Marmond]

sorry, it is not an answer to your main question, but to your 'PS':
to answer the list+sender, just do a 'reply-all'

Fred
Le mercredi 05 Janvier 2005 21:21, Sergei Migdalskiy a écrit :
> 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 Get it now!

-- 
Frederic Marmond