4. Description of document versions#
Version Aster |
Author (s) Organization (s) |
Description of changes |
5 |
|
Initial text |
8.4 |
|
Approximate Minimum Degree Method Reference Document
The « minimum degree » algorithm consists in numbering the nodes of a graph in increasing order of the number of their neighbors. Here is a simplified but essential description.
we form the initial graph associated with the sparse matrix to be factored,
we calculate the number of neighbors of the nodes (their degree),
we number first (then eliminate from the graph), the node having the fewest neighbors (minimum degree),
we update the graph from step 1,
we go back to step 2.
Calculating the degree of nodes is a costly operation in terms of calculation time. The « Approximate Minimum Degree » method [bib3] aims to reduce this cost. For this, instead of calculating the real degree of a node, we are satisfied with an increase (often equal, according to the authors, to the true degree), which is easier to calculate. In fact, during the elimination the true degree of node \(i\) is equal to \({d}_{i}\), cardinal of the following set: \({A}_{i}\cup \text{{}{L}_{e}\text{}}\), where the union is made on the set of neighbors \(e\) , previously eliminated, of \(i\) (filling terms), and where \({A}_{i}\) is the set of initial neighbors. In the approximate method \(i\) is replaced by \({d}_{i}=\text{card}({A}_{i})+\sum \text{card}\text{{}{L}_{e}\text{}}\), i.e. the intersection of \({L}_{e}\) is overlooked.
This method is described in [bib3] and the various variants of the « minimum degree » algorithm are explained in [bib4].
Reference document METIS
The implementation of the renumbering module for sparse matrices METIS is described in the note [bib5], provided in the software’s METIS -4.0/Doc directory. The algorithm used is described in [bib6]
It is also possible to consult the following internet address: http://www.cs.umn.edu/~karypis
METIS is mainly a tool for splitting graphs (meshes), with the following 2 goals:
split a given graph into \(p\) sub-graphs with the closest possible sizes,
minimize the size of the boundaries between subgraphs.
The first goal aims at a good balance of parallelization on \(p\) processors and the second aims to minimize communications.
METIS uses a graph partition algorithm at several levels, proceeding as follows: at each level we look for separators (set of sides), of minimum sizes that cut the graph into equal parts. METIS applies this principle to the renumbering of the nodes of a graph by looking for a separator at each step that divides the graph into 2 sub-graphs. The nodes in the first subgraph are numbered first, then those in the second, then those in the separator. The same algorithm is then applied to the 2 subgraphs recursively.