Unsymmetric Ordering Using A Constrained Markowitz Scheme

We present a family of ordering algorithms that can be used as a preprocessing step prior to performing sparse ${\bf L}{\bf U}$ factorization. The ordering algorithms simultaneously achieve the objectives of selecting numerically good pivots and preserving the sparsity. We describe the algorithmic properties and challenges in their implementation. By mixing the two objectives we show that we can reduce the amount of fill‐in in the factors and reduce the number of numerical problems during factorization. On a set of large unsymmetric real problems, we obtained the median reductions of $12\%$ in the factorization time, of $13\%$ in the size of the ${\bf L}{\bf U}$ factors, of $20\%$ in the number of operations performed during the factorization phase, and of $11\%$ in the memory needed by the multifrontal solver MA41_UNS. A byproduct of this ordering strategy is an incomplete ${\bf L}{\bf U}$‐factored matrix that can be used as a preconditioner in an iterative solver.