@TechReport{ AmLiPr2005.6,

author = {Amestoy, Patrick and Li, Xiaoye Sherry and Pralet, Stéphane},

title = "{Unsymmetric Ordering Using A Constrained Markowitz Scheme}",

year = {2005},

month = {janvier},

type = {Rapport de recherche},

number = {RT/APO/04/05},

institution = {IRIT},

address = {Université Paul Sabatier, Toulouse},

language = {français},

keywords = {sparse unsymmetric matrices, greedy heuristics, ordering methods, bipartite quotient graph},

note = {Part of this research was supported by a grant NSF-INRIA numberNSF-INT-0003274.},

abstract = {We consider the LU factorization of unsymmetric sparse matrices
using a three-phase approach (analysis, factorization and
triangular solution).
Usually the analysis phase first determines a set of potentially good
pivot and then orders this set of pivots to decrease the
fill-in in the factors.
In this paper, we present a preprocessing algorithm
that simultaneously achieves the objectives of selecting numerically
good pivots and preserving the sparsity.
We describe the algorithmic properties and difficulties in implementation.
By mixing the two objectives we show that we can reduce the amount of
fill in the factors and reduce the number of numerical problems
during factorization.
On a set of large unsymmetric real problems, we
obtain the average gains of 14% in the factorization time, of
12% in the size of the LU factors, and of
21% in the number of operations performed in the factorization phase.
}

}