Wiki

Minimum Degree Ordering Algorithm

The pattern of another category of high-quality ordering algorithms in wide use is based on a greedy approach such that the ordering is chosen to minimize some quantity at each step of a simulated -step symmetric Gaussian elimination process. The algorithms using such an approach are typically distinguished by their greedy minimization criteria [34].

In graph terms, the basic ordering process used by most greedy algorithms is as follows:

  1. Start: Construct undirected graph G0 corresponding to matrix A
  2. Iterate: For k = 1, 2, ... until Gk = { } do:
    • Choose a vertex vk from Gk according to some criterion
    • Eliminate vk from Gk to form Gk+1
The resulting ordering is the sequence of vertices {v0, v1,...} selected by the algorithm.

One of the most important examples of such an algorithm is the Minimum Degree algorithm. At each step the minimum degree algorithm chooses the vertex with minimum degree in the corresponding graph as vk. A number of enhancements to the basic minimum degree algorithm have been developed, such as the use of a quotient graph representation, mass elimination, incomplete degree update, multiple elimination, and external degree. See [35] for a historical survey of the minimum degree algorithm.

The BGL implementation of the Minimum Degree algorithm closely follows the algorithmic descriptions of the one in  [21]. The implementation presently includes the enhancements for mass elimination, incomplete degree update, multiple elimination, and external degree.

In particular, we create a graph representation to improve the performance of the algorithm. It is based on a templated ``vector of vectors.'' The vector container used is an adaptor class built on top the STL std::vector class. Particular characteristics of this adaptor class include the following:

  • Erasing elements does not shrink the associated memory. Adding new elements after erasing will not need to allocate additional memory.
  • Additional memory is allocated efficiently on demand when new elements are added (doubling the capacity every time it is increased). This property comes from STL vector.

Note that this representation is similar to that used in Liu's implementation, with some important differences due to dynamic memory allocation. With the dynamic memory allocation we do not need to over-write portions of the graph that have been eliminated, allowing for a more efficient graph traversal. More importantly, information about the elimination graph is preserved allowing for trivial symbolic factorization. Since symbolic factorization can be an expensive part of the entire solution process, improving its performance can result in significant computational savings.

The overhead of dynamic memory allocation could conceivably compromise performance in some cases. However, in practice, memory allocation overhead does not contribute significantly to run-time for our implementation as shown in  [] because it is not done very often and the cost gets amortized.

Proper Self-Avoiding Walk

The finite element method (FEM) is a flexible and attractive numerical approach for solving partial differential equations since it is straightforward to handle geometrically complicated domains. However, unstructured meshes generated by FEM does not provide an obvious labeling (numbering) of the unknowns while it is vital to have it for matrix-vector notation of the underlying algebraic equations. Special numbering techniques have been developed to optimize memory usage and locality of such algorithms. One novel technique is the self-avoiding walk [].

If we think a mesh is a graph, a self-avoiding walk(SAW) over an arbitrary unstructured two-dimensional mesh is an enumeration of all the triangles of the mesh such that two successive triangles shares an edge or a vertex. A proper SAW is a SAW where jumping twice over the same vertex is forbidden for three consecutive triangles in the walk. it can be used to improve parallel efficiency of several irregular algorithms, in particular issues related to reducing runtime memory access (improving locality) and interprocess communications. The reference [] has proved the existence of A PSAW for any arbitrary triangular mesh by extending an existing PSAW over a small piece of mesh to a larger part. The proof effectively provides a set of rules to construct a PSAW.

The algorithm family of constructing a PSAW on a mesh is to start from any random triangle of the mesh, choose new triangles sharing an edge with the current sub-mesh and extend the existing partial PSAW over the new triangles.

Let us define a dual graph of a mesh. Let a triangle in the mesh be a vertex and two triangles sharing an edge in the mesh means there is an edge between two vertices in the dual graph. By using a dual graph of a mesh, one way to implement the algorithm family of constructing a PSAW is to reuse BGL algorithms such as BFS and DFS with a customized visitor to provide operations during traversal. The customized visitor has the function tree_edge() which is to extend partial PSAW in case by case and function start_vertex() which is to set up the PSAW for the starting vertex.


Copyright © 2000-2001 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)