Education: Greedy Graph Coloring Algorithm
Matrix assembly in Finite Element Method often suffers from race condition if two adjacent elements are being assembled at the same time. A race condition arises when the execution order of the code unwittingly affects the output. Graph coloring is one of the many methods which can alleviate this problem. In graph coloring, a graph is colored in such a way that no two adjacent nodes share the same color. Thus if the system matrix is assembled one color at a time, two adjacent elements will never get assembled concurrently, effectively eliminating the race condition. A popular graph coloring techniques is greedy graph coloring, which is described in this technical presentation. In parallel computing, resources (also known as threads) are limited. Hence each color cannot be used more than a certain number of times, usually equal to the number of available threads.

In the following demonstration we show some examples for the greedy graph coloring scheme. The MATLAB code used to generate these results may be downloaded here. Jump to examples:

Regular quad mesh on rectangular domain

The first example shows the coloring for a regular Quad mesh with 20 elements on a rectangular domain.

Click on the tabs titled "10 Colors, 2 Threads", "6 Colors, 4 Threads" and "4 Colors, 6 Threads" to see coloring scheme for each case.

Note that the ratio of threads (color element capacity) by number of elements, severely impacts the efficiency of the algorithm. If we consider the algorithm to be efficient when all the colors are full (same as using the fewer number of colors), then the fewer threads or the larger the mesh, the more efficient is the solution. This because the thread restriction gains more control over the coloring solution.

  • 10 Colors, 2 Threads
  • 6 Colors, 4 Threads
  • 4 Colors, 6 Threads
Regular triangular mesh on rectangular domain

The second example shows the coloring for a regular Tria mesh with 40 elements on a rectangular domain. Triangular elements commonly share nodes with more elements, thus requiring more colors (even if we keep the number of elements fixed)

Click on the tabs "20 Colors, 2 Threads", "12 Colors, 4 Threads" and "8 Colors, 6 Threads" to see coloring scheme for each case.

  • 20 Colors, 2 Threads
  • 12 Colors, 4 Threads
  • 8 Colors, 6 Threads
Triangular mesh on circular domain

The coloring does not require for the domain to have any type of structure, nor the elements to be of any certain type. It can be universally applied to domains of all shapes and sizes. In the final example we illustrate the coloring for a circular domain. A regular Tria mesh with 92 elements is used to discretize the domain.

Two cases are depicted under the tabs titled "14 Colors, 8 Threads" and "10 Colors, 16 Threads". Other cases can be generated by modifying the provided MATLAB code.

  • 14 Colors, 8 Threads
  • 10 Colors, 16 Threads

1. Technical Presentations on Greedy graph coloring algorithm. PDF
2. MATLAB code for Greedy graph coloring algorithm. Code