Debian Codegraph @

include/deal.II/lac/sparse_vanka.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 1999 - 2025 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_sparse_vanka_h
16 #define dealii_sparse_vanka_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/multithread_info.h>
21 #include <deal.II/base/observer_pointer.h>
22 #include <deal.II/base/types.h>
23
24 #include <vector>
25
26 DEAL_II_NAMESPACE_OPEN
27
28 // Forward declarations
29 #ifndef DOXYGEN
30 template <typename number>
31 class FullMatrix;
32 template <typename number>
33 class SparseMatrix;
34 template <typename number>
35 class Vector;
36
37 template <typename number>
38 class SparseVanka;
39 template <typename number>
40 class SparseBlockVanka;
41 #endif
42
43 /**
44 * @addtogroup Preconditioners
45 * @{
46 */
47
48 /**
49 * Point-wise Vanka preconditioning. This class does Vanka preconditioning on
50 * a point-wise base. Vanka preconditioners are used for saddle point problems
51 * like Stokes' problem or problems arising in optimization where Lagrange
52 * multipliers occur and the Newton method matrix has a zero block. With these
53 * matrices the application of Jacobi or Gauss-Seidel methods is impossible,
54 * because some diagonal elements are zero in the rows of the Lagrange
55 * multiplier. The approach of Vanka is to solve a small (usually indefinite)
56 * system of equations for each Langrange multiplier variable (we will also
57 * call the pressure in Stokes' equation a Langrange multiplier since it can
58 * be interpreted as such).
59 *
60 * Objects of this class are constructed by passing a vector of indices of the
61 * degrees of freedom of the Lagrange multiplier. In the actual
62 * preconditioning method, these rows are traversed in the order in which the
63 * appear in the matrix. Since this is a Gauß-Seidel like procedure, remember
64 * to have a good ordering in advance (for transport dominated problems,
65 * Cuthill-McKee algorithms are a good means for this, if points on the inflow
66 * boundary are chosen as starting points for the renumbering).
67 *
68 * For each selected degree of freedom, a local system of equations is built
69 * by the degree of freedom itself and all other values coupling immediately,
70 * i.e. the set of degrees of freedom considered for the local system of
71 * equations for degree of freedom @p i is @p i itself and all @p j such that
72 * the element <tt>(i,j)</tt> is a nonzero entry in the sparse matrix under
73 * consideration. The elements <tt>(j,i)</tt> are not considered. We now pick
74 * all matrix entries from rows and columns out of the set of degrees of
75 * freedom just described out of the global matrix and put it into a local
76 * matrix, which is subsequently inverted. This system may be of different
77 * size for each degree of freedom, depending for example on the local
78 * neighborhood of the respective node on a computational grid.
79 *
80 * The right hand side is built up in the same way, i.e. by copying all
81 * entries that coupled with the one under present consideration, but it is
82 * augmented by all degrees of freedom coupling with the degrees from the set
83 * described above (i.e. the DoFs coupling second order to the present one).
84 * The reason for this is, that the local problems to be solved shall have
85 * Dirichlet boundary conditions on the second order coupling DoFs, so we have
86 * to take them into account but eliminate them before actually solving; this
87 * elimination is done by the modification of the right hand side, and in the
88 * end these degrees of freedom do not occur in the matrix and solution vector
89 * any more at all.
90 *
91 * This local system is solved and the values are updated into the destination
92 * vector.
93 *
94 * Remark: the Vanka method is a non-symmetric preconditioning method.
95 *
96 *
97 * <h3>Example of Use</h3> This little example is taken from a program doing
98 * parameter optimization. The Lagrange multiplier is the third component of
99 * the finite element used. The system is solved by the GMRES method.
100 * @code
101 * // tag the Lagrange multiplier variable
102 * vector<bool> signature(3);
103 * signature[0] = signature[1] = false;
104 * signature[2] = true;
105 *
106 * // tag all dofs belonging to the Lagrange multiplier
107 * vector<bool> selected_dofs (dof.n_dofs(), false);
108 * DoFTools::extract_dofs(dof, signature, p_select);
109 * // create the Vanka object
110 * SparseVanka<double> vanka (global_matrix, selected_dofs);
111 *
112 * // create the solver
113 * SolverGMRES<> gmres(control,memory,504);
114 *
115 * // solve
116 * gmres.solve (global_matrix, solution, right_hand_side,
117 * vanka);
118 * @endcode
119 *
120 *
121 * <h4>Implementor's remark</h4> At present, the local matrices are built up
122 * such that the degree of freedom associated with the local Lagrange
123 * multiplier is the first one. Thus, usually the upper left entry in the
124 * local matrix is zero. It is not clear to me (W.B.) whether this might pose
125 * some problems in the inversion of the local matrices. Maybe someone would
126 * like to check this.
127 *
128 * @note Instantiations for this template are provided for <tt>@<float@> and
129 * @<double@></tt>; others can be generated in application programs (see the
130 * section on
131 * @ref Instantiations
132 * in the manual).
133 */
134 template <typename number>
135 class SparseVanka
136 {
137 public:
138 /**
139 * Declare type for container size.
140 */
141 using size_type = types::global_dof_index;
142
143 /**
144 * Constructor. Does nothing.
145 *
146 * Call the initialize() function before using this object as preconditioner
147 * (vmult()).
148 */
149 SparseVanka();
150
151 /**
152 * Constructor. Gets the matrix for preconditioning and a bit vector with
153 * entries @p true for all rows to be updated. A reference to this vector
154 * will be stored, so it must persist longer than the Vanka object. The same
155 * is true for the matrix.
156 *
157 * The matrix @p M which is passed here may or may not be the same matrix
158 * for which this object shall act as preconditioner. In particular, it is
159 * conceivable that the preconditioner is build up for one matrix once, but
160 * is used for subsequent steps in a nonlinear process as well, where the
161 * matrix changes in each step slightly.
162 */
163 SparseVanka(const SparseMatrix<number> &M, const std::vector<bool> &selected);
164
165 /**
166 * Destructor. Delete all allocated matrices.
167 */
168 ~SparseVanka();
169
170 /**
171 * Parameters for SparseVanka.
172 */
173 class AdditionalData
174 {
175 public:
176 /**
177 * Constructor. For the parameters' description, see below.
178 */
179 explicit AdditionalData(const std::vector<bool> &selected);
180
181 /**
182 * Indices of those degrees of freedom that we shall work on.
183 */
184 const std::vector<bool> &selected;
185 };
186
187
188 /**
189 * If the default constructor is used then this function needs to be called
190 * before an object of this class is used as preconditioner.
191 *
192 * For more detail about possible parameters, see the class documentation
193 * and the documentation of the SparseVanka::AdditionalData class.
194 *
195 * After this function is called the preconditioner is ready to be used
196 * (using the <code>vmult</code> function of derived classes).
197 */
198 void
199 initialize(const SparseMatrix<number> &M,
200 const AdditionalData &additional_data);
201
202 /**
203 * Do the preconditioning. This function takes the residual in @p src and
204 * returns the resulting update vector in @p dst.
205 */
206 template <typename number2>
207 void
208 vmult(Vector<number2> &dst, const Vector<number2> &src) const;
209
210 /**
211 * Apply transpose preconditioner. This function takes the residual in @p
212 * src and returns the resulting update vector in @p dst.
213 */
214 template <typename number2>
215 void
216 Tvmult(Vector<number2> &dst, const Vector<number2> &src) const;
217
218 /**
219 * Clear all memory.
220 */
221 void
222 clear();
223
224 /**
225 * Return the dimension of the codomain (or range) space. Note that the
226 * matrix is of dimension $m \times n$.
227 *
228 * @note This function should only be called if the preconditioner has been
229 * initialized.
230 */
231 size_type
232 m() const;
233
234 /**
235 * Return the dimension of the domain space. Note that the matrix is of
236 * dimension $m \times n$.
237 *
238 * @note This function should only be called if the preconditioner has been
239 * initialized.
240 */
241 size_type
242 n() const;
243
244 protected:
245 /**
246 * Apply the inverses corresponding to those degrees of freedom that have a
247 * @p true value in @p dof_mask, to the @p src vector and move the result
248 * into @p dst. The transpose of the inverse is applied instead if
249 * @p transpose equals true. Actually, only values for allowed indices are
250 * written to @p dst, so the application of this function only does what is
251 * announced in the general documentation if the given mask sets all values
252 * to zero.
253 *
254 * The reason for providing the mask anyway is that in derived classes we
255 * may want to apply the preconditioner to parts of the matrix only, in
256 * order to parallelize the application. Then, it is important to only write
257 * to some slices of @p dst, in order to eliminate the dependencies of
258 * threads of each other.
259 *
260 * If a null pointer is passed instead of a pointer to the @p dof_mask (as
261 * is the default value), then it is assumed that we shall work on all
262 * degrees of freedom. This is then equivalent to calling the function with
263 * a <tt>vector<bool>(n_dofs,true)</tt>.
264 *
265 * The @p vmult of this class of course calls this function with a null
266 * pointer
267 */
268
269 template <typename number2>
270 void
271 apply_preconditioner(Vector<number2> &dst,
272 const Vector<number2> &src,
273 const bool transpose = false,
274 const std::vector<bool> *const dof_mask = nullptr) const;
275
276 /**
277 * Determine an estimate for the memory consumption (in bytes) of this
278 * object.
279 */
280 std::size_t
281 memory_consumption() const;
282
283 private:
284 /**
285 * Pointer to the matrix.
286 */
287 ObserverPointer<const SparseMatrix<number>, SparseVanka<number>> matrix;
288
289 /**
290 * Indices of those degrees of freedom that we shall work on.
291 */
292 const std::vector<bool> *selected;
293
294 /**
295 * Array of inverse matrices, one for each degree of freedom. Only those
296 * elements will be used that are tagged in @p selected.
297 */
298 mutable std::vector<ObserverPointer<FullMatrix<float>, SparseVanka<number>>>
299 inverses;
300
301 /**
302 * The dimension of the range space.
303 */
304 size_type _m;
305
306 /**
307 * The dimension of the domain space.
308 */
309 size_type _n;
310
311 /**
312 * Compute the inverses of all selected diagonal elements.
313 */
314 void
315 compute_inverses();
316
317 /**
318 * Compute the inverses at positions in the range <tt>[begin,end)</tt>. In
319 * non-multithreaded mode, <tt>compute_inverses()</tt> calls this function
320 * with the whole range, but in multithreaded mode, several copies of this
321 * function are spawned.
322 */
323 void
324 compute_inverses(const size_type begin, const size_type end);
325
326 /**
327 * Compute the inverse of the block located at position @p row. Since the
328 * vector is used quite often, it is generated only once in the caller of
329 * this function and passed to this function which first clears it. Reusing
330 * the vector makes the process significantly faster than in the case where
331 * this function re-creates it each time.
332 */
333 void
334 compute_inverse(const size_type row, std::vector<size_type> &local_indices);
335
336 // Make the derived class a friend. This seems silly, but is actually
337 // necessary, since derived classes can only access non-public members
338 // through their @p this pointer, but not access these members as member
339 // functions of other objects of the type of this base class (i.e. like
340 // <tt>x.f()</tt>, where @p x is an object of the base class, and @p f one
341 // of it's non-public member functions).
342 //
343 // Now, in the case of the @p SparseBlockVanka class, we would like to take
344 // the address of a function of the base class in order to call it through
345 // the multithreading framework, so the derived class has to be a friend.
346 template <typename T>
347 friend class SparseBlockVanka;
348 };
349
350
351
352 /**
353 * Block version of the sparse Vanka preconditioner. This class divides the
354 * matrix into blocks and works on the diagonal blocks only, which of course
355 * reduces the efficiency as preconditioner, but is perfectly parallelizable.
356 * The constructor takes a parameter into how many blocks the matrix shall be
357 * subdivided and then lets the underlying class do the work. Division of the
358 * matrix is done in several ways which are described in detail below.
359 *
360 * This class is probably useless if you don't have a multiprocessor system,
361 * since then the amount of work per preconditioning step is the same as for
362 * the @p SparseVanka class, but preconditioning properties are worse. On the
363 * other hand, if you have a multiprocessor system, the worse preconditioning
364 * quality (leading to more iterations of the linear solver) usually is well
365 * balanced by the increased speed of application due to the parallelization,
366 * leading to an overall decrease in elapsed wall-time for solving your linear
367 * system. It should be noted that the quality as preconditioner reduces with
368 * growing number of blocks, so there may be an optimal value (in terms of
369 * wall-time per linear solve) for the number of blocks.
370 *
371 * To facilitate writing portable code, if the number of blocks into which the
372 * matrix is to be subdivided, is set to one, then this class acts just like
373 * the @p SparseVanka class. You may therefore want to set the number of
374 * blocks equal to the number of processors you have.
375 *
376 * Note that the parallelization is done if <tt>deal.II</tt> was configured
377 * for multithread use and that the number of threads which is spawned equals
378 * the number of blocks. This is reasonable since you will not want to set the
379 * number of blocks unnecessarily large, since, as mentioned, this reduces the
380 * preconditioning properties.
381 *
382 *
383 * <h3>Splitting the matrix into blocks</h3>
384 *
385 * Splitting the matrix into blocks is always done in a way such that the
386 * blocks are not necessarily of equal size, but such that the number of
387 * selected degrees of freedom for which a local system is to be solved is
388 * equal between blocks. The reason for this strategy to subdivision is
389 * load-balancing for multithreading. There are several possibilities to
390 * actually split the matrix into blocks, which are selected by the flag @p
391 * blocking_strategy that is passed to the constructor. By a block, we will in
392 * the sequel denote a list of indices of degrees of freedom; the algorithm
393 * will work on each block separately, i.e. the solutions of the local systems
394 * corresponding to a degree of freedom of one block will only be used to
395 * update the degrees of freedom belonging to the same block, but never to
396 * update degrees of freedom of other blocks. A block can be a consecutive
397 * list of indices, as in the first alternative below, or a nonconsecutive
398 * list of indices. Of course, we assume that the intersection of each two
399 * blocks is empty and that the union of all blocks equals the interval
400 * <tt>[0,N)</tt>, where @p N is the number of degrees of freedom of the
401 * system of equations.
402 *
403 * <ul>
404 * <li> @p index_intervals: Here, we chose the blocks to be intervals
405 * <tt>[a_i,a_{i+1</tt>)}, i.e. consecutive degrees of freedom are usually
406 * also within the same block. This is a reasonable strategy, if the degrees
407 * of freedom have, for example, be re-numbered using the Cuthill-McKee
408 * algorithm, in which spatially neighboring degrees of freedom have
409 * neighboring indices. In that case, coupling in the matrix is usually
410 * restricted to the vicinity of the diagonal as well, and we can simply cut
411 * the matrix into blocks.
412 *
413 * The bounds of the intervals, i.e. the @p a_i above, are chosen such that
414 * the number of degrees of freedom on which we shall work (i.e. usually the
415 * degrees of freedom corresponding to Lagrange multipliers) is about the same
416 * in each block; this does not mean, however, that the sizes of the blocks
417 * are equal, since the blocks also comprise the other degrees of freedom for
418 * which no local system is solved. In the extreme case, consider that all
419 * Lagrange multipliers are sorted to the end of the range of DoF indices,
420 * then the first block would be very large, since it comprises all other DoFs
421 * and some Lagrange multipliers, while all other blocks are rather small and
422 * comprise only Langrange multipliers. This strategy therefore does not only
423 * depend on the order in which the Lagrange DoFs are sorted, but also on the
424 * order in which the other DoFs are sorted. It is therefore necessary to note
425 * that this almost renders the capability as preconditioner useless if the
426 * degrees of freedom are numbered by component, i.e. all Lagrange multipliers
427 * en bloc.
428 *
429 * <li> @p adaptive: This strategy is a bit more clever in cases where the
430 * Langrange DoFs are clustered, as in the example above. It works as follows:
431 * it first groups the Lagrange DoFs into blocks, using the same strategy as
432 * above. However, instead of grouping the other DoFs into the blocks of
433 * Lagrange DoFs with nearest DoF index, it decides for each non-Lagrange DoF
434 * to put it into the block of Lagrange DoFs which write to this non-Lagrange
435 * DoF most often. This makes it possible to even sort the Lagrange DoFs to
436 * the end and still associate spatially neighboring non-Lagrange DoFs to the
437 * same blocks where the respective Lagrange DoFs are, since they couple to
438 * each other while spatially distant DoFs don't couple.
439 *
440 * The additional computational effort to sorting the non-Lagrange DoFs is not
441 * very large compared with the inversion of the local systems and applying
442 * the preconditioner, so this strategy might be reasonable if you want to
443 * sort your degrees of freedom by component. If the degrees of freedom are
444 * not sorted by component, the results of the both strategies outlined above
445 * does not differ much. However, unlike the first strategy, the performance
446 * of the second strategy does not deteriorate if the DoFs are renumbered by
447 * component.
448 * </ul>
449 *
450 *
451 * <h3>Typical results</h3>
452 *
453 * As a prototypical test case, we use a nonlinear problem from optimization,
454 * which leads to a series of saddle point problems, each of which is solved
455 * using GMRES with Vanka as preconditioner. The equation had approx. 850
456 * degrees of freedom. With the non-blocked version @p SparseVanka (or @p
457 * SparseBlockVanka with <tt>n_blocks==1</tt>), the following numbers of
458 * iterations is needed to solver the linear system in each nonlinear step:
459 * @verbatim
460 * 101 68 64 53 35 21
461 * @endverbatim
462 *
463 * With four blocks, we need the following numbers of iterations
464 * @verbatim
465 * 124 88 83 66 44 28
466 * @endverbatim
467 * As can be seen, more iterations are needed. However, in terms of computing
468 * time, the first version needs 72 seconds wall time (and 79 seconds CPU
469 * time, which is more than wall time since some other parts of the program
470 * were parallelized as well), while the second version needed 53 second wall
471 * time (and 110 seconds CPU time) on a four processor machine. The total time
472 * is in both cases dominated by the linear solvers. In this case, it is
473 * therefore worth while using the blocked version of the preconditioner if
474 * wall time is more important than CPU time.
475 *
476 * The results with the block version above were obtained with the first
477 * blocking strategy and the degrees of freedom were not numbered by
478 * component. Using the second strategy does not much change the numbers of
479 * iterations (at most by one in each step) and they also do not change when
480 * the degrees of freedom are sorted by component, while the first strategy
481 * significantly deteriorated.
482 */
483 template <typename number>
484 class SparseBlockVanka : public SparseVanka<number>
485 {
486 public:
487 /**
488 * Declare type for container size.
489 */
490 using size_type = types::global_dof_index;
491
492 /**
493 * Enumeration of the different methods by which the DoFs are distributed to
494 * the blocks on which we are to work.
495 */
496 enum BlockingStrategy
497 {
498 /**
499 * Block by index intervals.
500 */
501 index_intervals,
502 /**
503 * Block with an adaptive strategy.
504 */
505 adaptive
506 };
507
508 /**
509 * Constructor. Pass all arguments except for @p n_blocks to the base class.
510 */
511 SparseBlockVanka(const SparseMatrix<number> &M,
512 const std::vector<bool> &selected,
513 const unsigned int n_blocks,
514 const BlockingStrategy blocking_strategy);
515
516 /**
517 * Apply the preconditioner.
518 */
519 template <typename number2>
520 void
521 vmult(Vector<number2> &dst, const Vector<number2> &src) const;
522
523
524 /**
525 * Apply the transpose preconditioner.
526 */
527 template <typename number2>
528 void
529 Tvmult(Vector<number2> &dst, const Vector<number2> &src) const;
530
531 /**
532 * Determine an estimate for the memory consumption (in bytes) of this
533 * object.
534 */
535 std::size_t
536 memory_consumption() const;
537
538 private:
539 /**
540 * Store the number of blocks.
541 */
542 const unsigned int n_blocks;
543
544 /**
545 * In this field, we precompute for each block which degrees of freedom
546 * belong to it. Thus, if <tt>dof_masks[i][j]==true</tt>, then DoF @p j
547 * belongs to block @p i. Of course, no other <tt>dof_masks[l][j]</tt> may
548 * be @p true for <tt>l!=i</tt>. This computation is done in the
549 * constructor, to avoid recomputing each time the preconditioner is called.
550 */
551 std::vector<std::vector<bool>> dof_masks;
552
553 /**
554 * Compute the contents of the field @p dof_masks. This function is called
555 * from the constructor.
556 */
557 void
558 compute_dof_masks(const SparseMatrix<number> &M,
559 const std::vector<bool> &selected,
560 const BlockingStrategy blocking_strategy);
561 };
562
563 /** @} */
564 /* ---------------------------------- Inline functions ------------------- */
565
566 #ifndef DOXYGEN
567
568 template <typename number>
569 inline typename SparseVanka<number>::size_type
570 SparseVanka<number>::m() const
571 {
572 Assert(_m != 0, ExcNotInitialized());
573 return _m;
574 }
575
576 template <typename number>
577 inline typename SparseVanka<number>::size_type
578 SparseVanka<number>::n() const
579 {
580 Assert(_n != 0, ExcNotInitialized());
581 return _n;
582 }
583
584 #endif // DOXYGEN
585
586 DEAL_II_NAMESPACE_CLOSE
587
588 #endif