Parallelizable conjugate gradient-based MLCP solver

Post Reply
XperienS
Posts: 34
Joined: Fri Nov 25, 2005 10:09 am

Parallelizable conjugate gradient-based MLCP solver

Post by XperienS »

Here (https://github.com/avoroshilov/physics_ ... _paper.pdf) you can download quick sketch of part of our recent research. We present a method of solving mixed linear complementarity problem with box constraints applied to a typical formulation of modern constraint-based dynamics simulator, which is easy parallelizable (hence will take benefit of modern GPUs) and has O(N) complexity, while showing better convergence than typical PGS solver.
That's early version of the sketch, so if you will find any errors or inaccuracies, please let us know.

Update #1:
https://github.com/avoroshilov/physics_fem_rbd is our public code repository where you can download the source code of demos presented in this thread.

Update #2:
Example in "Applying the preconditioner" fixed.
Last edited by XperienS on Tue Jan 02, 2018 12:39 am, edited 5 times in total.
nisse
Posts: 19
Joined: Sat Sep 05, 2009 12:26 pm

Re: Parallelizable conjugate gradient-based MLCP solver

Post by nisse »

Thanks for sharing. That is really grand of you! I will read it.

First reflection. I don't see any system with complementarity conditions among the test systems. What type of systems that imposes bounds on the multipliers or velocity have you considered? And are the results for that also just as positive as for purely holonomic systems.
XperienS
Posts: 34
Joined: Fri Nov 25, 2005 10:09 am

Re: Parallelizable conjugate gradient-based MLCP solver

Post by XperienS »

Ah, sorry, forgot to describe such test case. Actually in this forum thread, there is demos of the method described, and on the screenshot there is FEM brick, attached to world via chain of ball-socket joints, lying on the floor (contact joints with friction - here is where limits introduced). Actually, method is surprisingly good even with quite tight box constraints (e.g. low friction) - can't really share the numbers now, but if you want, I'll try to do some measurements on the weekend.
Actually, floor which produces contacts with friction is switchable in FEM stress demo too (long stiff brick), and it touches the floor when bending, also not really affecting convergence vitally.
One more thing I wanted to add in terms of test cases. We also tested arbitrary FEM models (up to 4k tetras) - they were main source of ill-conditioned systems, but having double Jacobi preconditioner, solver is converging quite fast there too. Models were falling onto floor with friction too, btw :)
XperienS
Posts: 34
Joined: Fri Nov 25, 2005 10:09 am

Re: Parallelizable conjugate gradient-based MLCP solver

Post by XperienS »

We forgot to attach link to our public code repository, fixing that.. Link is now in the first post of the thread.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Parallelizable conjugate gradient-based MLCP solver

Post by Dirk Gregorius »

I have a quick question. How many iterations would need for say a stack of five boxes?
XperienS
Posts: 34
Joined: Fri Nov 25, 2005 10:09 am

Re: Parallelizable conjugate gradient-based MLCP solver

Post by XperienS »

Dirk, sorry, but we didn't implement complex CD in our test framework, so we can't really say anything about stacks now. Although my assumption is that it would need about 15 iterations anyway because of CG nature.
xiaoQ0903
Posts: 10
Joined: Thu Jan 13, 2011 12:42 pm

Re: Parallelizable conjugate gradient-based MLCP solver

Post by xiaoQ0903 »

XperienS wrote:Here (http://fem.xp3d.net/files/sketch_v102.pdf) you can download quick sketch of part of our recent research. We present a method of solving mixed linear complementarity problem with box constraints applied to a typical formulation of modern constraint-based dynamics simulator, which is easy parallelizable (hence will take benefit of modern GPUs) and has O(N) complexity, while showing better convergence than typical PGS solver.
That's early version of the sketch, so if you will find any errors or inaccuracies, please let us know.

Update #1:
http://code.google.com/p/realtime-deformations-fem/ is our public code repository where you can download the source code of demos presented in this thread. GPU version of the solver is tested on NVIDIA GeForce GTX260.

Update #2:
Example in "Applying the preconditioner" fixed.
Hi XperienS!I am very interested in your work!but I cannot download the paper with link you provided([http://fem.xp3d.net/files/sketch_v102.pdf)! Also with the same problem in another thread(http://bulletphysics.org/Bullet/phpBB3/ ... f=6&t=5468) :(
Could you fix the link ,Thank you very much!
Post Reply