Projected Conjugate Gradient methods for solving LCP's

[KenB]

Hi,
We're digging deep into CG-methods for solving LCP's, e.g. contact problems. Anyone know of any recent references about this? If I remember correctly, someone implemented projected CG in ODE. Who did this, what was the result and has any of you tried it? (sorry for asking about ODE here, but my experience is that the R&D competence and general experience is quite high here).

[Erwin Coumans]

Bart Barenburg used a system to dynamically switch solvers in his Dynamo library, and one of them was conjugent gradient (and singular value decomposition when he couldn't find a solution). Later, David Wu discussed his use of conjugent gradient LCP for rigid body dynamics. James O'Brien uses conjugent gradient as LCP solver in his recent work for contact constraints. Some of them used some pre-conditioner. I don't have links handy right now, perhaps google on their names?

It would be interesting to try out conjugent gradient for LCP indeed, it seems to converge better than PGS in some conditions.
Thanks,
Erwin

[FD]

Erwin,

It would be great if you gave a few links. Googling doesn't give anything. I wonder if there's a CG modification really capable of solving LCPs

[raigan2]

David Wu's simulator used CG (among other methods), sadly Pseudointeractive is gone, I think he's working for Microsoft now. I don't have any contact info

Maybe he's a lurker here? He would certainly have some useful insights as AFAIK his solver was used in several shipped games and evolved over several years. Here are some old presentations: http://pseudointeractive.com/technology-research.php

[dneckels]

I have been using matrix free CG for substeps in the PGS-SM method (stop and solve for the active set every now and then).
This is different, but maybe of interest?
Things I have noticed:
1) The systems tend to be singular (I am using a bullet-like 4 contact points per proximity, maximize area) or horribly conditioned (edit: I just realized that having a large sphere rolling around in my sim is not helping with duplicate constraints, even maximizing area).
2) Since CG will work for singular systems if the right hand side is orthogonal to the nullspace, solving AAx=Ab gives a better ratio of success to fail for the iteration improving things (somewhat more expensive, though). Basically, just the normal equations, since I couldn't think of how to derive the nullspace of A simply.

I'm still in the battle with the algorithm, will write something up if it turns out to be a keeper.
Would be interested in knowing how Projected CG would work...

[Erwin Coumans]

See page 51 of Bart Barenbrug PhD thesis "Designing a class library for Rigid Body Dynamics"
http://users.bart.nl/users/starcat/dynamo

This paper mentions the use of conjugate gradient to solve a contact LCP: http://www.eecs.berkeley.edu/b-cam/Pape ... -2009-ISN/
Solving the LCP using CG should apply for rigid bodies as well.

As the previous poster pointed out, David Wu mention the use of Conjugate Gradient solving within the context of rigid body dynamics in his "The Physics That Brought Cel Damage To Life: A Case Study"
http://pseudointeractive.com/technology-research.php

I emailed David Wu and James O'Brien to see if they have any comments on this.

Thanks,
Erwin