Understanding MA27 - A Numerical Example - Keller, C (Unspecified, 2000)
The Harwell Subroutine Library code MA27 is a collection of FORTRAN subroutines for solving sparse sets of symmetric linear equations of the form by Gaussian elimination. In order to achieve a high degree of efficiency, Duff and Reid implement a large number of sophisticated methods including the minimum-degree ordering for reducing fill-in in the factors, the depth-first search algorithm for determining an efficient pivot ordering within a pre-computed elimination tree, and the ideas of frontal elimination for permitting a stable numerical factorisation to be performed based on a symbolically chosen pivot sequence. Understanding the interaction of all these methods within the subroutine library is not an easy task and requires the careful study of the source code. In this article an attempt is made to visualise the interactions between individual subroutines in the library by considering a specific example, and by discussing the more important theories that are implemented. We hope that by 'talking the reader through' a particular example, the beauty of the code can be appreciated and understood more easily. This work was supported by an EPSRC Research Studentship and by a CASE Award with the Rutherford Appleton Laboratory (RAL). We remark that permission has been given by the authors of the MA27 solver to publish this work.