Coloring Algorithm

A ``greedy algorithm'' was used to perform coloring: first all nodes are assigned the ``color'' (or label) zero. This means that it has no color. Then, for each and every node, a check is made to see what nodes are its neighbors, and for those neighboring nodes, a check is made to see what are their colors/labels. The node in question is assigned the smallest color (label) number which is ``not taken''. If that is not available, it is assigned the next lowest label/number after all the labels are checked. To find the neighbors of a node, a linked list is created where for every node in the connectivity (t vector), all the nodes in that element are placed in the linked list (while checking for duplicates). The entire procedure is described below:

1.

Create a linked list listarr. This list contains the neighbors of each node.

2.

For every node in the vector t, put all the nodes of that element into listarr.

3.

Label all these nodes with label zero. For every node, check the label of its neighbors. Assign the smallest label that the neighboring nodes do not have.

4.

Collect all nodes of each color, and number them sequentially. This is the new node numbering scheme.

5.

Change the mesh connectivity (vector t) and also the coordinates of the nodes (vector p) to reflect the new numbering scheme.

6.

Feed the vectors p and t into the FEM code to get the re-ordered stiffness matrix.

The above procedure was done and the new stiffness matrices were obtained. Cases were run with meshes containing, about 500, 25,000, 550,000, and 1,500,000 nodes. The re-ordered stiffness matrices for 500 nodes is shown in figure 4. For the 1.5 million node case, the computer ran out of RAM. This algorithm was written to parallelize the solver, it algorithm itself has not been parallelized, part of the reason being that any gains in speed look to be offset by the large amount of communication required here. The time for the code to run is about 2-3 seconds for the 25,000 node case and about 20 seconds for the 550,000 node case.

  

Figure: Re-ordered stiffness matrix for a $226\times 226$ matrix. The number of elements of each of the 13 colors are [30, 22, 25, 23, 24, 30, 24, 21, 9, 8, 4, 5, 1]. Note that nodes of the same color have no connection, that is, the diagonal blocks are purely diagonal matrices.