Debian Codegraph @

include/deal.II/numerics/matrix_tools.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 1998 - 2023 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_matrix_tools_h
16 #define dealii_matrix_tools_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/exceptions.h>
22 #include <deal.II/base/function.h>
23
24 #include <deal.II/lac/affine_constraints.h>
25
26 #include <deal.II/numerics/matrix_creator.h>
27
28 #include <map>
29
30 #ifdef DEAL_II_WITH_PETSC
31 # include <petscsys.h>
32 #endif
33
34 DEAL_II_NAMESPACE_OPEN
35
36
37 // forward declarations
38 #ifndef DOXYGEN
39 template <int dim>
40 class Quadrature;
41
42
43 template <typename number>
44 class Vector;
45 template <typename number>
46 class FullMatrix;
47 template <typename number>
48 class SparseMatrix;
49
50 template <typename number>
51 class BlockSparseMatrix;
52 template <typename Number>
53 class BlockVector;
54
55 template <int dim, int spacedim>
56 class Mapping;
57 template <int dim, int spacedim>
58 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
59 class DoFHandler;
60
61 namespace hp
62 {
63 template <int>
64 class QCollection;
65 template <int, int>
66 class MappingCollection;
67 } // namespace hp
68
69
70 # ifdef DEAL_II_WITH_PETSC
71 namespace PETScWrappers
72 {
73 class MatrixBase;
74 class VectorBase;
75 namespace MPI
76 {
77 class BlockSparseMatrix;
78 class BlockVector;
79 } // namespace MPI
80 } // namespace PETScWrappers
81 # endif
82
83 # ifdef DEAL_II_WITH_TRILINOS
84 namespace TrilinosWrappers
85 {
86 class SparseMatrix;
87 class BlockSparseMatrix;
88 namespace MPI
89 {
90 class Vector;
91 class BlockVector;
92 } // namespace MPI
93 } // namespace TrilinosWrappers
94 # endif
95 #endif
96
97
98
99 /**
100 * Provide a collection of functions operating on matrices. These include the
101 * application of boundary conditions to a linear system of equations and
102 * others.
103 *
104 *
105 * <h3>Boundary conditions</h3>
106 *
107 * The apply_boundary_values() functions modifies a linear system to incorporate
108 * the constraints that result from Dirichlet-type boundary conditions (or, more
109 * specifically: "strong" boundary conditions). To actually do this, the
110 * functions of this name in the current namespace require a list of degree of
111 * freedom indices along with the values these degrees of freedom should have.
112 * To see how to get such a list, see the discussion of the
113 * VectorTools::interpolate_boundary_values() function as one example.
114 *
115 * There are two ways to incorporate fixed degrees of freedom such as boundary
116 * nodes into a linear system, as discussed below. Both operate at either the
117 * level of local contributions to the global linear system, or the global
118 * system itself. A third way, using
119 * AffineConstraints::copy_local_to_global(), performs the same process as part
120 * of adding the local contributions of one cell into the global linear system
121 * (the "assembly" step) and is the method predominantly used in the tutorial
122 * programs today.
123 *
124 * @dealiiVideoLecture{21.6,21.65}
125 *
126 *
127 *
128 * <h3>Global elimination</h3>
129 *
130 * In the first method, we first assemble the global linear system without
131 * respect for fixed degrees of freedom, and in a second step eliminate them
132 * again from the linear system. The inclusion into the assembly process is as
133 * follows: when the matrix and vectors are set up, a list of nodes subject to
134 * Dirichlet boundary conditions is made and matrix and vectors are
135 * modified accordingly. This
136 * is done by deleting all entries in the matrix in the line of this degree of
137 * freedom, setting the main diagonal entry to a suitable positive value and
138 * the right hand side element to a value so that the solution of the linear
139 * system will have the boundary value at this node. To decouple the remaining
140 * linear system of equations and to make the system symmetric again (at least
141 * if it was before), one Gauss elimination step is performed with this line,
142 * by adding this (now almost empty) line to all other lines which couple with
143 * the given degree of freedom and thus eliminating all coupling between this
144 * degree of freedom and others. Now the respective column also consists only
145 * of zeroes, apart from the main diagonal entry. Alternatively, the functions
146 * in this namespace take a boolean parameter that allows to omit this last
147 * step, if symmetry of the resulting linear system is not required. Note that
148 * usually even CG can cope with a non-symmetric linear system with this
149 * particular structure.
150 *
151 * Finding which rows contain an entry in the column for which we are
152 * presently performing a Gauss elimination step is either difficult or very
153 * simple, depending on the circumstances. If the sparsity pattern is
154 * symmetric (whether the matrix is symmetric is irrelevant here), then we can
155 * infer the rows which have a nonzero entry in the present column by looking
156 * at which columns in the present row are nonempty. In this case, we only
157 * need to look into a fixed number of rows and need not search all rows. On
158 * the other hand, if the sparsity pattern is nonsymmetric, then we need to
159 * use an iterative solver which can handle nonsymmetric matrices in any case,
160 * so there may be no need to do the Gauss elimination anyway. In fact, this
161 * is the way the function works: it takes a parameter (@p eliminate_columns)
162 * that specifies whether the sparsity pattern is symmetric; if so, then the
163 * column is eliminated and the right hand side is also modified accordingly.
164 * If not, then only the row is deleted and the column is not touched at all,
165 * and all right hand side values apart from the one corresponding to the
166 * present row remain unchanged.
167 *
168 * If the sparsity pattern for your matrix is non-symmetric, you must set the
169 * value of this parameter to @p false in any case, since then we can't
170 * eliminate the column without searching all rows, which would be too
171 * expensive (if @p N be the number of rows, and @p m the number of nonzero
172 * elements per row, then eliminating one column is an <tt>O(N*log(m))</tt>
173 * operation, since searching in each row takes <tt>log(m)</tt> operations).
174 * If your sparsity pattern is symmetric, but your matrix is not, then you
175 * might specify @p false as well. If your sparsity pattern and matrix are
176 * both symmetric, you might want to specify @p true (the complexity of
177 * eliminating one row is then <tt>O(m*log(m))</tt>, since we only have to
178 * search @p m rows for the respective element of the column). Given the fact
179 * that @p m is roughly constant, irrespective of the discretization, and that
180 * the number of boundary nodes is <tt>sqrt(N)</tt> in 2d, the algorithm for
181 * symmetric sparsity patterns is <tt>O(sqrt(N)*m*log(m))</tt>, while it would
182 * be <tt>O(N*sqrt(N)*log(m))</tt> for the general case; the latter is too
183 * expensive to be performed.
184 *
185 * It seems as if we had to make clear not to overwrite the lines of other
186 * boundary nodes when doing the Gauss elimination step. However, since we
187 * reset the right hand side when passing such a node, it is not a problem to
188 * change the right hand side values of other boundary nodes not yet
189 * processed. It would be a problem to change those entries of nodes already
190 * processed, but since the matrix entry of the present column on the row of
191 * an already processed node is zero, the Gauss step does not change the right
192 * hand side. We need therefore not take special care of other boundary nodes.
193 *
194 * To make solving faster, we preset the solution vector with the right
195 * boundary values (as to why this is necessary, see the discussion below in
196 * the description of local elimination). It it not clear whether the deletion
197 * of coupling between the boundary degree of freedom and other dofs really
198 * forces the corresponding entry in the solution vector to have the right
199 * value when using iterative solvers, since their search directions may
200 * contain components in the direction of the boundary node. For this reason,
201 * we perform a very simple line balancing by not setting the main diagonal
202 * entry to unity, but rather to the value it had before deleting this line,
203 * or to the first nonzero main diagonal entry if it is zero for some reason.
204 * Of course we have to change the right hand side appropriately. This is not
205 * a very good strategy, but it at least should give the main diagonal entry a
206 * value in the right order of dimension, which makes the solution process a
207 * bit more stable. A refined algorithm would set the entry to the mean of the
208 * other diagonal entries, but this seems to be too expensive.
209 *
210 * In some cases, it might be interesting to solve several times with the same
211 * matrix, but for different right hand sides or boundary values. A typical
212 * case would be the solution of a time-dependent problem in which the boundary
213 * values or right hand side change, but the matrix itself does not. One
214 * may then be tempted to just assemble the matrix once and just call the
215 * MatrixTools::apply_boundary_values() function repeatedly on the same
216 * matrix object, with a right hand side vector newly formed in each time step.
217 * However,
218 * since the modification for boundary values of the right hand side vector
219 * depends on the original matrix, this is not possible without storing the
220 * original matrix somewhere, and in every time step initializing the system
221 * matrix with the unmodified matrix stored elsewhere. step-26 does a variation
222 * of this process by storing building blocks from which the system matrix is
223 * composed, but the general principle is the same. Alternatively, one can
224 * use the constrained_linear_operator() function. In its documentation you can
225 * also find a formal (mathematical) description of the process of modifying the
226 * matrix and right hand side vectors for boundary values.
227 *
228 *
229 * <h3>Local elimination</h3>
230 *
231 * The second way of handling boundary values is to modify the local matrix
232 * and vector contributions appropriately before transferring them into the
233 * global sparse matrix and vector. This is what local_apply_boundary_values()
234 * does. The advantage is that we save the call to the apply_boundary_values
235 * function (which is expensive because it has to work on sparse data
236 * structures). On the other hand, the local_apply_boundary_values() function
237 * is called many times, even if we only have a very small number of fixed
238 * boundary nodes, and the main drawback is that this function doesn't work as
239 * expected if there are hanging nodes that also need to be treated. The
240 * reason that this function doesn't work is that it is meant to be run before
241 * distribution into the global matrix, i.e. before hanging nodes are
242 * distributed; since hanging nodes can be constrained to a boundary node, the
243 * treatment of hanging nodes can add entries again to rows and columns
244 * corresponding to boundary values and that we have already vacated in the
245 * local elimination step. To make things worse, in 3d constrained nodes can
246 * even lie on the boundary. Thus, it is imperative that boundary node
247 * elimination happens @em after hanging node elimination, but this can't be
248 * achieved with local elimination of boundary nodes unless there are no
249 * hanging node constraints at all.
250 *
251 * Local elimination has one additional drawback: we don't have access to the
252 * solution vector, only to the local contributions to the matrix and right
253 * hand side. The problem with this is subtle, but can lead to very hard to
254 * find difficulties: when we eliminate a degree of freedom, we delete the row
255 * and column of this unknown, and set the diagonal entry to some positive
256 * value. To make the problem more or less well-conditioned, we set this
257 * diagonal entry to the absolute value of its prior value if that was
258 * non-zero, or to the average magnitude of all other nonzero diagonal elements.
259 * Then we set the right hand side value such that the resulting solution
260 * entry has the right value as given by the boundary values. Since we add
261 * these contributions up over all local contributions, the diagonal entry and
262 * the respective value in the right hand side are added up correspondingly,
263 * so that the entry in the solution of the linear system is still valid.
264 *
265 * A problem arises, however, if the diagonal entries so chosen are not
266 * appropriate for the linear system. Consider, for example, a mixed Laplace
267 * problem with matrix <tt>[[A B][C^T 0]]</tt>, where we only specify boundary
268 * values for the second component of the solution. In the mixed formulation,
269 * the stress-strain tensor only appears in either the matrix @p B or @p C, so
270 * one of them may be significantly larger or smaller than the other one. Now,
271 * if we eliminate boundary values, we delete some rows and columns, but we
272 * also introduce a few entries on the diagonal of the lower right block, so
273 * that we get the system <tt>[[A' B'][C'^T X]]</tt>. The diagonal entries in
274 * the matrix @p X will be of the same order of magnitude as those in @p A.
275 * Now, if we solve this system in the Schur complement formulation, we have
276 * to invert the matrix <tt>X-C'^TA'^{-1}B'</tt>. Deleting rows and columns
277 * above makes sure that boundary nodes indeed have empty rows and columns in
278 * the Schur complement as well, except for the entries in @p X. However, the
279 * entries in @p X may be of significantly different orders of magnitude than
280 * those in <tt>C'^TA'^{-1}B'</tt>! If this is the case, we may run into
281 * trouble with iterative solvers. For example, assume that we start with zero
282 * entries in the solution vector and that the entries in @p X are several
283 * orders of magnitude too small; in this case, iterative solvers will compute
284 * the residual vector in each step and form correction vectors, but since the
285 * entries in @p X are so small, the residual contributions for boundary nodes
286 * are really small, despite the fact that the boundary nodes are still at
287 * values close to zero and not in accordance with the prescribed boundary
288 * values. Since the residual is so small, the corrections the iterative
289 * solver computes are very small, and in the end the solver will indicate
290 * convergence to a small total residual with the boundary values still being
291 * significantly wrong.
292 *
293 * We avoid this problem in the global elimination process described above by
294 * 'priming' the solution vector with the correct values for boundary nodes.
295 * However, we can't do this for the local elimination process. Therefore, if
296 * you experience a problem like the one above, you need to either increase
297 * the diagonal entries in @p X to a size that matches those in the other part
298 * of the Schur complement, or, simpler, prime the solution vector before you
299 * start the solver.
300 *
301 * In conclusion, local elimination of boundary nodes only works if there are
302 * no hanging nodes and even then doesn't always work fully satisfactorily.
303 *
304 * @ingroup numerics
305 */
306 namespace MatrixTools
307 {
308 /**
309 * Import namespace MatrixCreator for backward compatibility with older
310 * versions of deal.II in which these namespaces were classes and class
311 * MatrixTools was publicly derived from class MatrixCreator.
312 */
313 using namespace MatrixCreator;
314
315 /**
316 * Apply Dirichlet boundary conditions to the system matrix and vectors as
317 * described in the general documentation of this namespace.
318 */
319 template <typename number>
320 void
321 apply_boundary_values(
322 const std::map<types::global_dof_index, number> &boundary_values,
323 SparseMatrix<number> &matrix,
324 Vector<number> &solution,
325 Vector<number> &right_hand_side,
326 const bool eliminate_columns = true);
327
328 /**
329 * Apply Dirichlet boundary conditions to the system matrix and vectors as
330 * described in the general documentation of this namespace. This function
331 * works for block sparse matrices and block vectors.
332 */
333 template <typename number>
334 void
335 apply_boundary_values(
336 const std::map<types::global_dof_index, number> &boundary_values,
337 BlockSparseMatrix<number> &matrix,
338 BlockVector<number> &solution,
339 BlockVector<number> &right_hand_side,
340 const bool eliminate_columns = true);
341
342 #ifdef DEAL_II_WITH_PETSC
343 /**
344 * Apply Dirichlet boundary conditions to the system matrix and vectors as
345 * described in the general documentation of this namespace. This function
346 * works on the classes that are used to wrap PETSc objects.
347 *
348 * This function is used in step-17 and step-18.
349 */
350 void
351 apply_boundary_values(
352 const std::map<types::global_dof_index, PetscScalar> &boundary_values,
353 PETScWrappers::MatrixBase &matrix,
354 PETScWrappers::VectorBase &solution,
355 PETScWrappers::VectorBase &right_hand_side,
356 const bool eliminate_columns = true);
357
358 /**
359 * Same as above but for the parallel BlockSparseMatrix.
360 */
361 void
362 apply_boundary_values(
363 const std::map<types::global_dof_index, PetscScalar> &boundary_values,
364 PETScWrappers::MPI::BlockSparseMatrix &matrix,
365 PETScWrappers::MPI::BlockVector &solution,
366 PETScWrappers::MPI::BlockVector &right_hand_side,
367 const bool eliminate_columns = true);
368
369 #endif
370
371 #ifdef DEAL_II_WITH_TRILINOS
372 /**
373 * Apply Dirichlet boundary conditions to the system matrix and vectors as
374 * described in the general documentation of this namespace. This function
375 * works on the classes that are used to wrap Trilinos objects.
376 *
377 * <b>Important:</b> This function is not very efficient: it needs to
378 * alternatingly read and write into the matrix, a situation that Trilinos
379 * does not handle well. In addition, we only get rid of rows corresponding
380 * to boundary nodes, but the corresponding case of deleting the respective
381 * columns (i.e. if @p eliminate_columns is @p true) is not presently
382 * implemented, and probably will never because it is too expensive without
383 * direct access to the Trilinos data structures. (This leads to the
384 * situation where the action indicated by the default value of the last
385 * argument is actually not implemented; that argument has <code>true</code>
386 * as its default value to stay consistent with the other functions of same
387 * name in this namespace.)
388 *
389 * @note If the matrix is stored in parallel across multiple processors
390 * using MPI, this function only touches rows that are locally stored and
391 * simply ignores all other rows. In other words, each processor is
392 * responsible for its own rows, and the @p boundary_values argument needs
393 * to contain all locally owned rows of the matrix that you want to have
394 * treated. (But it can also contain entries for degrees of freedom not
395 * owned locally; these will simply be ignored.) Further, in the context of
396 * parallel computations, you will get into trouble if you treat a row while
397 * other processors still have pending writes or additions into the same
398 * row. In other words, if another processor still wants to add something to
399 * an element of a row and you call this function to zero out the row, then
400 * the next time you call compress() may add the remote value to the zero
401 * you just created. Consequently, you will want to call compress() after
402 * you made the last modifications to a matrix and before starting to clear
403 * rows.
404 */
405 void
406 apply_boundary_values(
407 const std::map<types::global_dof_index, TrilinosScalar> &boundary_values,
408 TrilinosWrappers::SparseMatrix &matrix,
409 TrilinosWrappers::MPI::Vector &solution,
410 TrilinosWrappers::MPI::Vector &right_hand_side,
411 const bool eliminate_columns = true);
412
413 /**
414 * This function does the same as the one above, except now working on block
415 * structures.
416 */
417 void
418 apply_boundary_values(
419 const std::map<types::global_dof_index, TrilinosScalar> &boundary_values,
420 TrilinosWrappers::BlockSparseMatrix &matrix,
421 TrilinosWrappers::MPI::BlockVector &solution,
422 TrilinosWrappers::MPI::BlockVector &right_hand_side,
423 const bool eliminate_columns = true);
424 #endif
425
426 /**
427 * Rather than applying boundary values to the global matrix and vector
428 * after creating the global matrix, this function does so during assembly,
429 * by modifying the local matrix and vector contributions. If you call this
430 * function on all local contributions, the resulting matrix will have the
431 * same entries, and the final call to apply_boundary_values() on the global
432 * system will not be necessary.
433 *
434 * Since this function does not have to work on the complicated data
435 * structures of sparse matrices, it is relatively cheap. It may therefore
436 * be a win if you have many fixed degrees of freedom (e.g. boundary nodes),
437 * or if access to the sparse matrix is expensive (e.g. for block sparse
438 * matrices, or for PETSc or Trilinos matrices). However, it doesn't work as
439 * expected if there are also hanging nodes to be considered. More caveats
440 * are listed in the general documentation of this namespace.
441 *
442 * @dealiiVideoLecture{21.6,21.65}
443 */
444 template <typename number>
445 void
446 local_apply_boundary_values(
447 const std::map<types::global_dof_index, number> &boundary_values,
448 const std::vector<types::global_dof_index> &local_dof_indices,
449 FullMatrix<number> &local_matrix,
450 Vector<number> &local_rhs,
451 const bool eliminate_columns);
452
453 /**
454 * Exception
455 */
456 DeclExceptionMsg(ExcBlocksDontMatch,
457 "You are providing a matrix whose subdivision into "
458 "blocks in either row or column direction does not use "
459 "the same blocks sizes as the solution vector or "
460 "right hand side vectors, respectively.");
461 } // namespace MatrixTools
462
463
464
465 DEAL_II_NAMESPACE_CLOSE
466
467 #endif