High order sparse matrix LCP solver?

Andrey Tuganov · Post by **Andrey Tuganov** » Tue Jan 09, 2007 5:11 pm

Hi! I was looking for a large (100-10000 rows) sparse matrix LCP solver in internet some time ago. I found one: PATH. It works but there are some drawbacks: I guess it?s not free; it?s bulky and not open. Hard to understand what?s inside, impossible to make tweaks. So I decide for a simple Gauss-Seidel algorithm. Is there anything what is already made, open and better than that? I tend to favor precision over speed.

Jan Bender · Post by **Jan Bender** » Tue Jan 09, 2007 5:36 pm

Maybe you should take a look at PARDISO:

http://www.computational.unibas.ch/cs/s ... e/pardiso/

I use the commercial version of it which is integrated in the Intel MKL and it works well.

Jan

Andrey Tuganov · Post by **Andrey Tuganov** » Tue Jan 09, 2007 6:02 pm

Looks like it solves Linear Equations not LCP. That I need too however, I'll try to compare it with UMFPACK.

ngaloppo · Post by **ngaloppo** » Tue Jan 09, 2007 6:45 pm

I've used PARDISO. Indeed, I don't think it does LCP.

It's fast but I'm not convinced about its speed, especially about the backsubstitution part.

Let me know how it compares to UMFPACK, I'm interested.

Erwin Coumans · Post by **Erwin Coumans** » Wed Jan 10, 2007 4:31 pm

I asked Kenny Erleben, and he mentioned this link:

http://www.cs.wisc.edu/cpnet/

There is a bunch of libraries out there. CPNET got a small collection of links for some of these.

Also one can reformulate complimentarity problems, using smooth or nonsmooth reformulations. This will result in most cases result in typical constrainted optimization problems. If one do this then there is even more libraries out there that one can use... CPNET also got a lot of references to papers explaining these reformulations.

The downside is that most of these libraries are concerned with robustness and accuracy, they are not focused on game/graphics kind of numerics...

Erin Catto · Post by **Erin Catto** » Wed Jan 10, 2007 6:25 pm

Often a physics problem can be expressed as a box constrained quadratic program (equivalent to an LCP). For that I recommend GPCG and variations.

http://citeseer.ist.psu.edu/benson99gpcg.html

Jan Bender · Post by **Jan Bender** » Thu Jan 11, 2007 8:57 am

Looks like it solves Linear Equations not LCP.

Sorry that was my mistake. I didn't read LCP.

Jan

ngbinh · Post by **ngbinh** » Sun Jan 21, 2007 1:28 am

IMHO, Tod Munson's PATH is one of the most stable LCP/NCP solver.
You can try their free version but the matrix size will be limited.