Optimal Numbering for the Schur Complement Boundary Matrix

To solve the global matrix system the boundary system is solved first . This is done by using the Schur complement. A direct solve on this system involves processing a large data structure. Here we present a method for applying the Cuthill-McKee algorithm [38] to reduce the bandwidth of the boundary solve matrix.

Although the boundary system matrix is large it is sparse. By reordering the global numbering of the unknowns we take advantage of the sparcity and pack the data into a band along the diagonal of the matrix. We define the bandwidth of the matrix as the width of this band. The bandwidth is equivalent to the largest elemental bandwidth taken of all the elements.The elemental bandwidth is defined as the largest difference between the global identity of the unknowns in a single element.

All the unknowns in a single edge (or face) are grouped together and numbered consecutively because they will inevitably be closely associated in an optimal renumbering. We define an approximate bandwidth as the maximum difference between the global numbering of any two facets in an element. Minimizing the approximate elemental bandwidth over all the elements is almost equivalent to the original minimization problem.

We start this re-ordering at a facet on the boundary of the region and consider all the elements in which it lies. We order all the facets in these elements in ascending order of their degree. The degree of a node is defined as the number of facets with which it shares an element. The new facets are collectively defined as a layer. We apply this procedure to all the facets in the layer, in their new order, to form a new layer. We order the facets in the new layer in order of their degree. We apply this ordering repeatedly to create a sequence of layers that span the mesh.

Because any element will contain facets from two layers the resulting bandwidth is equivalent to the maximum number of facets in any single layer. We choose the initial facet so that each of the layers contains the least number of elements possible. Thus, we start the algorithm on the boundary to restrict the directions that the layers can expand. Because we do not know which boundary facet will give us the best result, we start the algorithm from a number of the boundary facets in the order of their degree. This number can be set for speed of the overall algorithm.

The described re-ordering leads to a distinct structure in the final boundary solve matrix. The banded region of the matrix is formed from intersecting ``squares'' that show how the different layers formed by the ``wave-front'' interact.

  

Figure 4.19: Here we show the domain that we solved the Helmholtz equation in the following forcing function, $f = -(3.4 \pi^{2})\sin{(\pi.x)} cos{(\pi y)} \cos{(0.2 \pi.z)}$ and boundary conditions $u = \sin{(\pi.x)} cos{(\pi.y)} \cos{(0.2 \pi.z)}$, with periodic boundary conditions at the spiral ends. We see a dramatic bandwidth reduction because of the aspect ratio of the mesh and the exponential decay in the error with increasing expansion order.

We could have performed an O(N_b!) search where N_b is the number of unknowns but this would be prohibitive in all but the simplest meshes.