Debian Codegraph @

include/deal.II/lac/sparsity_tools.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2008 - 2023 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_sparsity_tools_h
16 #define dealii_sparsity_tools_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/exceptions.h>
22 #include <deal.II/base/index_set.h>
23 #include <deal.II/base/mpi_stub.h>
24
25 #include <deal.II/lac/block_sparsity_pattern.h>
26 #include <deal.II/lac/dynamic_sparsity_pattern.h>
27 #include <deal.II/lac/sparsity_pattern.h>
28
29 #include <memory>
30 #include <vector>
31
32 DEAL_II_NAMESPACE_OPEN
33
34
35 /**
36 * @addtogroup Sparsity
37 * @{
38 */
39
40 /**
41 * A namespace for functions that deal with things that one can do on sparsity
42 * patterns, such as renumbering rows and columns (or degrees of freedom if
43 * you want) according to the connectivity, or partitioning degrees of
44 * freedom.
45 */
46 namespace SparsityTools
47 {
48 /**
49 * Enumerator with options for partitioner
50 */
51 enum class Partitioner
52 {
53 /**
54 * Use METIS partitioner.
55 */
56 metis = 0,
57 /**
58 * Use ZOLTAN partitioner.
59 */
60 zoltan
61 };
62
63
64 /**
65 * Use a partitioning algorithm to generate a partitioning of the degrees of
66 * freedom represented by this sparsity pattern. In effect, we view this
67 * sparsity pattern as a graph of connections between various degrees of
68 * freedom, where each nonzero entry in the sparsity pattern corresponds to
69 * an edge between two nodes in the connection graph. The goal is then to
70 * decompose this graph into groups of nodes so that a minimal number of
71 * edges are cut by the boundaries between node groups. This partitioning is
72 * done by METIS or ZOLTAN, depending upon which partitioner is chosen
73 * in the fourth argument. The default is METIS. Note that METIS and
74 * ZOLTAN can only partition symmetric sparsity patterns, and that of
75 * course the sparsity pattern has to be square. We do not check for
76 * symmetry of the sparsity pattern, since this is an expensive operation,
77 * but rather leave this as the responsibility of caller of this function.
78 *
79 * After calling this function, the output array will have values between
80 * zero and @p n_partitions-1 for each node (i.e. row or column of the
81 * matrix).
82 *
83 * If deal.II was not installed with packages ZOLTAN or METIS, this
84 * function will generate an error when corresponding partition method
85 * is chosen, unless @p n_partitions is one. I.e., you can write a program
86 * so that it runs in the single-processor single-partition case without
87 * the packages installed, and only requires them installed when
88 * multiple partitions are required.
89 *
90 * Note that the sparsity pattern itself is not changed by calling this
91 * function. However, you will likely use the information generated by
92 * calling this function to renumber degrees of freedom, after which you
93 * will of course have to regenerate the sparsity pattern.
94 *
95 * This function will rarely be called separately, since in finite element
96 * methods you will want to partition the mesh, not the matrix. This can be
97 * done by calling @p GridTools::partition_triangulation.
98 */
99 void
100 partition(const SparsityPattern &sparsity_pattern,
101 const unsigned int n_partitions,
102 std::vector<unsigned int> &partition_indices,
103 const Partitioner partitioner = Partitioner::metis);
104
105
106 /**
107 * This function performs the same operation as the one above, except that
108 * it takes into consideration a set of @p cell_weights, which allow the
109 * partitioner to balance the graph while taking into consideration the
110 * computational effort expended on each cell.
111 *
112 * @note If the @p cell_weights vector is empty, then no weighting is taken
113 * into consideration. If not then the size of this vector must equal to the
114 * number of active cells in the triangulation.
115 */
116 void
117 partition(const SparsityPattern &sparsity_pattern,
118 const std::vector<unsigned int> &cell_weights,
119 const unsigned int n_partitions,
120 std::vector<unsigned int> &partition_indices,
121 const Partitioner partitioner = Partitioner::metis);
122
123 /**
124 * Using a coloring algorithm provided by ZOLTAN to color nodes whose
125 * connections are represented using a SparsityPattern object. In effect,
126 * we view this sparsity pattern as a graph of connections between nodes,
127 * where each nonzero entry in the @p sparsity_pattern corresponds to
128 * an edge between two nodes. The goal is to assign each node a color index
129 * such that no two directly connected nodes have the same color.
130 * The assigned colors are listed in @p color_indices indexed from one and
131 * the function returns total number of colors used. ZOLTAN coloring
132 * algorithm is run in serial by each processor. Hence all processors have
133 * coloring information of all the nodes. A wrapper function to this
134 * function is available in GraphColoring namespace as well.
135 *
136 * Note that this function requires that SparsityPattern be symmetric
137 * (and hence square) i.e an undirected graph representation. We do not
138 * check for symmetry of the sparsity pattern, since this is an expensive
139 * operation, but rather leave this as the responsibility of caller of
140 * this function.
141 *
142 * @image html color_undirected_graph.png
143 * The usage of the function is illustrated by the image above, showing five
144 * nodes numbered from 0 to 4. The connections shown are bidirectional.
145 * After coloring, it is clear that no two directly connected nodes are
146 * assigned the same color.
147 *
148 * If deal.II was not installed with package ZOLTAN, this function will
149 * generate an error.
150 *
151 * @note The current function is an alternative to
152 * GraphColoring::make_graph_coloring() which is tailored to graph
153 * coloring arising in shared-memory parallel assembly of matrices.
154 */
155 unsigned int
156 color_sparsity_pattern(const SparsityPattern &sparsity_pattern,
157 std::vector<unsigned int> &color_indices);
158
159 /**
160 * For a given sparsity pattern, compute a re-enumeration of row/column
161 * indices based on the algorithm by Cuthill-McKee.
162 *
163 * This algorithm is a graph renumbering algorithm in which we attempt to
164 * find a new numbering of all nodes of a graph based on their connectivity
165 * to other nodes (i.e. the edges that connect nodes). This connectivity is
166 * here represented by the sparsity pattern. In many cases within the
167 * library, the nodes represent degrees of freedom and edges are nonzero
168 * entries in a matrix, i.e. pairs of degrees of freedom that couple through
169 * the action of a bilinear form.
170 *
171 * The algorithms starts at a node, searches the other nodes for those which
172 * are coupled with the one we started with and numbers these in a certain
173 * way. It then finds the second level of nodes, namely those that couple
174 * with those of the previous level (which were those that coupled with the
175 * initial node) and numbers these. And so on. For the details of the
176 * algorithm, especially the numbering within each level, we refer the
177 * reader to the book of Schwarz (H. R. Schwarz: Methode der finiten
178 * Elemente).
179 *
180 * These algorithms have one major drawback: they require a good starting
181 * node, i.e. node that will have number zero in the output array. A
182 * starting node forming the initial level of nodes can thus be given by the
183 * user, e.g. by exploiting knowledge of the actual topology of the domain.
184 * It is also possible to give several starting indices, which may be used
185 * to simulate a simple upstream numbering (by giving the inflow nodes as
186 * starting values) or to make preconditioning faster (by letting the
187 * Dirichlet boundary indices be starting points).
188 *
189 * If no starting index is given, one is chosen automatically, namely one
190 * with the smallest coordination number (the coordination number is the
191 * number of other nodes this node couples with). This node is usually
192 * located on the boundary of the domain. There is, however, large ambiguity
193 * in this when using the hierarchical meshes used in this library, since in
194 * most cases the computational domain is not approximated by tilting and
195 * deforming elements and by plugging together variable numbers of elements
196 * at vertices, but rather by hierarchical refinement. There is therefore a
197 * large number of nodes with equal coordination numbers. The renumbering
198 * algorithms will therefore not give optimal results.
199 *
200 * If the graph has two or more unconnected components and if no starting
201 * indices are given, the algorithm will number each component
202 * consecutively. However, this requires the determination of a starting
203 * index for each component; as a consequence, the algorithm will produce an
204 * exception if starting indices are given, taking the latter as an
205 * indication that the caller of the function would like to override the
206 * part of the algorithm that chooses starting indices.
207 */
208 void
209 reorder_Cuthill_McKee(
210 const DynamicSparsityPattern &sparsity,
211 std::vector<DynamicSparsityPattern::size_type> &new_indices,
212 const std::vector<DynamicSparsityPattern::size_type> &starting_indices =
213 std::vector<DynamicSparsityPattern::size_type>());
214
215 /**
216 * For a given sparsity pattern, compute a re-enumeration of row/column
217 * indices in a hierarchical way, similar to what
218 * DoFRenumbering::hierarchical does for degrees of freedom on
219 * hierarchically refined meshes.
220 *
221 * This algorithm first selects a node with the minimum number of neighbors
222 * and puts that node and its direct neighbors into one chunk. Next, it
223 * selects one of the neighbors of the already selected nodes, adds the node
224 * and its direct neighbors that are not part of one of the previous chunks,
225 * into the next. After this sweep, neighboring nodes are grouped together.
226 * To ensure a similar grouping on a more global level, this grouping is
227 * called recursively on the groups so formed. The recursion stops when no
228 * further grouping is possible. Eventually, the ordering obtained by this
229 * method passes through the indices represented in the sparsity pattern in
230 * a z-like way.
231 *
232 * If the graph has two or more unconnected components, the algorithm will
233 * number each component consecutively, starting with the components with
234 * the lowest number of nodes.
235 */
236 void
237 reorder_hierarchical(
238 const DynamicSparsityPattern &sparsity,
239 std::vector<DynamicSparsityPattern::size_type> &new_indices);
240
241 #ifdef DEAL_II_WITH_MPI
242 /**
243 * Communicate rows in a dynamic sparsity pattern over MPI.
244 *
245 * @param[in,out] dsp A dynamic sparsity pattern that has been built locally
246 * and for which we need to exchange entries with other processors to make
247 * sure that each processor knows all the elements of the rows of a matrix
248 * it stores and that may eventually be written to. This sparsity pattern
249 * will be changed as a result of this function: All entries in rows that
250 * belong to a different processor are sent to them and added there.
251 *
252 * @param locally_owned_rows An IndexSet describing the rows owned by the
253 * calling MPI process. The index set shall be one-to-one among the
254 * processors in the communicator.
255 *
256 * @param mpi_comm The MPI communicator shared between the processors that
257 * participate in this operation.
258 *
259 * @param locally_relevant_rows The range of elements stored on the local
260 * MPI process. This should be the one used in the constructor of the
261 * DynamicSparsityPattern, and should also be the locally relevant set. Only
262 * rows contained in this set are checked in dsp for transfer. This function
263 * needs to be used with PETScWrappers::MPI::SparseMatrix for it to work
264 * correctly in a parallel computation.
265 */
266 void
267 distribute_sparsity_pattern(DynamicSparsityPattern &dsp,
268 const IndexSet &locally_owned_rows,
269 const MPI_Comm mpi_comm,
270 const IndexSet &locally_relevant_rows);
271
272 /**
273 * Communicate rows in a dynamic sparsity pattern over MPI, similar to the
274 * one above but using a vector `rows_per_cpu` containing the number of
275 * rows per CPU for determining ownership. This is typically the value
276 * returned by Utilities::MPI::all_gather(MPI_Comm,
277 * DoFHandler::locally_owned_dofs()) -- given that the construction of the
278 * input to this function involves all-to-all communication, it is typically
279 * slower than the function above for more than a thousand of processes (and
280 * quick enough also for small sizes).
281 */
282 void
283 distribute_sparsity_pattern(
284 DynamicSparsityPattern &dsp,
285 const std::vector<DynamicSparsityPattern::size_type> &rows_per_cpu,
286 const MPI_Comm mpi_comm,
287 const IndexSet &myrange);
288
289 /**
290 * Similar to the function above, but for BlockDynamicSparsityPattern
291 * instead.
292 *
293 * @param[in,out] dsp The locally built sparsity pattern to be modified.
294 *
295 * @param locally_owned_rows An IndexSet describing the rows owned by the
296 * calling MPI process. The index set shall be one-to-one among the
297 * processors in the communicator.
298 *
299 * @param mpi_comm The MPI communicator to use.
300 *
301 * @param locally_relevant_rows Typically the locally relevant DoFs.
302 */
303 void
304 distribute_sparsity_pattern(BlockDynamicSparsityPattern &dsp,
305 const IndexSet &locally_owned_rows,
306 const MPI_Comm mpi_comm,
307 const IndexSet &locally_relevant_rows);
308
309 /**
310 * @deprecated Use the distribute_sparsity_pattern() with a single index set
311 * for the present MPI process only.
312 */
313 void
314 distribute_sparsity_pattern(BlockDynamicSparsityPattern &dsp,
315 const std::vector<IndexSet> &owned_set_per_cpu,
316 const MPI_Comm mpi_comm,
317 const IndexSet &myrange);
318
319 /**
320 * Gather rows in a dynamic sparsity pattern over MPI.
321 * The function is similar to SparsityTools::distribute(),
322 * however instead of distributing sparsity stored in non-owned
323 * rows on this MPI process, this function will gather sparsity
324 * from other MPI processes and will add this to the local
325 * DynamicSparsityPattern.
326 *
327 * @param dsp A dynamic sparsity pattern that has been built locally and which
328 * we need to extend according to the sparsity of rows stored on other MPI
329 * processes.
330 *
331 * @param locally_owned_rows An IndexSet describing the rows owned by the
332 * calling MPI process. The index set shall be one-to-one among the
333 * processors in the communicator.
334 *
335 * @param mpi_comm The MPI communicator shared between the processors that
336 * participate in this operation.
337 *
338 * @param locally_relevant_rows The range of rows this MPI process needs to
339 * gather. Only the part which is not included in the locally owned rows will
340 * be used.
341 */
342 void
343 gather_sparsity_pattern(DynamicSparsityPattern &dsp,
344 const IndexSet &locally_owned_rows,
345 const MPI_Comm mpi_comm,
346 const IndexSet &locally_relevant_rows);
347
348 #endif
349
350
351 /**
352 * Exception
353 */
354 DeclExceptionMsg(ExcMETISNotInstalled,
355 "The function you called requires METIS, but you did not "
356 "configure deal.II with METIS.");
357
358 /**
359 * Exception
360 */
361 DeclException1(ExcInvalidNumberOfPartitions,
362 int,
363 << "The number of partitions you gave is " << arg1
364 << ", but must be greater than zero.");
365
366 /**
367 * Exception
368 */
369 DeclException1(ExcMETISError,
370 int,
371 << " An error with error number " << arg1
372 << " occurred while calling a METIS function");
373
374 /**
375 * Exception
376 */
377 DeclException2(ExcInvalidArraySize,
378 int,
379 int,
380 << "The array has size " << arg1 << " but should have size "
381 << arg2);
382 /**
383 * Exception
384 */
385 DeclExceptionMsg(
386 ExcZOLTANNotInstalled,
387 "The function you called requires ZOLTAN, but you did not "
388 "configure deal.II with ZOLTAN or zoltan_cpp.h is not available.");
389 } // namespace SparsityTools
390
391 /**
392 * @}
393 */
394
395 DEAL_II_NAMESPACE_CLOSE
396
397 #endif