STFC Website

part of UK Research & Innovation

Version 2.1.0

31st October 2007

MC47: Sparse symmetric pattern: approximate minimum-degree ordering allowing dense rows

Given the sparsity pattern of a symmetric matrix \(\mathbf{A}\), MC47 uses an approximate minimum degree algorithm to compute a pivot order that is efficient when used with a sparse Cholesky solver. MC47 optionally allows for the efficient handling of dense or almost dense rows of \(\mathbf{A}\). At each step, the pivot selected is the one that minimizes an upper-bound on the (external) degree. A permutation corresponding to this ordering is returned, together with information that may assist in the subsequent numerical factorization of the matrix.

The code is typically faster than other minimum degree algorithms and produces comparable results to other minimum external degree algorithms in terms of fill-in and the number of floating-point operations needed to compute the factors.