(3M) Calculator User Manual

measure its quality, several parameters can be defined: h
min
, h
max
, and h
avg
denote
the minimum, maximum, and average heights of the tree
1
, r e spec tively, and h
dlt
is the variance, expressed as a percentage of h
avg
. Since small separators result in
small chains in the elimination tree, h
avg
should also indirectly reflect the quality
of separators.
3.2.5 Ordering methods
The core of our ordering algorithm uses graph ordering methods as black boxes,
which allows the orderer to run any type of order ing method. In addition to yie lding
orderings of the s ubgraphs that are passed to them, these methods may compute
column block partitions of the subgraphs, that are recorded in a separate tree
structure. The currently implemented graph ordering methods are listed below.
Halo approximate minimum degree
The halo approximate minimum degree method [47] is an improvement of
the approximate minimum degree [1] algorithm, suited for use on subgraphs
produced by nested dissection methods. Its interest compar e d to classical min-
imum degree algorithms is that boundary vertices are processed using their
real deg ree in the global graph rather than their (much smaller) degree in the
subgraph, resulting in smaller fill-in and operation count. This method also
implements amalgamation techniques that result in efficient block computa-
tions in the factoring and the solving process e s.
Halo approximate minimum fill
The halo approximate minimum fill method is a variant of the halo approxi-
mate minimum degree algorithm, where the criterion to select the next vertex
to permute is not based on its current estimated degr e e but on the minimiza-
tion of the induced fill.
Graph compressi on
The graph compression method [2] merges cliques of vertices into single nodes,
so a s to speed-up the ordering of the compressed graph. It also results in some
improvement of the quality of separators, especially for stiffness matrices.
Gibbs-Poole-Stockmeyer
This method is mainly used on separators to reduce the number and extent
of extra-diagonal blocks.
Simple method
Vertices are or dered consecutively, in the same order as they are stored in the
graph. This is the fastest method to use on separa tors when the shape of
extra-diag onal structures is not a concern.
Nested dissection
Incomplete nested dissection method. Separators are computed recursively on
subgraphs, and spec ific ordering methods are applied to the separators and
to the resulting subgr aphs (see sections 3.2.2 and 3.2.3).
1
We do not consider as leaves the disconnected vertices that are present in some meshes, since
they do not participate in the solving process.
17