Skip to content

Use a bit vector in greedy coloring

Carsten Gräser requested to merge feature/use-flag-vector-in-coloring into master

Instead of using a set-like container we can simply mark colors used by neighbors in a bit vector. Since the number of colors is expected to be small, this is significantly faster. E.g. matrix coloring is up to twice as fast. Notice that we use std::vector<char> instead of std::vector<bool> since memory usage is not an issue and bit access is measurably faster.

This also adds some documentation (for my later self) of the choice of container and why it's used among the various possible alternatives.

This coloring is now probably as good as it can get. In comparison to grid refinement and matrix assembly it's almost for free. Using the advancing front (aka. breadth first search) it provides very good colorings that are in fact provably quasi-optimal (i.e. mesh independent).

Merge request reports

Loading