A new row ordering strategy for frontal solvers

The frontal method is a variant of Gaussian elimination that has been widel y used since the mid 1970s. In the innermost loop of the computation the me thod exploits dense linear algebra kernels, which are straightforward to ve ctorize and parallelize. This makes the method attractive for modern comput er architectures. However, unless the matrix can be ordered so that the fro nt is never very large, frontal methods can require many mole floating-poin t operations for factorization than other approaches. We are interested in matrices that have a highly asymmetric structure. We use the idea of a row graph of an unsymmetric matrix combined with a variant of Sloan's profile r eduction algorithm to reorder the rows. We also look at applying the spectr al method to the row graph. Numerical experiments performed on a range of p ractical problems illustrate that our proposed MSRO and hybrid MSRO row ord ering algorithms yield substantial reductions in the front sizes and, when used with a frontal solver, significantly enhance its performance both in t erms of the factorization time and storage requirements. Copyright (C) 1999 John Wiley & Sons, Ltd.