Abstract
Ordering algorithms aim to pre-order a matrix
in order to achieve a favourable structure for factorization.
Two prototype structures are described
which are commonly aimed at by current algorithms.
A different structure based on a lower Hessenberg form is introduced. We show
that the common structures may be obtained from the Hessenberg form in
a simple way. A fundamental and very simple algorithm is presented for
deriving the lower Hessenberg form. This algorithm is inherently a part of
other common algorithms, but is usually obscured by other detailed heuristics.
Some of these heuristics are seen to correspond to different tie-break rules
in the fundamental algorithm. We describe a particularly simple tie-break rule
used in SPK1 by Stadtherr and Wood (Computers Chem. Engng. 8, 9-18,
1984), which is effective and not at all well known.
Ordering algorithms need to be modified to enable pivoting for numerical
stability to be carried out. We describe how the idea of threshold pivoting can be
used in the context of these algorithms.
Most ordering algorithms in common use employ some sort of look-ahead to
promote a favourable structure.
It is argued that look-ahead is generally ineffective in practice,
and that numerical evidence supports the use of very simple strategies.
A new ordering algorithm is presented which aims to obtain a narrower
bandwidth in the lower Hessenberg form.
Some limited numerical experience is presented which enables
us to draw tentative conclusions about various ordering strategies, and how they
compare with those in common use.
Key words: Sparse linear systems, direct solution, matrix ordering.