[Coin-discuss] Experiences with paralleling simplex

[Matthew Saltzman]

On Fri, 5 Jan 2007, Sathi wrote:

>
>> Some kind
>> of sparse LU factorization is typical.
>
> In case of Cholesky factorization one could use column ordering heuristics
> like minimum-degree to get a better factorization. Does the LU
> factorization depend upon the column ordering like Cholesky factorization?

In unsymmetric LU factorization, the sparsity pattern and column selection 
order can (and usually does) change based on the magnitudes of the 
coefficients involved at each pivot.  A fixed ordering cannot be computed 
in advance.  See, e.g, Markowitz ordering.  Also, updating a sparse 
factorization at each pivot is much faster in general than recomputing it. 
In interior-point algorithms, pivot order is stable from iteration to 
iteration, but there is no exploitable relationship between the 
coefficents of consecutive iterations, so factorizations must be 
recomputed from scratch.

>
> Thanks,
> Sathi
>
>
>
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>

-- 
 		Matthew Saltzman

Clemson University Math Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs