![]() |
Reference documentation for deal.II version 9.1.1
|
Functions | |
template<typename Iterator > | |
std::vector< std::vector< Iterator > > | make_graph_coloring (const Iterator &begin, const typename identity< Iterator >::type &end, const std::function< std::vector< types::global_dof_index >(const typename identity< Iterator >::type &)> &get_conflict_indices) |
unsigned int | color_sparsity_pattern (const SparsityPattern &sparsity_pattern, std::vector< unsigned int > &color_indices) |
A namespace containing functions that can color graphs.
std::vector<std::vector<Iterator> > GraphColoring::make_graph_coloring | ( | const Iterator & | begin, |
const typename identity< Iterator >::type & | end, | ||
const std::function< std::vector< types::global_dof_index >(const typename identity< Iterator >::type &)> & | get_conflict_indices | ||
) |
Create a partitioning of the given range of iterators so that iterators that point to conflicting objects will be placed into different partitions, where the question whether two objects conflict is determined by a user-provided function.
This function can also be considered as a graph coloring: each object pointed to by an iterator is considered to be a node and there is an edge between each two nodes that conflict. The graph coloring algorithm then assigns a color to each node in such a way that two nodes connected by an edge do not have the same color.
A typical use case for this function is in assembling a matrix in parallel. There, one would like to assemble local contributions on different cells at the same time (an operation that is purely local and so requires no synchronization) but then we need to add these local contributions to the global matrix. In general, the contributions from different cells may be to the same matrix entries if the cells share degrees of freedom and, consequently, can not happen at the same time unless we want to risk a race condition (see http://en.wikipedia.org/wiki/Race_condition). Thus, we call these two cells in conflict, and we can only allow operations in parallel from cells that do not conflict. In other words, two cells are in conflict if the set of matrix entries (for example characterized by the rows) have a nonempty intersection.
In this generality, computing the graph of conflicts would require calling a function that determines whether two iterators (or the two objects they represent) conflict, and calling it for every pair of iterators, i.e., \(\frac 12 N (N-1)\) times. This is too expensive in general. A better approach is to require a user-defined function that returns for every iterator it is called for a set of indicators of some kind that characterize a conflict; two iterators are in conflict if their conflict indicator sets have a nonempty intersection. In the example of assembling a matrix, the conflict indicator set would contain the indices of all degrees of freedom on the cell pointed to (in the case of continuous Galerkin methods) or the union of indices of degree of freedom on the current cell and all cells adjacent to the faces of the current cell (in the case of discontinuous Galerkin methods, because there one computes face integrals coupling the degrees of freedom connected by a common face – see step-12).
In other situations, the conflict indicator sets may represent something different altogether – it is up to the caller of this function to describe what it means for two iterators to conflict. Given this, computing conflict graph edges can be done significantly more cheaply than with \({\cal O}(N^2)\) operations.
In any case, the result of the function will be so that iterators whose conflict indicator sets have overlap will not be assigned to the same color.
[in] | begin | The first element of a range of iterators for which a coloring is sought. |
[in] | end | The element past the end of the range of iterators. |
[in] | get_conflict_indices | A user defined function object returning a set of indicators that are descriptive of what represents a conflict. See above for a more thorough discussion. |
Definition at line 544 of file graph_coloring.h.
unsigned int GraphColoring::color_sparsity_pattern | ( | const SparsityPattern & | sparsity_pattern, |
std::vector< unsigned int > & | color_indices | ||
) |
GraphColoring::color_sparsity_pattern, a wrapper function for SparsityTools::color_sparsity_pattern, is an alternate method for coloring using graph connections represented by SparsityPattern. For further details, refer to SparsityTools::color_sparsity_pattern.
Definition at line 24 of file graph_coloring.cc.