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
, respectively, 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 ordering method. In addition to yielding
orderings of the subgraphs 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 compared to classical min-
imum degree algorithms is that boundary vertices are processed using their
real degree 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 processes.
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 degree but on the minimiza-
tion of the induced fill.
Graph compression
The graph compression method [2] merges cliques of vertices into single nodes,
so as 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 ordered consecutively, in the same order as they are stored in the
graph. This is the fastest method to use on separators when the shape of
extra-diagonal structures is not a concern.
Nested dissection
Incomplete nested dissection method. Separators are computed recursively on
subgraphs, and specific ordering methods are applied to the separators and
to the resulting subgraphs (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
