1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 1998 - 2019 by the deal.II authors
4 //
5 // This file is part of the deal.II library.
6 //
7 // The deal.II library is free software; you can use it, redistribute
8 // it, and/or modify it under the terms of the GNU Lesser General
9 // Public License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
11 // The full text of the license can be found in the file LICENSE.md at
12 // the top level directory of deal.II.
13 //
14 // ---------------------------------------------------------------------
15
16 #ifndef dealii_affine_constraints_h
17 #define dealii_affine_constraints_h
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/subscriptor.h>
24 #include <deal.II/base/table.h>
25 #include <deal.II/base/template_constraints.h>
26 #include <deal.II/base/thread_local_storage.h>
27
28 #include <deal.II/lac/vector.h>
29 #include <deal.II/lac/vector_element_access.h>
30
31 #include <boost/range/iterator_range.hpp>
32
33 #include <set>
34 #include <utility>
35 #include <vector>
36
37 DEAL_II_NAMESPACE_OPEN
38
39 // Forward declarations
40 #ifndef DOXYGEN
41 template <typename>
42 class FullMatrix;
43 class SparsityPattern;
44 class DynamicSparsityPattern;
45 class BlockSparsityPattern;
46 class BlockDynamicSparsityPattern;
47 template <typename number>
48 class SparseMatrix;
49 template <typename number>
50 class BlockSparseMatrix;
51
52 namespace internal
53 {
54 namespace AffineConstraints
55 {
56 using size_type = types::global_dof_index;
57
58 /**
59 * This struct contains all the information we need to store about each of
60 * the global entries (global_row): are they obtained directly by some local
61 * entry (local_row) or some constraints (constraint_position). This is not
62 * directly used in the user code, but accessed via the GlobalRowsFromLocal.
63 *
64 * The actions performed here correspond to reshaping the constraint
65 * information from global degrees of freedom to local ones (i.e.,
66 * cell-related DoFs), and also transforming the constraint information from
67 * compressed row storage (each local dof that is constrained has a list of
68 * constraint entries associated to it) into compressed column storage based
69 * on the cell-related DoFs (we have a list of global degrees of freedom,
70 * and to each we have a list of local rows where the entries come from). To
71 * increase the speed, we additionally store whether an entry is generated
72 * directly from the local degrees of freedom or whether it comes from a
73 * constraint.
74 */
75 struct Distributing
76 {
77 Distributing(const size_type global_row = numbers::invalid_size_type,
78 const size_type local_row = numbers::invalid_size_type);
79
80 Distributing(const Distributing &in);
81
82 Distributing &
83 operator=(const Distributing &in);
84
85 bool
86 operator<(const Distributing &in) const
87 {
88 return global_row < in.global_row;
89 }
90
91 size_type global_row;
92 size_type local_row;
93 mutable size_type constraint_position;
94 };
95
96
97
98 /**
99 * This class represents a cache for constraints that are encountered on a
100 * local level. The functionality is similar to
101 * std::vector<std::vector<std::pair<uint,double> > >, but tuned so that
102 * frequent memory allocation for each entry is avoided. The data is put
103 * into a std::vector<std::pair<uint,double> > and the row length is kept
104 * fixed at row_length. Both the number of rows and the row length can
105 * change is this structure is filled. In that case, the data is
106 * rearranged. This is not directly used in the user code, but accessed
107 * via the GlobalRowsFromLocal.
108 */
109 template <typename number>
110 struct DataCache
111 {
112 DataCache();
113
114 void
115 reinit();
116
117 size_type
118 insert_new_index(const std::pair<size_type, number> &pair);
119
120 void
121 append_index(const size_type index,
122 const std::pair<size_type, number> &pair);
123
124 size_type
125 get_size(const size_type index) const;
126
127 const std::pair<size_type, number> *
128 get_entry(const size_type index) const;
129
130 size_type row_length;
131
132 std::vector<std::pair<size_type, number>> data;
133
134 std::vector<size_type> individual_size;
135 };
136
137
138
139 /**
140 * A data structure that collects all the global rows from a local
141 * contribution (cell) and their origin (direct/constraint). This
142 * is basically a vector consisting of "Distributing" structs
143 * using access via the DataCache. The structure provides some
144 * specialized sort and insert functions.
145 *
146 * In case there are no constraints, this is basically a list of pairs
147 * `<uint,uint>` with the first index being the global index and the second
148 * index the local index. The list is sorted with respect to the global
149 * index.
150 *
151 * In case there are constraints, a global dof might get a contribution also
152 * because it gets data from a constrained dof. This means that a global dof
153 * might also have indirect contributions from a local dof via a constraint,
154 * besides the direct ones.
155 *
156 * The actions performed here correspond to reshaping the constraint
157 * information from global degrees of freedom to local ones (i.e.,
158 * cell-related DoFs), and also transforming the constraint information from
159 * compressed row storage (each local dof that is constrained has a list of
160 * constraint entries associated to it) into compressed column storage based
161 * on the cell-related DoFs (we have a list of global degrees of freedom,
162 * and to each we have a list of local rows where the entries come from). To
163 * increase the speed, we additionally store whether an entry is generated
164 * directly from the local degrees of freedom or whether it comes from a
165 * constraint.
166 */
167 template <typename number>
168 class GlobalRowsFromLocal
169 {
170 public:
171 /**
172 * Constructor.
173 */
174 GlobalRowsFromLocal();
175
176 void
177 reinit(const size_type n_local_rows);
178
179 void
180 insert_index(const size_type global_row,
181 const size_type local_row,
182 const number constraint_value);
183 void
184 sort();
185
186 void
187 print(std::ostream &os);
188
189 /**
190 * Return the number of global indices in the struct.
191 */
192 size_type
193 size() const;
194
195 /**
196 * Return the number of constraints that are associated to the
197 * counter_index-th entry in the list.
198 */
199 size_type
200 size(const size_type counter_index) const;
201
202 /**
203 * Return the global row of the counter_index-th entry in the list.
204 */
205 size_type
206 global_row(const size_type counter_index) const;
207
208 /**
209 * Return the global row of the counter_index-th entry in the list.
210 */
211 size_type &
212 global_row(const size_type counter_index);
213
214 /**
215 * Return the local row in the cell matrix associated with the
216 * counter_index-th entry in the list. Return invalid_size_type for
217 * constrained rows.
218 */
219 size_type
220 local_row(const size_type counter_index) const;
221
222 /**
223 * Return a reference instead of the value as in the function above.
224 */
225 size_type &
226 local_row(const size_type counter_index);
227
228 /**
229 * Return the local row in the cell matrix associated with the
230 * counter_index-th entry in the list in the index_in_constraint-th
231 * position of constraints.
232 */
233 size_type
234 local_row(const size_type counter_index,
235 const size_type index_in_constraint) const;
236
237 /**
238 * Return the value of the constraint in the counter_index-th entry in
239 * the list in the index_in_constraint-th position of constraints.
240 */
241 number
242 constraint_value(const size_type counter_index,
243 const size_type index_in_constraint) const;
244
245 /**
246 * Return whether there is one row with indirect contributions (i.e.,
247 * there has been at least one constraint with non-trivial
248 * ConstraintLine).
249 */
250 bool
251 have_indirect_rows() const;
252
253 /**
254 * Append an entry that is constrained. This means that there is one less
255 * nontrivial row.
256 */
257 void
258 insert_constraint(const size_type constrained_local_dof);
259
260 /**
261 * Return the number of constrained dofs in the structure. Constrained
262 * dofs do not contribute directly to the matrix, but are needed in order
263 * to set matrix diagonals and resolve inhomogeneities.
264 */
265 size_type
266 n_constraints() const;
267
268 /**
269 * Return the number of constrained dofs in the structure that have an
270 * inhomogeneity.
271 */
272 size_type
273 n_inhomogeneities() const;
274
275 /**
276 * This function tells the structure that the ith constraint is
277 * inhomogeneous. inhomogeneous constraints contribute to right hand
278 * sides, so to have fast access to them, put them before homogeneous
279 * constraints.
280 */
281 void
282 set_ith_constraint_inhomogeneous(const size_type i);
283
284 /**
285 * The local row where constraint number i was detected, to find that row
286 * easily when the GlobalRowsToLocal has been set up.
287 */
288 size_type
289 constraint_origin(size_type i) const;
290
291 /**
292 * A vector that contains all the global ids and the corresponding local
293 * ids as well as a pointer to that data where we store how to resolve
294 * constraints.
295 */
296 std::vector<Distributing> total_row_indices;
297
298 private:
299 /**
300 * A data structure that holds the actual data from the constraints.
301 */
302 DataCache<number> data_cache;
303
304 /**
305 * A number that states how many rows there are, constraints
306 * disregarded.
307 */
308 size_type n_active_rows;
309
310 /**
311 * A number that represents the number of rows with
312 * inhomogeneous constraints.
313 */
314 size_type n_inhomogeneous_rows;
315 };
316
317
318
319 /**
320 * Scratch data that is used during calls to distribute_local_to_global and
321 * add_entries_local_to_global. In order to avoid frequent memory
322 * allocation, we keep the data alive from one call to the next in a static
323 * variable. Since we want to allow for different number types in matrices,
324 * this is a template.
325 *
326 * Since each thread gets its private version of scratch data out of a
327 * ThreadLocalStorage, no conflicting access can occur. For this to be
328 * valid, we need to make sure that no call within
329 * distribute_local_to_global is made that by itself can spawn tasks.
330 * Otherwise, we might end up in a situation where several threads fight for
331 * the data.
332 *
333 * Access to the scratch data is only through an accessor class which
334 * handles the access as well as marks the data as used.
335 */
336 template <typename number>
337 struct ScratchData
338 {
339 /**
340 * Constructor, does nothing.
341 */
ScratchDataScratchData342 ScratchData()
343 : in_use(false)
344 {}
345
346 /**
347 * Copy constructor, does nothing
348 */
ScratchDataScratchData349 ScratchData(const ScratchData &)
350 : in_use(false)
351 {}
352
353 /**
354 * Stores whether the data is currently in use.
355 */
356 bool in_use;
357
358 /**
359 * Temporary array for column indices
360 */
361 std::vector<size_type> columns;
362
363 /**
364 * Temporary array for column values
365 */
366 std::vector<number> values;
367
368 /**
369 * Temporary array for block start indices
370 */
371 std::vector<size_type> block_starts;
372
373 /**
374 * Temporary array for vector indices
375 */
376 std::vector<size_type> vector_indices;
377
378 /**
379 * Temporary array for vector values
380 */
381 std::vector<number> vector_values;
382
383 /**
384 * Data array for reorder row/column indices.
385 */
386 GlobalRowsFromLocal<number> global_rows;
387
388 /**
389 * Data array for reorder row/column indices.
390 */
391 GlobalRowsFromLocal<number> global_columns;
392 };
393 } // namespace AffineConstraints
394 } // namespace internal
395
396 namespace internal
397 {
398 namespace AffineConstraintsImplementation
399 {
400 template <class VectorType>
401 void
402 set_zero_all(const std::vector<types::global_dof_index> &cm,
403 VectorType & vec);
404
405 template <class T>
406 void
407 set_zero_all(const std::vector<types::global_dof_index> &cm,
408 dealii::Vector<T> & vec);
409
410 template <class T>
411 void
412 set_zero_all(const std::vector<types::global_dof_index> &cm,
413 dealii::BlockVector<T> & vec);
414 } // namespace AffineConstraintsImplementation
415 } // namespace internal
416
417
418 template <typename number>
419 class AffineConstraints;
420 #endif
421
422 // TODO[WB]: We should have a function of the kind
423 // AffineConstraints::add_constraint (const size_type constrained_dof,
424 // const std::vector<std::pair<size_type, number> > &entries,
425 // const number inhomogeneity = 0);
426 // rather than building up constraints piecemeal through add_line/add_entry
427 // etc. This would also eliminate the possibility of accidentally changing
428 // existing constraints into something pointless, see the discussion on the
429 // mailing list on "Tiny bug in interpolate_boundary_values" in Sept. 2010.
430
431 /**
432 * This class implements dealing with linear (possibly inhomogeneous)
433 * constraints on degrees of freedom. The concept and origin of such
434 * constraints is extensively described in the
435 * @ref constraints
436 * module. The class is meant to deal with a limited number of constraints
437 * relative to the total number of degrees of freedom, for example a few per
438 * cent up to maybe 30 per cent; and with a linear combination of <i>M</i>
439 * other degrees of freedom where <i>M</i> is also relatively small (no larger
440 * than at most around the average number of entries per row of a linear
441 * system). It is <em>not</em> meant to describe full rank linear systems.
442 *
443 * The algorithms used in the implementation of this class are described in
444 * some detail in the
445 * @ref hp_paper "hp paper".
446 * There is also a significant amount of documentation on how to use this
447 * class in the
448 * @ref constraints
449 * module.
450 *
451 *
452 * <h3>Description of constraints</h3>
453 *
454 * Each "line" in objects of this class corresponds to one constrained degree
455 * of freedom, with the number of the line being <i>i</i>, entered by using
456 * add_line() or add_lines(). The entries in this line are pairs of the form
457 * (<i>j</i>,<i>a<sub>ij</sub></i>), which are added by add_entry() or
458 * add_entries(). The organization is essentially a SparsityPattern, but with
459 * only a few lines containing nonzero elements, and therefore no data wasted
460 * on the others. For each line, which has been added by the mechanism above,
461 * an elimination of the constrained degree of freedom of the form
462 * @f[
463 * x_i = \sum_j a_{ij} x_j + b_i
464 * @f]
465 * is performed, where <i>b<sub>i</sub></i> is optional and set by
466 * set_inhomogeneity(). Thus, if a constraint is formulated for instance as a
467 * zero mean value of several degrees of freedom, one of the degrees has to be
468 * chosen to be eliminated.
469 *
470 * Note that the constraints are linear in the <i>x<sub>i</sub></i>, and that
471 * there might be a constant (non-homogeneous) term in the constraint. This is
472 * exactly the form we need for hanging node constraints, where we need to
473 * constrain one degree of freedom in terms of others. There are other
474 * conditions of this form possible, for example for implementing mean value
475 * conditions as is done in the step-11 tutorial program. The name of the
476 * class stems from the fact that these constraints can be represented in
477 * matrix form as <b>X</b> <i>x</i> = <i>b</i>, and this object then describes
478 * the matrix <b>X</b> and the vector <i>b</i>. The most frequent way to
479 * create/fill objects of this type is using the
480 * DoFTools::make_hanging_node_constraints() function. The use of these
481 * objects is first explained in step-6.
482 *
483 * Objects of the present type are organized in lines (rows), but only those
484 * lines are stored where constraints are present. New constraints are added
485 * by adding new lines using the add_line() function, and then populating it
486 * using the add_entry() function to a given line, or add_entries() to add
487 * more than one entry at a time. The right hand side element, if nonzero, can
488 * be set using the set_inhomogeneity() function. After all constraints have
489 * been added, you need to call close(), which compresses the storage format
490 * and sorts the entries.
491 *
492 * @note Many of the algorithms this class implements are discussed in the
493 * @ref hp_paper.
494 * The algorithms are also related to those shown in <i>M. S. Shephard: Linear
495 * multipoint constraints applied via transformation as part of a direct
496 * stiffness assembly process. Int. J. Numer. Meth. Engrg., vol. 20 (1984),
497 * pp. 2107-2112.</i>, with the difference that the algorithms shown there
498 * completely eliminated constrained degrees of freedom, whereas we usually
499 * keep them as part of the linear system.
500 *
501 * @ingroup dofs
502 * @ingroup constraints
503 */
504 template <typename number = double>
505 class AffineConstraints : public Subscriptor
506 {
507 public:
508 /**
509 * Declare the type for container size.
510 */
511 using size_type = types::global_dof_index;
512
513 /**
514 * An enum that describes what should happen if the two AffineConstraints
515 * objects involved in a call to the merge() function happen to have
516 * constraints on the same degrees of freedom.
517 */
518 enum MergeConflictBehavior
519 {
520 /**
521 * Throw an exception if the two objects concerned have conflicting
522 * constraints on the same degree of freedom.
523 */
524 no_conflicts_allowed,
525
526 /**
527 * In an operation <code>cm1.merge(cm2)</code>, if <code>cm1</code> and
528 * <code>cm2</code> have constraints on the same degree of freedom, take
529 * the one from <code>cm1</code>.
530 */
531 left_object_wins,
532
533 /**
534 * In an operation <code>cm1.merge(cm2)</code>, if <code>cm1</code> and
535 * <code>cm2</code> have constraints on the same degree of freedom, take
536 * the one from <code>cm2</code>.
537 */
538 right_object_wins
539 };
540
541 /**
542 * Constructor. The supplied IndexSet defines which indices might be
543 * constrained inside this AffineConstraints container. In a calculation
544 * with a DoFHandler object based on parallel::distributed::Triangulation
545 * or parallel::shared::Triangulation, one should use the set of locally
546 * relevant dofs (see
547 * @ref GlossLocallyRelevantDof).
548 *
549 * The given IndexSet allows the AffineConstraints container to save
550 * memory by just not caring about degrees of freedom that are not of
551 * importance to the current processor. Alternatively, if no such
552 * IndexSet is provided, internal data structures for <i>all</i> possible
553 * indices will be created, leading to memory consumption on every
554 * processor that is proportional to the <i>overall</i> size of the
555 * problem, not just proportional to the size of the portion of the
556 * overall problem that is handled by the current processor.
557 */
558 explicit AffineConstraints(const IndexSet &local_constraints = IndexSet());
559
560 /**
561 * Copy constructor
562 */
563 explicit AffineConstraints(const AffineConstraints &affine_constraints);
564
565 /**
566 * Move constructor
567 */
568 AffineConstraints(AffineConstraints &&affine_constraints) noexcept =
569 default; // NOLINT
570
571 /**
572 * Copy operator. Like for many other large objects, this operator
573 * is deleted to avoid its inadvertent use in places such as
574 * accidentally declaring a @p AffineConstraints object as a
575 * function argument by value, rather than by reference.
576 *
577 * However, you can use the copy_from() function to explicitly
578 * copy AffineConstraints objects.
579 */
580 AffineConstraints &
581 operator=(const AffineConstraints &) = delete;
582
583 /**
584 * Move assignment operator
585 */
586 AffineConstraints &
587 operator=(AffineConstraints &&affine_constraints) noexcept =
588 default; // NOLINT
589
590 /**
591 * Copy the given object to the current one.
592 *
593 * This function exists because @p operator=() is explicitly
594 * disabled.
595 */
596 void
597 copy_from(const AffineConstraints &other);
598
599 /**
600 * clear() the AffineConstraints object and supply an IndexSet with lines
601 * that may be constrained. This function is only relevant in the
602 * distributed case to supply a different IndexSet. Otherwise this routine
603 * is equivalent to calling clear(). See the constructor for details.
604 */
605 void
606 reinit(const IndexSet &local_constraints = IndexSet());
607
608 /**
609 * Determines if we can store a constraint for the given @p line_n. This
610 * routine only matters in the distributed case and checks if the IndexSet
611 * allows storage of this line. Always returns true if not in the
612 * distributed case.
613 */
614 bool
615 can_store_line(const size_type line_n) const;
616
617 /**
618 * Return the index set describing locally relevant lines if any are
619 * present. Note that if no local lines were given, this represents an empty
620 * IndexSet, whereas otherwise it contains the global problem size and the
621 * local range.
622 */
623 const IndexSet &
624 get_local_lines() const;
625
626 /**
627 * This function copies the content of @p constraints_in with DoFs that are
628 * element of the IndexSet @p filter. Elements that are not present in the
629 * IndexSet are ignored. All DoFs will be transformed to local index space
630 * of the filter, both the constrained DoFs and the other DoFs these entries
631 * are constrained to. The local index space of the filter is a contiguous
632 * numbering of all (global) DoFs that are elements in the filter.
633 *
634 * If, for example, the filter represents the range <tt>[10,20)</tt>, and
635 * the constraints object @p constraints_in includes the global indices
636 * <tt>{7,13,14}</tt>, the indices <tt>{3,4}</tt> are added to the calling
637 * constraints object (since 13 and 14 are elements in the filter and element
638 * 13 is the fourth element in the index, and 14 is the fifth).
639 *
640 * This function provides an easy way to create a AffineConstraints for
641 * certain vector components in a vector-valued problem from a full
642 * AffineConstraints, i.e. extracting a diagonal subblock from a larger
643 * AffineConstraints. The block is specified by the IndexSet argument.
644 */
645 void
646 add_selected_constraints(const AffineConstraints &constraints_in,
647 const IndexSet & filter);
648
649 /**
650 * @name Adding constraints
651 * @{
652 */
653
654 /**
655 * Add a new line to the matrix. If the line already exists, then the
656 * function simply returns without doing anything.
657 */
658 void
659 add_line(const size_type line_n);
660
661 /**
662 * Call the first add_line() function for every index <code>i</code> for
663 * which <code>lines[i]</code> is true.
664 *
665 * This function essentially exists to allow adding several constraints of
666 * the form <i>x<sub>i</sub></i>=0 all at once, where the set of indices
667 * <i>i</i> for which these constraints should be added are given by the
668 * argument of this function. On the other hand, just as if the single-
669 * argument add_line() function were called repeatedly, the constraints can
670 * later be modified to include linear dependencies using the add_entry()
671 * function as well as inhomogeneities using set_inhomogeneity().
672 */
673 void
674 add_lines(const std::vector<bool> &lines);
675
676 /**
677 * Call the first add_line() function for every index <code>i</code> that
678 * appears in the argument.
679 *
680 * This function essentially exists to allow adding several constraints of
681 * the form <i>x<sub>i</sub></i>=0 all at once, where the set of indices
682 * <i>i</i> for which these constraints should be added are given by the
683 * argument of this function. On the other hand, just as if the single-
684 * argument add_line() function were called repeatedly, the constraints can
685 * later be modified to include linear dependencies using the add_entry()
686 * function as well as inhomogeneities using set_inhomogeneity().
687 */
688 void
689 add_lines(const std::set<size_type> &lines);
690
691 /**
692 * Call the first add_line() function for every index <code>i</code> that
693 * appears in the argument.
694 *
695 * This function essentially exists to allow adding several constraints of
696 * the form <i>x<sub>i</sub></i>=0 all at once, where the set of indices
697 * <i>i</i> for which these constraints should be added are given by the
698 * argument of this function. On the other hand, just as if the single-
699 * argument add_line() function were called repeatedly, the constraints can
700 * later be modified to include linear dependencies using the add_entry()
701 * function as well as inhomogeneities using set_inhomogeneity().
702 */
703 void
704 add_lines(const IndexSet &lines);
705
706 /**
707 * Add an entry to a given line. The list of lines is searched from the back
708 * to the front, so clever programming would add a new line (which is pushed
709 * to the back) and immediately afterwards fill the entries of that line.
710 * This way, no expensive searching is needed.
711 *
712 * If an entry with the same indices as the one this function call denotes
713 * already exists, then this function simply returns provided that the value
714 * of the entry is the same. Thus, it does no harm to enter a constraint
715 * twice.
716 */
717 void
718 add_entry(const size_type line_n, const size_type column, const number value);
719
720 /**
721 * Add a whole series of entries, denoted by pairs of column indices and
722 * values, to a line of constraints. This function is equivalent to calling
723 * the preceding function several times, but is faster.
724 */
725 void
726 add_entries(const size_type line_n,
727 const std::vector<std::pair<size_type, number>> &col_val_pairs);
728
729 /**
730 * Set an inhomogeneity to the constraint line @p line_n, according to the
731 * discussion in the general class description.
732 *
733 * @note the line needs to be added with one of the add_line() calls first.
734 */
735 void
736 set_inhomogeneity(const size_type line_n, const number value);
737
738 /**
739 * Close the filling of entries. Since the lines of a matrix of this type
740 * are usually filled in an arbitrary order and since we do not want to use
741 * associative constrainers to store the lines, we need to sort the lines
742 * and within the lines the columns before usage of the matrix. This is done
743 * through this function.
744 *
745 * Also, zero entries are discarded, since they are not needed.
746 *
747 * After closing, no more entries are accepted. If the object was already
748 * closed, then this function returns immediately.
749 *
750 * This function also resolves chains of constraints. For example, degree of
751 * freedom 13 may be constrained to $u_{13} = \frac{u_3}{2} + \frac{u_7}{2}$
752 * while degree of freedom 7 is itself constrained as $u_{7} = \frac{u_2}{2}
753 * + \frac{u_4}{2}$. Then, the resolution will be that $u_{13} =
754 * \frac{u_3}{2} + \frac{u_2}{4} + \frac{u_4}{4}$. Note, however, that
755 * cycles in this graph of constraints are not allowed, i.e. for example
756 * $u_4$ may not be constrained, directly or indirectly, to $u_{13}$ again.
757 */
758 void
759 close();
760
761 /**
762 * Merge the constraints represented by the object given as argument into
763 * the constraints represented by this object. Both objects may or may not
764 * be closed (by having their function close() called before). If this
765 * object was closed before, then it will be closed afterwards as well.
766 * Note, however, that if the other argument is closed, then merging may be
767 * significantly faster.
768 *
769 * Using the default value of the second arguments, the constraints in each
770 * of the two objects (the old one represented by this object and the
771 * argument) may not refer to the same degree of freedom, i.e. a degree of
772 * freedom that is constrained in one object may not be constrained in the
773 * second. If this is nevertheless the case, an exception is thrown.
774 * However, this behavior can be changed by providing a different value for
775 * the second argument.
776 *
777 * By default, merging two AffineConstraints objects that are initialized
778 * with different IndexSet objects is not allowed.
779 * This behavior can be altered by setting @p allow_different_local_lines
780 * appropriately.
781 *
782 * Merging a AffineConstraints that is initialized with an IndexSet
783 * and one that is not initialized with an IndexSet is not yet implemented.
784 */
785 void
786 merge(
787 const AffineConstraints & other_constraints,
788 const MergeConflictBehavior merge_conflict_behavior = no_conflicts_allowed,
789 const bool allow_different_local_lines = false);
790
791 /**
792 * Shift all entries of this matrix down @p offset rows and over @p offset
793 * columns. If this object is initialized with an IndexSet, local_lines are
794 * shifted as well.
795 *
796 * This function is useful if you are building block matrices, where all
797 * blocks are built by the same DoFHandler object, i.e. the matrix size is
798 * larger than the number of degrees of freedom. Since several matrix rows
799 * and columns correspond to the same degrees of freedom, you'd generate
800 * several constraint objects, then shift them, and finally merge() them
801 * together again.
802 */
803 void
804 shift(const size_type offset);
805
806 /**
807 * Clear all entries of this matrix. Reset the flag determining whether new
808 * entries are accepted or not.
809 *
810 * This function may be called also on objects which are empty or already
811 * cleared.
812 */
813 void
814 clear();
815
816 /**
817 * @}
818 */
819
820 /**
821 * @name Querying constraints
822 * @{
823 */
824
825 /**
826 * Return number of constraints stored in this matrix.
827 */
828 size_type
829 n_constraints() const;
830
831 /**
832 * Return whether the degree of freedom with number @p line_n is a
833 * constrained one.
834 *
835 * Note that if close() was called before, then this function is
836 * significantly faster, since then the constrained degrees of freedom are
837 * sorted and we can do a binary search, while before close() was called, we
838 * have to perform a linear search through all entries.
839 */
840 bool
841 is_constrained(const size_type line_n) const;
842
843 /**
844 * Return whether the dof is constrained, and whether it is constrained to
845 * only one other degree of freedom with weight one. The function therefore
846 * returns whether the degree of freedom would simply be eliminated in favor
847 * of exactly one other degree of freedom.
848 *
849 * The function returns @p false if either the degree of freedom is not
850 * constrained at all, or if it is constrained to more than one other degree
851 * of freedom, or if it is constrained to only one degree of freedom but
852 * with a weight different from one.
853 */
854 bool
855 is_identity_constrained(const size_type line_n) const;
856
857 /**
858 * Return whether the two given degrees of freedom are linked by an equality
859 * constraint that either constrains index1 to be so that
860 * <code>index1=index2</code> or constrains index2 so that
861 * <code>index2=index1</code>.
862 */
863 bool
864 are_identity_constrained(const size_type line_n_1,
865 const size_type line_n_2) const;
866
867 /**
868 * Return the maximum number of other dofs that one dof is constrained to.
869 * For example, in 2d a hanging node is constrained only to its two
870 * neighbors, so the returned value would be 2. However, for higher order
871 * elements and/or higher dimensions, or other types of constraints, this
872 * number is no more obvious.
873 *
874 * The name indicates that within the system matrix, references to a
875 * constrained node are indirected to the nodes it is constrained to.
876 */
877 size_type
878 max_constraint_indirections() const;
879
880 /**
881 * Return <tt>true</tt> in case the dof is constrained and there is a non-
882 * trivial inhomogeneous values set to the dof.
883 */
884 bool
885 is_inhomogeneously_constrained(const size_type index) const;
886
887 /**
888 * Return <tt>false</tt> if all constraints in the AffineConstraints are
889 * homogeneous ones, and <tt>true</tt> if there is at least one
890 * inhomogeneity.
891 */
892 bool
893 has_inhomogeneities() const;
894
895 /**
896 * Return a pointer to the vector of entries if a line is constrained,
897 * and a zero pointer in case the dof is not constrained.
898 */
899 const std::vector<std::pair<size_type, number>> *
900 get_constraint_entries(const size_type line_n) const;
901
902 /**
903 * Return the value of the inhomogeneity stored in the constrained dof @p
904 * line_n. Unconstrained dofs also return a zero value.
905 */
906 number
907 get_inhomogeneity(const size_type line_n) const;
908
909 /**
910 * Print the constraints represented by the current object to the
911 * given stream.
912 *
913 * For each constraint of the form
914 * @f[
915 * x_{42} = 0.5 x_2 + 0.25 x_{14} + 2.75
916 * @f]
917 * this function will write a sequence of lines that look like this:
918 * @code
919 * 42 2 : 0.5
920 * 42 14 : 0.25
921 * 42 : 2.75
922 * @endcode
923 * The last line is only shown if the inhomogeneity (here: 2.75) is
924 * nonzero.
925 *
926 * A block of lines such as the one above is repeated for each
927 * constrained degree of freedom.
928 */
929 void
930 print(std::ostream &out) const;
931
932 /**
933 * Write the graph of constraints in 'dot' format. 'dot' is a program that
934 * can take a list of nodes and produce a graphical representation of the
935 * graph of constrained degrees of freedom and the degrees of freedom they
936 * are constrained to.
937 *
938 * The output of this function can be used as input to the 'dot' program
939 * that can convert the graph into a graphical representation in postscript,
940 * png, xfig, and a number of other formats.
941 *
942 * This function exists mostly for debugging purposes.
943 */
944 void
945 write_dot(std::ostream &) const;
946
947 /**
948 * Determine an estimate for the memory consumption (in bytes) of this
949 * object.
950 */
951 std::size_t
952 memory_consumption() const;
953
954 /**
955 * Add the constraint indices associated to the indices in the given vector.
956 * After a call to this function, the indices vector contains the initial
957 * elements and all the associated constrained indices. This function sorts
958 * the elements and suppresses duplicates.
959 */
960 void
961 resolve_indices(std::vector<types::global_dof_index> &indices) const;
962
963 /**
964 * @}
965 */
966
967 /**
968 * @name Eliminating constraints from linear systems after their creation
969 * @{
970 */
971
972 /**
973 * Condense a sparsity pattern. The name of the function mimics the name of
974 * the function we use to condense linear systems, but it is a bit of a
975 * misnomer for the current context. This is because in the context of
976 * linear systems, we eliminate certain rows and columns of the linear
977 * system, i.e., we "reduce" or "condense" the linear system. On the other
978 * hand, in the current context, the functions does not remove nonzero
979 * entries from the sparsity pattern. Rather, it adds those nonzero entry
980 * locations to the sparsity pattern that will later be needed for the
981 * process of condensation of constrained degrees of freedom from a linear
982 * system.
983 *
984 * Since this function adds new nonzero entries to the sparsity pattern, the
985 * given sparsity pattern must not be compressed. The current object must be
986 * closed. The sparsity pattern is compressed at the end of the function.
987 */
988 void
989 condense(SparsityPattern &sparsity) const;
990
991 /**
992 * Same function as above, but condenses square block sparsity patterns.
993 */
994 void
995 condense(BlockSparsityPattern &sparsity) const;
996
997 /**
998 * Same function as above, but condenses square compressed sparsity
999 * patterns.
1000 */
1001 void
1002 condense(DynamicSparsityPattern &sparsity) const;
1003
1004 /**
1005 * Same function as above, but condenses square compressed sparsity
1006 * patterns.
1007 */
1008 void
1009 condense(BlockDynamicSparsityPattern &sparsity) const;
1010
1011 /**
1012 * Condense a given matrix, i.e., eliminate the rows and columns of the
1013 * matrix that correspond to constrained degrees of freedom.
1014 *
1015 * See the general documentation of this class for more detailed
1016 * information.
1017 */
1018 void
1019 condense(SparseMatrix<number> &matrix) const;
1020
1021 /**
1022 * Same function as above, but condenses square block sparse matrices.
1023 */
1024 void
1025 condense(BlockSparseMatrix<number> &matrix) const;
1026
1027 /**
1028 * Condense the given vector in-place. The @p VectorType may be a
1029 * Vector<float>, Vector<number>, BlockVector<tt><...></tt>, a PETSc or
1030 * Trilinos vector wrapper class, or any other type having the same
1031 * interface. Note that this function does not take any inhomogeneity into
1032 * account and throws an exception in case there are any inhomogeneities.
1033 * Use the function using both a matrix and vector for that case.
1034 *
1035 * @note This function does not work for MPI vectors. Use condense() with
1036 * two vector arguments instead.
1037 */
1038 template <class VectorType>
1039 void
1040 condense(VectorType &vec) const;
1041
1042 /**
1043 * The function copies and condenses values from @p vec_ghosted into @p
1044 * output. In a serial code it is equivalent to calling condense (vec). If
1045 * called in parallel, @p vec_ghosted is supposed to contain ghost elements
1046 * while @p output should not.
1047 */
1048 template <class VectorType>
1049 void
1050 condense(const VectorType &vec_ghosted, VectorType &output) const;
1051
1052 /**
1053 * Condense a given matrix and a given vector by eliminating rows and
1054 * columns of the linear system that correspond to constrained degrees of
1055 * freedom. The sparsity pattern associated with the matrix needs to be
1056 * condensed and compressed. This function is the appropriate choice for
1057 * applying inhomogeneous constraints.
1058 *
1059 * The current object must be closed to call this function.
1060 *
1061 * See the general documentation of this class for more detailed
1062 * information.
1063 */
1064 template <class VectorType>
1065 void
1066 condense(SparseMatrix<number> &matrix, VectorType &vector) const;
1067
1068 /**
1069 * Same function as above, but condenses square block sparse matrices and
1070 * vectors.
1071 */
1072 template <class BlockVectorType>
1073 void
1074 condense(BlockSparseMatrix<number> &matrix, BlockVectorType &vector) const;
1075
1076 /**
1077 * Set the values of all constrained DoFs in a vector to zero. The @p
1078 * VectorType may be a Vector<float>, Vector<number>,
1079 * BlockVector<tt><...></tt>, a PETSc or Trilinos vector wrapper class, or
1080 * any other type having the same interface.
1081 */
1082 template <class VectorType>
1083 void
1084 set_zero(VectorType &vec) const;
1085
1086 /**
1087 * @}
1088 */
1089
1090 /**
1091 * @name Eliminating constraints from linear systems during their creation
1092 * @{
1093 */
1094
1095 /**
1096 * This function takes a vector of local contributions (@p local_vector)
1097 * corresponding to the degrees of freedom indices given in @p
1098 * local_dof_indices and distributes them to the global vector. In most
1099 * cases, these local contributions will be the result of an integration
1100 * over a cell or face of a cell. However, as long as @p local_vector and @p
1101 * local_dof_indices have the same number of elements, this function is
1102 * happy with whatever it is given.
1103 *
1104 * In contrast to the similar function in the DoFAccessor class, this
1105 * function also takes care of constraints, i.e. if one of the elements of
1106 * @p local_dof_indices belongs to a constrained node, then rather than
1107 * writing the corresponding element of @p local_vector into @p
1108 * global_vector, the element is distributed to the entries in the global
1109 * vector to which this particular degree of freedom is constrained.
1110 *
1111 * Thus, by using this function to distribute local contributions to the
1112 * global object, one saves the call to the condense function after the
1113 * vectors and matrices are fully assembled. On the other hand, by
1114 * consequence, the function does not only write into the entries enumerated
1115 * by the @p local_dof_indices array, but also (possibly) others as
1116 * necessary.
1117 *
1118 * Note that this function will apply all constraints as if they were
1119 * homogeneous. For correctly setting inhomogeneous constraints, use the
1120 * similar function with a matrix argument or the function with both matrix
1121 * and vector arguments.
1122 *
1123 * @note This function in itself is thread-safe, i.e., it works properly
1124 * also when several threads call it simultaneously. However, the function
1125 * call is only thread-safe if the underlying global vector allows for
1126 * simultaneous access and the access is not to rows with the same global
1127 * index at the same time. This needs to be made sure from the caller's
1128 * site. There is no locking mechanism inside this method to prevent data
1129 * races.
1130 *
1131 * @param[in] local_vector Vector of local contributions.
1132 * @param[in] local_dof_indices Local degrees of freedom indices
1133 * corresponding to the vector of local contributions.
1134 * @param[out] global_vector The global vector to which all local
1135 * contributions will be added.
1136 */
1137 template <class InVector, class OutVector>
1138 void
1139 distribute_local_to_global(const InVector & local_vector,
1140 const std::vector<size_type> &local_dof_indices,
1141 OutVector & global_vector) const;
1142
1143 /**
1144 * This function takes a vector of local contributions (@p local_vector)
1145 * corresponding to the degrees of freedom indices given in @p
1146 * local_dof_indices and distributes them to the global vector. In most
1147 * cases, these local contributions will be the result of an integration
1148 * over a cell or face of a cell. However, as long as @p local_vector and @p
1149 * local_dof_indices have the same number of elements, this function is
1150 * happy with whatever it is given.
1151 *
1152 * In contrast to the similar function in the DoFAccessor class, this
1153 * function also takes care of constraints, i.e. if one of the elements of
1154 * @p local_dof_indices belongs to a constrained node, then rather than
1155 * writing the corresponding element of @p local_vector into @p
1156 * global_vector, the element is distributed to the entries in the global
1157 * vector to which this particular degree of freedom is constrained.
1158 *
1159 * Thus, by using this function to distribute local contributions to the
1160 * global object, one saves the call to the condense function after the
1161 * vectors and matrices are fully assembled. On the other hand, by
1162 * consequence, the function does not only write into the entries enumerated
1163 * by the @p local_dof_indices array, but also (possibly) others as
1164 * necessary. This includes writing into diagonal elements of the matrix if
1165 * the corresponding degree of freedom is constrained.
1166 *
1167 * The fourth argument <tt>local_matrix</tt> is intended to be used in case
1168 * one wants to apply inhomogeneous constraints on the vector only. Such a
1169 * situation could be where one wants to assemble of a right hand side
1170 * vector on a problem with inhomogeneous constraints, but the global matrix
1171 * has been assembled previously. A typical example of this is a time
1172 * stepping algorithm where the stiffness matrix is assembled once, and the
1173 * right hand side updated every time step. Note that, however, the entries
1174 * in the columns of the local matrix have to be exactly the same as those
1175 * that have been written into the global matrix. Otherwise, this function
1176 * will not be able to correctly handle inhomogeneities.
1177 *
1178 * @note This function in itself is thread-safe, i.e., it works properly
1179 * also when several threads call it simultaneously. However, the function
1180 * call is only thread-safe if the underlying global vector allows for
1181 * simultaneous access and the access is not to rows with the same global
1182 * index at the same time. This needs to be made sure from the caller's
1183 * site. There is no locking mechanism inside this method to prevent data
1184 * races.
1185 */
1186 template <typename VectorType>
1187 void
1188 distribute_local_to_global(const Vector<number> & local_vector,
1189 const std::vector<size_type> &local_dof_indices,
1190 VectorType & global_vector,
1191 const FullMatrix<number> & local_matrix) const;
1192
1193 /**
1194 * Same as the previous function, except that it uses two (possibly) different
1195 * index sets to correctly handle inhomogeneities when the local matrix is
1196 * computed from a combination of two neighboring elements, for example for an
1197 * edge integral term in DG. Note that in the case that these two elements
1198 * have different polynomial degree, the local matrix is rectangular.
1199 *
1200 * <tt>local_dof_indices_row</tt> is the set of row indices and
1201 * <tt>local_dof_indices_col</tt> is the set of column indices of the local
1202 * matrix. <tt>diagonal=false</tt> says whether the two index sets are equal
1203 * or not.
1204 *
1205 * If both index sets are equal, <tt>diagonal</tt> must be set to true or we
1206 * simply use the previous function. If both index sets are different
1207 * (diagonal=false) the <tt>global_vector</tt> is modified to handle
1208 * inhomogeneities but no entries from <tt>local_vector</tt> are added. Note
1209 * that the edge integrals for inner edged for DG do not contribute any values
1210 * to the right hand side.
1211 */
1212 template <typename VectorType>
1213 void
1214 distribute_local_to_global(
1215 const Vector<number> & local_vector,
1216 const std::vector<size_type> &local_dof_indices_row,
1217 const std::vector<size_type> &local_dof_indices_col,
1218 VectorType & global_vector,
1219 const FullMatrix<number> & local_matrix,
1220 bool diagonal = false) const;
1221
1222 /**
1223 * Enter a single value into a result vector, obeying constraints.
1224 */
1225 template <class VectorType>
1226 void
1227 distribute_local_to_global(const size_type index,
1228 const number value,
1229 VectorType & global_vector) const;
1230
1231 /**
1232 * This function takes a pointer to a vector of local contributions (@p
1233 * local_vector) corresponding to the degrees of freedom indices given in @p
1234 * local_dof_indices and distributes them to the global vector. In most
1235 * cases, these local contributions will be the result of an integration
1236 * over a cell or face of a cell. However, as long as the entries in @p
1237 * local_dof_indices indicate reasonable global vector entries, this
1238 * function is happy with whatever it is given.
1239 *
1240 * If one of the elements of @p local_dof_indices belongs to a constrained
1241 * node, then rather than writing the corresponding element of @p
1242 * local_vector into @p global_vector, the element is distributed to the
1243 * entries in the global vector to which this particular degree of freedom
1244 * is constrained.
1245 *
1246 * Thus, by using this function to distribute local contributions to the
1247 * global object, one saves the call to the condense function after the
1248 * vectors and matrices are fully assembled. Note that this function
1249 * completely ignores inhomogeneous constraints.
1250 *
1251 * @note This function in itself is thread-safe, i.e., it works properly
1252 * also when several threads call it simultaneously. However, the function
1253 * call is only thread-safe if the underlying global vector allows for
1254 * simultaneous access and the access is not to rows with the same global
1255 * index at the same time. This needs to be made sure from the caller's
1256 * site. There is no locking mechanism inside this method to prevent data
1257 * races.
1258 */
1259 template <typename ForwardIteratorVec,
1260 typename ForwardIteratorInd,
1261 class VectorType>
1262 void
1263 distribute_local_to_global(ForwardIteratorVec local_vector_begin,
1264 ForwardIteratorVec local_vector_end,
1265 ForwardIteratorInd local_indices_begin,
1266 VectorType & global_vector) const;
1267
1268 /**
1269 * This function takes a matrix of local contributions (@p local_matrix)
1270 * corresponding to the degrees of freedom indices given in @p
1271 * local_dof_indices and distributes them to the global matrix. In most
1272 * cases, these local contributions will be the result of an integration
1273 * over a cell or face of a cell. However, as long as @p local_matrix and @p
1274 * local_dof_indices have the same number of elements, this function is
1275 * happy with whatever it is given.
1276 *
1277 * In contrast to the similar function in the DoFAccessor class, this
1278 * function also takes care of constraints, i.e. if one of the elements of
1279 * @p local_dof_indices belongs to a constrained node, then rather than
1280 * writing the corresponding element of @p local_matrix into @p
1281 * global_matrix, the element is distributed to the entries in the global
1282 * matrix to which this particular degree of freedom is constrained.
1283 *
1284 * With this scheme, we never write into rows or columns of constrained
1285 * degrees of freedom. In order to make sure that the resulting matrix can
1286 * still be inverted, we need to do something with the diagonal elements
1287 * corresponding to constrained nodes. Thus, if a degree of freedom in @p
1288 * local_dof_indices is constrained, we distribute the corresponding entries
1289 * in the matrix, but also add the absolute value of the diagonal entry of
1290 * the local matrix to the corresponding entry in the global matrix.
1291 * Assuming the discretized operator is positive definite, this guarantees
1292 * that the diagonal entry is always non-zero, positive, and of the same
1293 * order of magnitude as the other entries of the matrix. On the other hand,
1294 * when solving a source problem $Au=f$ the exact value of the diagonal
1295 * element is not important, since the value of the respective degree of
1296 * freedom will be overwritten by the distribute() call later on anyway.
1297 *
1298 * @note The procedure described above adds an unforeseeable number of
1299 * artificial eigenvalues to the spectrum of the matrix. Therefore, it is
1300 * recommended to use the equivalent function with two local index vectors
1301 * in such a case.
1302 *
1303 * By using this function to distribute local contributions to the global
1304 * object, one saves the call to the condense function after the vectors and
1305 * matrices are fully assembled.
1306 *
1307 * @note This function in itself is thread-safe, i.e., it works properly
1308 * also when several threads call it simultaneously. However, the function
1309 * call is only thread-safe if the underlying global matrix allows for
1310 * simultaneous access and the access is not to rows with the same global
1311 * index at the same time. This needs to be made sure from the caller's
1312 * site. There is no locking mechanism inside this method to prevent data
1313 * races.
1314 */
1315 template <typename MatrixType>
1316 void
1317 distribute_local_to_global(const FullMatrix<number> & local_matrix,
1318 const std::vector<size_type> &local_dof_indices,
1319 MatrixType & global_matrix) const;
1320
1321 /**
1322 * Does almost the same as the function above but can treat general
1323 * rectangular matrices. The main difference to achieve this is that the
1324 * diagonal entries in constrained rows are left untouched instead of being
1325 * filled with arbitrary values.
1326 *
1327 * Since the diagonal entries corresponding to eliminated degrees of freedom
1328 * are not set, the result may have a zero eigenvalue, if applied to a
1329 * square matrix. This has to be considered when solving the resulting
1330 * problems. For solving a source problem $Au=f$, it is possible to set the
1331 * diagonal entry after building the matrix by a piece of code of the form
1332 *
1333 * @code
1334 * for (unsigned int i=0;i<matrix.m();++i)
1335 * if (constraints.is_constrained(i))
1336 * matrix.diag_element(i) = 1.;
1337 * @endcode
1338 *
1339 * The value of one which is used here is arbitrary, but in the context of
1340 * Krylov space methods uncritical, since it corresponds to an invariant
1341 * subspace. If the other matrix entries are smaller or larger by a factor
1342 * close to machine accuracy, it may be advisable to adjust it.
1343 *
1344 * For solving eigenvalue problems, this will only add one spurious zero
1345 * eigenvalue (with a multiplicity that is possibly greater than one).
1346 * Taking this into account, nothing else has to be changed.
1347 */
1348 template <typename MatrixType>
1349 void
1350 distribute_local_to_global(const FullMatrix<number> & local_matrix,
1351 const std::vector<size_type> &row_indices,
1352 const std::vector<size_type> &col_indices,
1353 MatrixType & global_matrix) const;
1354
1355 /**
1356 * Does almost the same as the function above for general rectangular
1357 * matrices but uses different AffineConstraints objects on the row and
1358 * column indices. The convention is that row indices are constrained
1359 * according to the calling AffineConstraints <code>*this</code>, whereas
1360 * column indices are constrained according to the given AffineConstraints
1361 * <code>column_affine_constraints</code>. This function allows to handle the
1362 * case where rows and columns of a matrix are represented by different
1363 * function spaces with their own enumeration of indices, as e.g. in mixed
1364 * finite element problems with separate DoFHandler objects or for flux
1365 * matrices between different levels in multigrid methods.
1366 *
1367 * Like the other method with separate slots for row and column indices,
1368 * this method does not add diagonal entries to eliminated degrees of
1369 * freedom. See there for a more elaborate description.
1370 */
1371 template <typename MatrixType>
1372 void
1373 distribute_local_to_global(const FullMatrix<number> & local_matrix,
1374 const std::vector<size_type> &row_indices,
1375 const AffineConstraints &column_affine_constraints,
1376 const std::vector<size_type> &column_indices,
1377 MatrixType & global_matrix) const;
1378
1379 /**
1380 * This function simultaneously writes elements into matrix and vector,
1381 * according to the constraints specified by the calling AffineConstraints.
1382 * This function can correctly handle inhomogeneous constraints as well. For
1383 * the parameter use_inhomogeneities_for_rhs see the documentation in
1384 * @ref constraints
1385 * module.
1386 *
1387 * @note This function in itself is thread-safe, i.e., it works properly
1388 * also when several threads call it simultaneously. However, the function
1389 * call is only thread-safe if the underlying global matrix and vector allow
1390 * for simultaneous access and the access is not to rows with the same
1391 * global index at the same time. This needs to be made sure from the
1392 * caller's site. There is no locking mechanism inside this method to
1393 * prevent data races.
1394 */
1395 template <typename MatrixType, typename VectorType>
1396 void
1397 distribute_local_to_global(const FullMatrix<number> & local_matrix,
1398 const Vector<number> & local_vector,
1399 const std::vector<size_type> &local_dof_indices,
1400 MatrixType & global_matrix,
1401 VectorType & global_vector,
1402 bool use_inhomogeneities_for_rhs = false) const;
1403
1404 /**
1405 * Do a similar operation as the distribute_local_to_global() function that
1406 * distributes writing entries into a matrix for constrained degrees of
1407 * freedom, except that here we don't write into a matrix but only allocate
1408 * sparsity pattern entries.
1409 *
1410 * As explained in the
1411 * @ref hp_paper "hp paper"
1412 * and in step-27, first allocating a sparsity pattern and later coming back
1413 * and allocating additional entries for those matrix entries that will be
1414 * written to due to the elimination of constrained degrees of freedom
1415 * (using AffineConstraints::condense() ), can be a very expensive procedure.
1416 * It is cheaper to allocate these entries right away without having to do a
1417 * second pass over the sparsity pattern object. This function does exactly
1418 * that.
1419 *
1420 * Because the function only allocates entries in a sparsity pattern, all it
1421 * needs to know are the degrees of freedom that couple to each other.
1422 * Unlike the previous function, no actual values are written, so the second
1423 * input argument is not necessary here.
1424 *
1425 * The third argument to this function, keep_constrained_entries determines
1426 * whether the function shall allocate entries in the sparsity pattern at
1427 * all for entries that will later be set to zero upon condensation of the
1428 * matrix. These entries are necessary if the matrix is built unconstrained,
1429 * and only later condensed. They are not necessary if the matrix is built
1430 * using the distribute_local_to_global() function of this class which
1431 * distributes entries right away when copying a local matrix into a global
1432 * object. The default of this argument is true, meaning to allocate the few
1433 * entries that may later be set to zero.
1434 *
1435 * By default, the function adds entries for all pairs of indices given in
1436 * the first argument to the sparsity pattern (unless
1437 * keep_constrained_entries is false). However, sometimes one would like to
1438 * only add a subset of all of these pairs. In that case, the last argument
1439 * can be used which specifies a boolean mask which of the pairs of indices
1440 * should be considered. If the mask is false for a pair of indices, then no
1441 * entry will be added to the sparsity pattern for this pair, irrespective
1442 * of whether one or both of the indices correspond to constrained degrees
1443 * of freedom.
1444 *
1445 * This function is not typically called from user code, but is used in the
1446 * DoFTools::make_sparsity_pattern() function when passed an
1447 * AffineConstraints object.
1448 *
1449 * @note This function in itself is thread-safe, i.e., it works properly
1450 * also when several threads call it simultaneously. However, the function
1451 * call is only thread-safe if the underlying global sparsity pattern allows
1452 * for simultaneous access and the access is not to rows with the same
1453 * global index at the same time. This needs to be made sure from the
1454 * caller's site. There is no locking mechanism inside this method to
1455 * prevent data races.
1456 */
1457 template <typename SparsityPatternType>
1458 void
1459 add_entries_local_to_global(
1460 const std::vector<size_type> &local_dof_indices,
1461 SparsityPatternType & sparsity_pattern,
1462 const bool keep_constrained_entries = true,
1463 const Table<2, bool> & dof_mask = Table<2, bool>()) const;
1464
1465 /**
1466 * Similar to the other function, but for non-quadratic sparsity patterns.
1467 */
1468 template <typename SparsityPatternType>
1469 void
1470 add_entries_local_to_global(
1471 const std::vector<size_type> &row_indices,
1472 const std::vector<size_type> &col_indices,
1473 SparsityPatternType & sparsity_pattern,
1474 const bool keep_constrained_entries = true,
1475 const Table<2, bool> & dof_mask = Table<2, bool>()) const;
1476
1477 /**
1478 * This function imports values from a global vector (@p global_vector) by
1479 * applying the constraints to a vector of local values, expressed in
1480 * iterator format. In most cases, the local values will be identified by
1481 * the local dof values on a cell. However, as long as the entries in @p
1482 * local_dof_indices indicate reasonable global vector entries, this
1483 * function is happy with whatever it is given.
1484 *
1485 * If one of the elements of @p local_dof_indices belongs to a constrained
1486 * node, then rather than writing the corresponding element of @p
1487 * global_vector into @p local_vector, the constraints are resolved as the
1488 * respective distribute function does, i.e., the local entry is constructed
1489 * from the global entries to which this particular degree of freedom is
1490 * constrained.
1491 *
1492 * In contrast to the similar function get_dof_values in the DoFAccessor
1493 * class, this function does not need the constrained values to be correctly
1494 * set (i.e., distribute to be called).
1495 */
1496 template <typename ForwardIteratorVec,
1497 typename ForwardIteratorInd,
1498 class VectorType>
1499 void
1500 get_dof_values(const VectorType & global_vector,
1501 ForwardIteratorInd local_indices_begin,
1502 ForwardIteratorVec local_vector_begin,
1503 ForwardIteratorVec local_vector_end) const;
1504
1505 /**
1506 * @}
1507 */
1508
1509 /**
1510 * @name Dealing with constraints after solving a linear system
1511 * @{
1512 */
1513
1514 /**
1515 * Given a vector, set all constrained degrees of freedom to values so
1516 * that the constraints are satisfied. For example, if the current object
1517 * stores the constraint $x_3=\frac 12 x_1 + \frac 12 x_2$, then this
1518 * function will read the values of $x_1$ and $x_2$ from the given vector
1519 * and set the element $x_3$ according to this constraints. Similarly, if
1520 * the current object stores the constraint $x_{42}=208$, then this
1521 * function will set the 42nd element of the given vector to 208.
1522 *
1523 * @note If this function is called with a parallel vector @p vec, then the
1524 * vector must not contain ghost elements.
1525 */
1526 template <class VectorType>
1527 void
1528 distribute(VectorType &vec) const;
1529
1530 /**
1531 * @}
1532 */
1533
1534 /**
1535 * This class represents one constraint in an AffineConstraints object.
1536 */
1537 struct ConstraintLine
1538 {
1539 /**
1540 * A data type in which we store the list of entries that make up the
1541 * homogeneous part of a constraint.
1542 */
1543 using Entries = std::vector<std::pair<size_type, number>>;
1544
1545 /**
1546 * Global DoF index of this line. Since only very few lines are stored,
1547 * we can not assume a specific order and have to store the index
1548 * explicitly.
1549 */
1550 size_type index;
1551
1552 /**
1553 * Row numbers and values of the entries in this line.
1554 *
1555 * For the reason why we use a vector instead of a map and the
1556 * consequences thereof, the same applies as what is said for
1557 * AffineConstraints::lines.
1558 */
1559 Entries entries;
1560
1561 /**
1562 * Value of the inhomogeneity.
1563 */
1564 number inhomogeneity;
1565
1566 /**
1567 * This operator is a bit weird and unintuitive: it compares the line
1568 * numbers of two lines. We need this to sort the lines; in fact we could
1569 * do this using a comparison predicate. However, this way, it is easier,
1570 * albeit unintuitive since two lines really have no god-given order
1571 * relation.
1572 */
1573 bool
1574 operator<(const ConstraintLine &) const;
1575
1576 /**
1577 * This operator is likewise weird: it checks whether the line indices of
1578 * the two operands are equal, irrespective of the fact that the contents
1579 * of the line may be different.
1580 */
1581 bool
1582 operator==(const ConstraintLine &) const;
1583
1584 /**
1585 * Determine an estimate for the memory consumption (in bytes) of this
1586 * object.
1587 */
1588 std::size_t
1589 memory_consumption() const;
1590
1591 /**
1592 * Support for boost:serialization.
1593 */
1594 template <class Archive>
1595 void
serializeConstraintLine1596 serialize(Archive &ar, const unsigned int)
1597 {
1598 ar &index &entries &inhomogeneity;
1599 }
1600 };
1601
1602 /**
1603 * Alias for the iterator type that is used in the LineRange container.
1604 */
1605 using const_iterator = typename std::vector<ConstraintLine>::const_iterator;
1606
1607 /**
1608 * Alias for the return type used by get_lines().
1609 */
1610 using LineRange = boost::iterator_range<const_iterator>;
1611
1612 /**
1613 * Return a range object containing (const) iterators to all line entries
1614 * stored in the AffineConstraints container. Such a range is useful to
1615 * initialize range-based for loops as supported by C++11.
1616 *
1617 * @return A range object for the half open range <code>[this->begin(),
1618 * this->end())</code> of line entries.
1619 */
1620 const LineRange
1621 get_lines() const;
1622
1623 /**
1624 * Check if the current object is consistent on all processors
1625 * in a distributed computation.
1626 *
1627 * This method checks if all processors agree on the constraints for their
1628 * local lines as given by @p locally_active_dofs. This method is a collective
1629 * operation and will return @p true only if all processors are consistent.
1630 *
1631 * Please supply the owned DoFs per processor as returned by
1632 * DoFHandler::locally_owned_dofs_per_processor() as @p locally_owned_dofs
1633 * and the result of DoFTools::extract_locally_active_dofs() as
1634 * @p locally_active_dofs. The
1635 * former is used to determine ownership of the specific DoF, while the latter
1636 * is used as the set of rows that need to be checked.
1637 *
1638 * If @p verbose is set to @p true, additional debug information is written
1639 * to std::cout.
1640 *
1641 * @note This method exchanges all constraint information of locally active
1642 * lines and is as such slow for large computations and should probably
1643 * only be used in debug mode. We do not check all lines returned by
1644 * get_local_lines() but only the locally active ones, as we allow processors
1645 * to not know about some locally relevant rows.
1646 *
1647 * @return Whether all AffineConstraints objects are consistent. Returns
1648 * the same value on all processors.
1649 */
1650 bool
1651 is_consistent_in_parallel(const std::vector<IndexSet> &locally_owned_dofs,
1652 const IndexSet & locally_active_dofs,
1653 const MPI_Comm mpi_communicator,
1654 const bool verbose = false) const;
1655
1656 /**
1657 * Exception
1658 *
1659 * @ingroup Exceptions
1660 */
1661 DeclException0(ExcMatrixIsClosed);
1662 /**
1663 * Exception
1664 *
1665 * @ingroup Exceptions
1666 */
1667 DeclException0(ExcMatrixNotClosed);
1668 /**
1669 * Exception
1670 *
1671 * @ingroup Exceptions
1672 */
1673 DeclException1(ExcLineInexistant,
1674 size_type,
1675 << "The specified line " << arg1 << " does not exist.");
1676 /**
1677 * Exception
1678 *
1679 * @ingroup Exceptions
1680 */
1681 DeclException4(ExcEntryAlreadyExists,
1682 size_type,
1683 size_type,
1684 number,
1685 number,
1686 << "The entry for the indices " << arg1 << " and " << arg2
1687 << " already exists, but the values " << arg3 << " (old) and "
1688 << arg4 << " (new) differ "
1689 << "by " << (arg4 - arg3) << ".");
1690 /**
1691 * Exception
1692 *
1693 * @ingroup Exceptions
1694 */
1695 DeclException2(ExcDoFConstrainedToConstrainedDoF,
1696 int,
1697 int,
1698 << "You tried to constrain DoF " << arg1 << " to DoF " << arg2
1699 << ", but that one is also constrained. This is not allowed!");
1700 /**
1701 * Exception.
1702 *
1703 * @ingroup Exceptions
1704 */
1705 DeclException1(ExcDoFIsConstrainedFromBothObjects,
1706 size_type,
1707 << "Degree of freedom " << arg1
1708 << " is constrained from both object in a merge operation.");
1709 /**
1710 * Exception
1711 *
1712 * @ingroup Exceptions
1713 */
1714 DeclException1(ExcDoFIsConstrainedToConstrainedDoF,
1715 size_type,
1716 << "In the given argument a degree of freedom is constrained "
1717 << "to another DoF with number " << arg1
1718 << ", which however is constrained by this object. This is not"
1719 << " allowed.");
1720 /**
1721 * Exception
1722 *
1723 * @ingroup Exceptions
1724 */
1725 DeclException1(ExcRowNotStoredHere,
1726 size_type,
1727 << "The index set given to this constraints object indicates "
1728 << "constraints for degree of freedom " << arg1
1729 << " should not be stored by this object, but a constraint "
1730 << "is being added.");
1731
1732 /**
1733 * Exception
1734 *
1735 * @ingroup Exceptions
1736 */
1737 DeclException2(ExcColumnNotStoredHere,
1738 size_type,
1739 size_type,
1740 << "The index set given to this constraints object indicates "
1741 << "constraints using degree of freedom " << arg2
1742 << " should not be stored by this object, but a constraint "
1743 << "for degree of freedom " << arg1 << " uses it.");
1744
1745 /**
1746 * Exception
1747 *
1748 * @ingroup Exceptions
1749 */
1750 DeclException2(ExcIncorrectConstraint,
1751 int,
1752 int,
1753 << "While distributing the constraint for DoF " << arg1
1754 << ", it turns out that one of the processors "
1755 << "who own the " << arg2 << " degrees of freedom that x_"
1756 << arg1 << " is constrained against does not know about "
1757 << "the constraint on x_" << arg1
1758 << ". Did you not initialize the AffineConstraints container "
1759 << "with the appropriate locally_relevant set so "
1760 << "that every processor who owns a DoF that constrains "
1761 << "another DoF also knows about this constraint?");
1762
1763 private:
1764 /**
1765 * Store the lines of the matrix. Entries are usually appended in an
1766 * arbitrary order and insertion into a vector is done best at the end, so
1767 * the order is unspecified after all entries are inserted. Sorting of the
1768 * entries takes place when calling the <tt>close()</tt> function.
1769 *
1770 * We could, instead of using a vector, use an associative array, like a map
1771 * to store the lines. This, however, would mean a much more fragmented heap
1772 * since it allocates many small objects, and would additionally make usage
1773 * of this matrix much slower.
1774 */
1775 std::vector<ConstraintLine> lines;
1776
1777 /**
1778 * A list of size_type that contains the position of the ConstraintLine of a
1779 * constrained degree of freedom, or numbers::invalid_size_type if the
1780 * degree of freedom is not constrained. The numbers::invalid_size_type
1781 * return value returns thus whether there is a constraint line for a given
1782 * degree of freedom index. Note that this class has no notion of how many
1783 * degrees of freedom there really are, so if we check whether there is a
1784 * constraint line for a given degree of freedom, then this vector may
1785 * actually be shorter than the index of the DoF we check for.
1786 *
1787 * This field exists since when adding a new constraint line we have to
1788 * figure out whether it already exists. Previously, we would simply walk
1789 * the unsorted list of constraint lines until we either hit the end or
1790 * found it. This algorithm is O(N) if N is the number of constraints, which
1791 * makes it O(N^2) when inserting all constraints. For large problems with
1792 * many constraints, this could easily take 5-10 per cent of the total run
1793 * time. With this field, we can save this time since we find any constraint
1794 * in O(1) time or get to know that it a certain degree of freedom is not
1795 * constrained.
1796 *
1797 * To make things worse, traversing the list of existing constraints
1798 * requires reads from many different places in memory. Thus, in large 3d
1799 * applications, the add_line() function showed up very prominently in the
1800 * overall compute time, mainly because it generated a lot of cache misses.
1801 * This should also be fixed by using the O(1) algorithm to access the
1802 * fields of this array.
1803 *
1804 * The field is useful in a number of other contexts as well, e.g. when one
1805 * needs random access to the constraints as in all the functions that apply
1806 * constraints on the fly while add cell contributions into vectors and
1807 * matrices.
1808 */
1809 std::vector<size_type> lines_cache;
1810
1811 /**
1812 * This IndexSet is used to limit the lines to save in the AffineConstraints
1813 * to a subset. This is necessary, because the lines_cache vector would
1814 * become too big in a distributed calculation.
1815 */
1816 IndexSet local_lines;
1817
1818 /**
1819 * Store whether the arrays are sorted. If so, no new entries can be added.
1820 */
1821 bool sorted;
1822
1823 mutable Threads::ThreadLocalStorage<
1824 internal::AffineConstraints::ScratchData<number>>
1825 scratch_data;
1826
1827 /**
1828 * Internal function to calculate the index of line @p line_n in the vector
1829 * lines_cache using local_lines.
1830 */
1831 size_type
1832 calculate_line_index(const size_type line_n) const;
1833
1834 /**
1835 * This function actually implements the local_to_global function for
1836 * standard (non-block) matrices.
1837 */
1838 template <typename MatrixType, typename VectorType>
1839 void
1840 distribute_local_to_global(const FullMatrix<number> & local_matrix,
1841 const Vector<number> & local_vector,
1842 const std::vector<size_type> &local_dof_indices,
1843 MatrixType & global_matrix,
1844 VectorType & global_vector,
1845 bool use_inhomogeneities_for_rhs,
1846 std::integral_constant<bool, false>) const;
1847
1848 /**
1849 * This function actually implements the local_to_global function for block
1850 * matrices.
1851 */
1852 template <typename MatrixType, typename VectorType>
1853 void
1854 distribute_local_to_global(const FullMatrix<number> & local_matrix,
1855 const Vector<number> & local_vector,
1856 const std::vector<size_type> &local_dof_indices,
1857 MatrixType & global_matrix,
1858 VectorType & global_vector,
1859 bool use_inhomogeneities_for_rhs,
1860 std::integral_constant<bool, true>) const;
1861
1862 /**
1863 * This function actually implements the local_to_global function for
1864 * standard (non-block) sparsity types.
1865 */
1866 template <typename SparsityPatternType>
1867 void
1868 add_entries_local_to_global(const std::vector<size_type> &local_dof_indices,
1869 SparsityPatternType & sparsity_pattern,
1870 const bool keep_constrained_entries,
1871 const Table<2, bool> &dof_mask,
1872 std::integral_constant<bool, false>) const;
1873
1874 /**
1875 * This function actually implements the local_to_global function for block
1876 * sparsity types.
1877 */
1878 template <typename SparsityPatternType>
1879 void
1880 add_entries_local_to_global(const std::vector<size_type> &local_dof_indices,
1881 SparsityPatternType & sparsity_pattern,
1882 const bool keep_constrained_entries,
1883 const Table<2, bool> &dof_mask,
1884 std::integral_constant<bool, true>) const;
1885
1886 /**
1887 * Internal helper function for distribute_local_to_global function.
1888 *
1889 * Creates a list of affected global rows for distribution, including the
1890 * local rows where the entries come from. The list is sorted according to
1891 * the global row indices.
1892 */
1893 void
1894 make_sorted_row_list(const std::vector<size_type> &local_dof_indices,
1895 internal::AffineConstraints::GlobalRowsFromLocal<number>
1896 &global_rows) const;
1897
1898 /**
1899 * Internal helper function for add_entries_local_to_global function.
1900 *
1901 * Creates a list of affected rows for distribution without any additional
1902 * information, otherwise similar to the other make_sorted_row_list()
1903 * function.
1904 */
1905 void
1906 make_sorted_row_list(const std::vector<size_type> &local_dof_indices,
1907 std::vector<size_type> & active_dofs) const;
1908
1909 /**
1910 * Internal helper function for distribute_local_to_global function.
1911 */
1912 template <typename MatrixScalar, typename VectorScalar>
1913 typename ProductType<VectorScalar, MatrixScalar>::type
1914 resolve_vector_entry(
1915 const size_type i,
1916 const internal::AffineConstraints::GlobalRowsFromLocal<number> &global_rows,
1917 const Vector<VectorScalar> & local_vector,
1918 const std::vector<size_type> & local_dof_indices,
1919 const FullMatrix<MatrixScalar> &local_matrix) const;
1920 };
1921
1922 /* ---------------- template and inline functions ----------------- */
1923
1924 template <typename number>
AffineConstraints(const IndexSet & local_constraints)1925 inline AffineConstraints<number>::AffineConstraints(
1926 const IndexSet &local_constraints)
1927 : lines()
1928 , local_lines(local_constraints)
1929 , sorted(false)
1930 {
1931 // make sure the IndexSet is compressed. Otherwise this can lead to crashes
1932 // that are hard to find (only happen in release mode).
1933 // see tests/mpi/affine_constraints_crash_01
1934 local_lines.compress();
1935 }
1936
1937 template <typename number>
AffineConstraints(const AffineConstraints & affine_constraints)1938 inline AffineConstraints<number>::AffineConstraints(
1939 const AffineConstraints &affine_constraints)
1940 : Subscriptor()
1941 , lines(affine_constraints.lines)
1942 , lines_cache(affine_constraints.lines_cache)
1943 , local_lines(affine_constraints.local_lines)
1944 , sorted(affine_constraints.sorted)
1945 {}
1946
1947 template <typename number>
1948 inline void
add_line(const size_type line_n)1949 AffineConstraints<number>::add_line(const size_type line_n)
1950 {
1951 Assert(sorted == false, ExcMatrixIsClosed());
1952
1953 // the following can happen when we compute with distributed meshes and dof
1954 // handlers and we constrain a degree of freedom whose number we don't have
1955 // locally. if we don't abort here the program will try to allocate several
1956 // terabytes of memory to resize the various arrays below :-)
1957 Assert(line_n != numbers::invalid_size_type, ExcInternalError());
1958 const size_type line_index = calculate_line_index(line_n);
1959
1960 // check whether line already exists; it may, in which case we can just quit
1961 if (is_constrained(line_n))
1962 return;
1963
1964 // if necessary enlarge vector of existing entries for cache
1965 if (line_index >= lines_cache.size())
1966 lines_cache.resize(std::max(2 * static_cast<size_type>(lines_cache.size()),
1967 line_index + 1),
1968 numbers::invalid_size_type);
1969
1970 // push a new line to the end of the list
1971 lines.emplace_back();
1972 lines.back().index = line_n;
1973 lines.back().inhomogeneity = 0.;
1974 lines_cache[line_index] = lines.size() - 1;
1975 }
1976
1977 template <typename number>
1978 inline void
add_entry(const size_type line_n,const size_type column,const number value)1979 AffineConstraints<number>::add_entry(const size_type line_n,
1980 const size_type column,
1981 const number value)
1982 {
1983 Assert(sorted == false, ExcMatrixIsClosed());
1984 Assert(line_n != column,
1985 ExcMessage("Can't constrain a degree of freedom to itself"));
1986
1987 // Ensure that the current line is present in the cache:
1988 const size_type line_index = calculate_line_index(line_n);
1989 Assert(line_index < lines_cache.size(),
1990 ExcMessage("The current AffineConstraints does not contain the line "
1991 "for the current entry. Call AffineConstraints::add_line "
1992 "before calling this function."));
1993
1994 // if in debug mode, check whether an entry for this column already exists
1995 // and if it's the same as the one entered at present
1996 //
1997 // in any case: exit the function if an entry for this column already
1998 // exists, since we don't want to enter it twice
1999 Assert(lines_cache[line_index] != numbers::invalid_size_type,
2000 ExcInternalError());
2001 Assert(!local_lines.size() || local_lines.is_element(column),
2002 ExcColumnNotStoredHere(line_n, column));
2003 ConstraintLine *line_ptr = &lines[lines_cache[line_index]];
2004 Assert(line_ptr->index == line_n, ExcInternalError());
2005 for (const auto &p : line_ptr->entries)
2006 if (p.first == column)
2007 {
2008 Assert(std::abs(p.second - value) < 1.e-14,
2009 ExcEntryAlreadyExists(line_n, column, p.second, value));
2010 return;
2011 }
2012
2013 line_ptr->entries.emplace_back(column, value);
2014 }
2015
2016 template <typename number>
2017 inline void
set_inhomogeneity(const size_type line_n,const number value)2018 AffineConstraints<number>::set_inhomogeneity(const size_type line_n,
2019 const number value)
2020 {
2021 const size_type line_index = calculate_line_index(line_n);
2022 Assert(line_index < lines_cache.size() &&
2023 lines_cache[line_index] != numbers::invalid_size_type,
2024 ExcMessage("call add_line() before calling set_inhomogeneity()"));
2025 Assert(lines_cache[line_index] < lines.size(), ExcInternalError());
2026 ConstraintLine *line_ptr = &lines[lines_cache[line_index]];
2027 line_ptr->inhomogeneity = value;
2028 }
2029
2030 template <typename number>
2031 template <class VectorType>
2032 inline void
set_zero(VectorType & vec)2033 AffineConstraints<number>::set_zero(VectorType &vec) const
2034 {
2035 // since lines is a private member, we cannot pass it to the functions
2036 // above. therefore, copy the content which is cheap
2037 std::vector<size_type> constrained_lines(lines.size());
2038 for (unsigned int i = 0; i < lines.size(); ++i)
2039 constrained_lines[i] = lines[i].index;
2040 internal::AffineConstraintsImplementation::set_zero_all(constrained_lines,
2041 vec);
2042 }
2043
2044 template <typename number>
2045 inline types::global_dof_index
n_constraints()2046 AffineConstraints<number>::n_constraints() const
2047 {
2048 return lines.size();
2049 }
2050
2051 template <typename number>
2052 inline bool
is_constrained(const size_type index)2053 AffineConstraints<number>::is_constrained(const size_type index) const
2054 {
2055 const size_type line_index = calculate_line_index(index);
2056 return ((line_index < lines_cache.size()) &&
2057 (lines_cache[line_index] != numbers::invalid_size_type));
2058 }
2059
2060 template <typename number>
2061 inline bool
is_inhomogeneously_constrained(const size_type line_n)2062 AffineConstraints<number>::is_inhomogeneously_constrained(
2063 const size_type line_n) const
2064 {
2065 // check whether the entry is constrained. could use is_constrained, but
2066 // that means computing the line index twice
2067 const size_type line_index = calculate_line_index(line_n);
2068 if (line_index >= lines_cache.size() ||
2069 lines_cache[line_index] == numbers::invalid_size_type)
2070 return false;
2071 else
2072 {
2073 Assert(lines_cache[line_index] < lines.size(), ExcInternalError());
2074 return !(lines[lines_cache[line_index]].inhomogeneity == number(0.));
2075 }
2076 }
2077
2078 template <typename number>
2079 inline const std::vector<std::pair<types::global_dof_index, number>> *
get_constraint_entries(const size_type line_n)2080 AffineConstraints<number>::get_constraint_entries(const size_type line_n) const
2081 {
2082 // check whether the entry is constrained. could use is_constrained, but
2083 // that means computing the line index twice
2084 const size_type line_index = calculate_line_index(line_n);
2085 if (line_index >= lines_cache.size() ||
2086 lines_cache[line_index] == numbers::invalid_size_type)
2087 return nullptr;
2088 else
2089 return &lines[lines_cache[line_index]].entries;
2090 }
2091
2092 template <typename number>
2093 inline number
get_inhomogeneity(const size_type line_n)2094 AffineConstraints<number>::get_inhomogeneity(const size_type line_n) const
2095 {
2096 // check whether the entry is constrained. could use is_constrained, but
2097 // that means computing the line index twice
2098 const size_type line_index = calculate_line_index(line_n);
2099 if (line_index >= lines_cache.size() ||
2100 lines_cache[line_index] == numbers::invalid_size_type)
2101 return 0;
2102 else
2103 return lines[lines_cache[line_index]].inhomogeneity;
2104 }
2105
2106 template <typename number>
2107 inline types::global_dof_index
calculate_line_index(const size_type line_n)2108 AffineConstraints<number>::calculate_line_index(const size_type line_n) const
2109 {
2110 // IndexSet is unused (serial case)
2111 if (!local_lines.size())
2112 return line_n;
2113
2114 Assert(local_lines.is_element(line_n), ExcRowNotStoredHere(line_n));
2115
2116 return local_lines.index_within_set(line_n);
2117 }
2118
2119 template <typename number>
2120 inline bool
can_store_line(size_type line_n)2121 AffineConstraints<number>::can_store_line(size_type line_n) const
2122 {
2123 return !local_lines.size() || local_lines.is_element(line_n);
2124 }
2125
2126 template <typename number>
2127 inline const IndexSet &
get_local_lines()2128 AffineConstraints<number>::get_local_lines() const
2129 {
2130 return local_lines;
2131 }
2132
2133 template <typename number>
2134 template <class VectorType>
2135 inline void
distribute_local_to_global(const size_type index,const number value,VectorType & global_vector)2136 AffineConstraints<number>::distribute_local_to_global(
2137 const size_type index,
2138 const number value,
2139 VectorType & global_vector) const
2140 {
2141 Assert(lines.empty() || sorted == true, ExcMatrixNotClosed());
2142
2143 if (is_constrained(index) == false)
2144 global_vector(index) += value;
2145 else
2146 {
2147 const ConstraintLine &position =
2148 lines[lines_cache[calculate_line_index(index)]];
2149 for (size_type j = 0; j < position.entries.size(); ++j)
2150 global_vector(position.entries[j].first) +=
2151 value * position.entries[j].second;
2152 }
2153 }
2154
2155 template <typename number>
2156 template <typename ForwardIteratorVec,
2157 typename ForwardIteratorInd,
2158 class VectorType>
2159 inline void
distribute_local_to_global(ForwardIteratorVec local_vector_begin,ForwardIteratorVec local_vector_end,ForwardIteratorInd local_indices_begin,VectorType & global_vector)2160 AffineConstraints<number>::distribute_local_to_global(
2161 ForwardIteratorVec local_vector_begin,
2162 ForwardIteratorVec local_vector_end,
2163 ForwardIteratorInd local_indices_begin,
2164 VectorType & global_vector) const
2165 {
2166 Assert(lines.empty() || sorted == true, ExcMatrixNotClosed());
2167 for (; local_vector_begin != local_vector_end;
2168 ++local_vector_begin, ++local_indices_begin)
2169 {
2170 if (is_constrained(*local_indices_begin) == false)
2171 internal::ElementAccess<VectorType>::add(*local_vector_begin,
2172 *local_indices_begin,
2173 global_vector);
2174 else
2175 {
2176 const ConstraintLine &position =
2177 lines[lines_cache[calculate_line_index(*local_indices_begin)]];
2178 for (size_type j = 0; j < position.entries.size(); ++j)
2179 internal::ElementAccess<VectorType>::add(
2180 (*local_vector_begin) * position.entries[j].second,
2181 position.entries[j].first,
2182 global_vector);
2183 }
2184 }
2185 }
2186
2187 template <typename number>
2188 template <class InVector, class OutVector>
2189 inline void
distribute_local_to_global(const InVector & local_vector,const std::vector<size_type> & local_dof_indices,OutVector & global_vector)2190 AffineConstraints<number>::distribute_local_to_global(
2191 const InVector & local_vector,
2192 const std::vector<size_type> &local_dof_indices,
2193 OutVector & global_vector) const
2194 {
2195 Assert(local_vector.size() == local_dof_indices.size(),
2196 ExcDimensionMismatch(local_vector.size(), local_dof_indices.size()));
2197 distribute_local_to_global(local_vector.begin(),
2198 local_vector.end(),
2199 local_dof_indices.begin(),
2200 global_vector);
2201 }
2202
2203 template <typename number>
2204 template <typename ForwardIteratorVec,
2205 typename ForwardIteratorInd,
2206 class VectorType>
2207 inline void
get_dof_values(const VectorType & global_vector,ForwardIteratorInd local_indices_begin,ForwardIteratorVec local_vector_begin,ForwardIteratorVec local_vector_end)2208 AffineConstraints<number>::get_dof_values(
2209 const VectorType & global_vector,
2210 ForwardIteratorInd local_indices_begin,
2211 ForwardIteratorVec local_vector_begin,
2212 ForwardIteratorVec local_vector_end) const
2213 {
2214 Assert(lines.empty() || sorted == true, ExcMatrixNotClosed());
2215 for (; local_vector_begin != local_vector_end;
2216 ++local_vector_begin, ++local_indices_begin)
2217 {
2218 if (is_constrained(*local_indices_begin) == false)
2219 *local_vector_begin = global_vector(*local_indices_begin);
2220 else
2221 {
2222 const ConstraintLine &position =
2223 lines[lines_cache[calculate_line_index(*local_indices_begin)]];
2224 typename VectorType::value_type value = position.inhomogeneity;
2225 for (size_type j = 0; j < position.entries.size(); ++j)
2226 value += (global_vector(position.entries[j].first) *
2227 position.entries[j].second);
2228 *local_vector_begin = value;
2229 }
2230 }
2231 }
2232
2233 template <typename MatrixType>
2234 class BlockMatrixBase;
2235 template <typename SparsityPatternType>
2236 class BlockSparsityPatternBase;
2237 template <typename number>
2238 class BlockSparseMatrixEZ;
2239
2240 /**
2241 * A class that can be used to determine whether a given type is a block
2242 * matrix type or not. For example,
2243 * @code
2244 * IsBlockMatrix<SparseMatrix<number> >::value
2245 * @endcode
2246 * has the value false, whereas
2247 * @code
2248 * IsBlockMatrix<BlockSparseMatrix<number> >::value
2249 * @endcode
2250 * is true. This is sometimes useful in template contexts where we may want to
2251 * do things differently depending on whether a template type denotes a
2252 * regular or a block matrix type.
2253 *
2254 * @see
2255 * @ref GlossBlockLA "Block (linear algebra)"
2256 */
2257 template <typename MatrixType>
2258 struct IsBlockMatrix
2259 {
2260 private:
2261 struct yes_type
2262 {
2263 char c[1];
2264 };
2265 struct no_type
2266 {
2267 char c[2];
2268 };
2269
2270 /**
2271 * Overload returning true if the class is derived from BlockMatrixBase,
2272 * which is what block matrices do (with the exception of
2273 * BlockSparseMatrixEZ).
2274 */
2275 template <typename T>
2276 static yes_type
2277 check_for_block_matrix(const BlockMatrixBase<T> *);
2278
2279 /**
2280 * Overload returning true if the class is derived from
2281 * BlockSparsityPatternBase, which is what block sparsity patterns do.
2282 */
2283 template <typename T>
2284 static yes_type
2285 check_for_block_matrix(const BlockSparsityPatternBase<T> *);
2286
2287 /**
2288 * Overload for BlockSparseMatrixEZ, which is the only block matrix not
2289 * derived from BlockMatrixBase at the time of writing this class.
2290 */
2291 template <typename T>
2292 static yes_type
2293 check_for_block_matrix(const BlockSparseMatrixEZ<T> *);
2294
2295 /**
2296 * Catch all for all other potential matrix types that are not block
2297 * matrices.
2298 */
2299 static no_type
2300 check_for_block_matrix(...);
2301
2302 public:
2303 /**
2304 * A statically computable value that indicates whether the template
2305 * argument to this class is a block matrix (in fact whether the type is
2306 * derived from BlockMatrixBase<T>).
2307 */
2308 static const bool value =
2309 (sizeof(check_for_block_matrix(static_cast<MatrixType *>(nullptr))) ==
2310 sizeof(yes_type));
2311 };
2312
2313 // instantiation of the static member
2314 template <typename MatrixType>
2315 const bool IsBlockMatrix<MatrixType>::value;
2316
2317 template <typename number>
2318 template <typename MatrixType>
2319 inline void
distribute_local_to_global(const FullMatrix<number> & local_matrix,const std::vector<size_type> & local_dof_indices,MatrixType & global_matrix)2320 AffineConstraints<number>::distribute_local_to_global(
2321 const FullMatrix<number> & local_matrix,
2322 const std::vector<size_type> &local_dof_indices,
2323 MatrixType & global_matrix) const
2324 {
2325 // create a dummy and hand on to the function actually implementing this
2326 // feature in the cm.templates.h file.
2327 Vector<typename MatrixType::value_type> dummy(0);
2328 distribute_local_to_global(
2329 local_matrix,
2330 dummy,
2331 local_dof_indices,
2332 global_matrix,
2333 dummy,
2334 false,
2335 std::integral_constant<bool, IsBlockMatrix<MatrixType>::value>());
2336 }
2337
2338 template <typename number>
2339 template <typename MatrixType, typename VectorType>
2340 inline void
distribute_local_to_global(const FullMatrix<number> & local_matrix,const Vector<number> & local_vector,const std::vector<size_type> & local_dof_indices,MatrixType & global_matrix,VectorType & global_vector,bool use_inhomogeneities_for_rhs)2341 AffineConstraints<number>::distribute_local_to_global(
2342 const FullMatrix<number> & local_matrix,
2343 const Vector<number> & local_vector,
2344 const std::vector<size_type> &local_dof_indices,
2345 MatrixType & global_matrix,
2346 VectorType & global_vector,
2347 bool use_inhomogeneities_for_rhs) const
2348 {
2349 // enter the internal function with the respective block information set,
2350 // the actual implementation follows in the cm.templates.h file.
2351 distribute_local_to_global(
2352 local_matrix,
2353 local_vector,
2354 local_dof_indices,
2355 global_matrix,
2356 global_vector,
2357 use_inhomogeneities_for_rhs,
2358 std::integral_constant<bool, IsBlockMatrix<MatrixType>::value>());
2359 }
2360
2361 template <typename number>
2362 template <typename SparsityPatternType>
2363 inline void
add_entries_local_to_global(const std::vector<size_type> & local_dof_indices,SparsityPatternType & sparsity_pattern,const bool keep_constrained_entries,const Table<2,bool> & dof_mask)2364 AffineConstraints<number>::add_entries_local_to_global(
2365 const std::vector<size_type> &local_dof_indices,
2366 SparsityPatternType & sparsity_pattern,
2367 const bool keep_constrained_entries,
2368 const Table<2, bool> & dof_mask) const
2369 {
2370 // enter the internal function with the respective block information set,
2371 // the actual implementation follows in the cm.templates.h file.
2372 add_entries_local_to_global(
2373 local_dof_indices,
2374 sparsity_pattern,
2375 keep_constrained_entries,
2376 dof_mask,
2377 std::integral_constant<bool, IsBlockMatrix<SparsityPatternType>::value>());
2378 }
2379
2380 DEAL_II_NAMESPACE_CLOSE
2381
2382 #endif
2383