[Clp] Sparse matrices

[Miles Lubin]

Dear Daniel,

Clp uses essentially the Suhl-Suhl approach for forming the sparse LU
decomposition and the Forrest-Tomlin approach for updating the factors
after each simplex iteration. This code is all in the
CoinFactorization class in CoinUtils. If you take a look at that code,
you may lose your desire to try to parallelize it ;). Forming a sparse
LU factorization on a GPU will likely be very difficult, but if you do
manage to do that, for updates I would suggest using as a starting
point the so-called product-form update that you can find in any
textbook; with these, you can treat the LU factorization as a black
box.

Are you aware of the work of Iain Dunning (https://github.com/IainNZ/LPG)?

Regards,
Miles

On Mon, Mar 5, 2012 at 9:49 AM, Daniel Herrero <dani_herrero at yahoo.es> wrote:
> Hello everybody:
>
> I'm researh at Politechnic University of Madrid. I've been working on
> solving LP problems with Nvidia GPU's using parallel methods.
>
> I'm starting now with sparse matrices, and I have read Suhl & Shul papers
> form 1990 and 1993. The results are much more time consuming than what I
> hope, for example a problem with 3500 constraints, 9625 continous variables
> and 90% sparsity, as is described in those papers, I spend 250 seconds using
> the usual Simplex method, and about 2500 seconds using the LU decomposition
> because the matrix multiplication is much more time consuming than row
> updates.
>
> I'm not trying to parallelize the problem yet, just trying to understand the
> methodology of LU decomposition. Could you tell me what are you using for
> doing this?, I've read that you use Cholesky, but I'm a little lost and
> maybe not taking into account something important.
>
> Thank you so much
>
> Daniel Herrero Giner
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/clp
>