Guermouche, L’Excellent, and Utard discuss the solution of sparse linear algebraic systems using a multifrontal (direct) solver. Such methods are known for their large memory requirements relative to iterative methods, but they are robust and efficient. This paper discusses various ordering techniques and compares their memory requirements. The following methods are compared: approximate minimum degree (AMD); multiple minimum degree (MMD), the approximate minimum fill, as implemented in a multifrontal massively parallel sparse direct solver (MUMPS); PORD, a hybrid bottom-up and top-down sparse reordering; METIS, a hybrid multilevel nested dissection and multiple minimum degree; and SCOTCH, a modified version of the algorithm.

The pure nested dissection was not competitive with these and was abandoned. It was shown that reordering impacts the width and depth of the tree. METIS and SCOTCH generate wide well-balanced trees. The others generate deep trees, with AMD having a better-balanced one. PORD and AMF use the smallest stack size.

The authors developed an algorithm for optimal tree reordering to minimize stack memory requirements. This algorithm improves the requirements of METIS and SCOTCH. Of course, for AMD, one cannot expect any gain since the tree is already deep and balanced. Numerical experiments show that deep, unbalanced trees (AMF and PORD) require less memory than wide, well-balanced ones (METIS and SCOTCH).

The solution on massively parallel machines, using three variants of MUMPS, was also discussed. The authors conclude, based on the numerical experiments, that the current scheduling strategy in MUMPS can be improved upon.