Debian Codegraph @

include/deal.II/lac/schur_complement.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2016 - 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_schur_complement_h
16 #define dealii_schur_complement_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/exceptions.h>
21
22 #include <deal.II/lac/linear_operator.h>
23 #include <deal.II/lac/packaged_operation.h>
24 #include <deal.II/lac/vector_memory.h>
25
26
27 DEAL_II_NAMESPACE_OPEN
28
29 /**
30 * @name Creation of a LinearOperator related to the Schur Complement
31 */
32 /** @{ */
33
34 /**
35 * @relatesalso LinearOperator
36 *
37 * Return a LinearOperator that performs the operations associated with the
38 * Schur complement. There are two additional helper functions,
39 * condense_schur_rhs() and postprocess_schur_solution(), that are likely
40 * necessary to be used in order to perform any useful tasks in linear algebra
41 * with this operator.
42 *
43 * We construct the definition of the Schur complement in the following way:
44 *
45 * Consider a general system of linear equations that can be decomposed into
46 * two major sets of equations:
47 * @f{eqnarray*}{
48 * \mathbf{K}\mathbf{d} = \mathbf{f}
49 * \quad \Rightarrow\quad
50 * \left(\begin{array}{cc}
51 * A & B \\ C & D
52 * \end{array}\right)
53 * \left(\begin{array}{cc}
54 * x \\ y
55 * \end{array}\right)
56 * =
57 * \left(\begin{array}{cc}
58 * f \\ g
59 * \end{array}\right),
60 * @f}
61 * where $ A,B,C,D $ represent general subblocks of the matrix $ \mathbf{K} $
62 * and, similarly, general subvectors of $ \mathbf{d},\mathbf{f} $ are given
63 * by $ x,y,f,g $ .
64 *
65 * This is equivalent to the following two statements:
66 * @f{eqnarray*}{
67 * (1) \quad Ax + By &=& f \\
68 * (2) \quad Cx + Dy &=& g \quad .
69 * @f}
70 *
71 * Assuming that $ A,D $ are both square and invertible, we could then perform
72 * one of two possible substitutions,
73 * @f{eqnarray*}{
74 * (3) \quad x &=& A^{-1}(f - By) \quad \text{from} \quad (1) \\
75 * (4) \quad y &=& D^{-1}(g - Cx) \quad \text{from} \quad (2) ,
76 * @f}
77 * which amount to performing block Gaussian elimination on this system of
78 * equations.
79 *
80 * For the purpose of the current implementation, we choose to substitute (3)
81 * into (2)
82 * @f{eqnarray*}{
83 * C \: A^{-1}(f - By) + Dy &=& g \\
84 * -C \: A^{-1} \: By + Dy &=& g - C \: A^{-1} \: f \quad .
85 * @f}
86 * This leads to the result
87 * @f[
88 * (5) \quad (D - C\: A^{-1} \:B)y = g - C \: A^{-1} f
89 * \quad \Rightarrow \quad Sy = g'
90 * @f]
91 * with $ S = (D - C\: A^{-1} \:B) $ being the Schur complement and the
92 * modified right-hand side vector $ g' = g - C \: A^{-1} f $ arising from the
93 * condensation step. Note that for this choice of $ S $, submatrix $ D $ need
94 * not be invertible and may thus be the null matrix. Ideally $ A $ should be
95 * well-conditioned.
96 *
97 * So for any arbitrary vector $ a $, the Schur complement performs the
98 * following operation:
99 * @f[
100 * (6) \quad Sa = (D - C \: A^{-1} \: B)a
101 * @f]
102 *
103 * A typical set of steps needed the solve a linear system (1),(2) would be:
104 * 1. Define the inverse matrix @p A_inv (using inverse_operator()).
105 * 2. Define the Schur complement $ S $ (using schur_complement()).
106 * 3. Define iterative inverse matrix $ S^{-1} $ such that (6)
107 * holds. It is necessary to use a solver with a preconditioner to compute the
108 * approximate inverse operation of $ S $ since we never compute $ S $
109 * directly, but rather the result of its operation. To achieve this, one may
110 * again use the inverse_operator() in conjunction with the Schur complement
111 * that we've just constructed. Observe that the both $ S $ and its
112 * preconditioner operate over the same space as $ D $.
113 * 4. Perform pre-processing step on the RHS of (5) using
114 * condense_schur_rhs():
115 * @f[
116 * g' = g - C \: A^{-1} \: f
117 * @f]
118 * 5. Solve for $ y $ in (5):
119 * @f[
120 * y = S^{-1} g'
121 * @f]
122 * 6. Perform the post-processing step from (3) using
123 * postprocess_schur_solution():
124 * @f[
125 * x = A^{-1} (f - By)
126 * @f]
127 *
128 * An illustration of typical usage of this operator for a fully coupled
129 * system is given below.
130 * @code
131 * #include <deal.II/lac/schur_complement.h>
132 *
133 * // Given BlockMatrix K and BlockVectors d,F
134 *
135 * // Decomposition of tangent matrix
136 * const auto A = linear_operator(K.block(0,0));
137 * const auto B = linear_operator(K.block(0,1));
138 * const auto C = linear_operator(K.block(1,0));
139 * const auto D = linear_operator(K.block(1,1));
140 *
141 * // Decomposition of solution vector
142 * auto x = d.block(0);
143 * auto y = d.block(1);
144 *
145 * // Decomposition of RHS vector
146 * auto f = F.block(0);
147 * auto g = F.block(1);
148 *
149 * // Construction of inverse of Schur complement
150 * const auto prec_A = PreconditionSelector<...>(A);
151 * const auto A_inv = inverse_operator<...>(A,prec_A);
152 * const auto S = schur_complement(A_inv,B,C,D);
153 *
154 * // D and S operate on same space
155 * const auto S_prec = PreconditionSelector<...>(D);
156 * const auto S_inv = inverse_operator<...>(S,...,prec_S);
157 *
158 * // Solve reduced block system
159 * // PackagedOperation that represents the condensed form of g
160 * auto rhs = condense_schur_rhs (A_inv,C,f,g);
161 *
162 * // Solve for y
163 * y = S_inv * rhs;
164 *
165 * // Compute x using resolved solution y
166 * x = postprocess_schur_solution (A_inv,B,y,f);
167 * @endcode
168 *
169 * In the above example, the preconditioner for $ S $ was defined as the
170 * preconditioner for $ D $, which is valid since they operate on the same
171 * space. However, if $ D $ and $ S $ are too dissimilar, then this may lead
172 * to a large number of solver iterations as $ \text{prec}(D) $ is not a good
173 * approximation for $ S^{-1} $.
174 *
175 * A better preconditioner in such a case would be one that provides a more
176 * representative approximation for $ S^{-1} $. One approach is shown in
177 * step-22, where $ D $ is the null matrix and the preconditioner for $ S^{-1}
178 * $ is derived from the @ref GlossMassMatrix "mass matrix" over this space.
179 *
180 * From another viewpoint, a similar result can be achieved by first
181 * constructing an object that represents an approximation for $ S $ wherein
182 * expensive operation, namely $ A^{-1} $, is approximated. Thereafter we
183 * construct the approximate inverse operator $ \tilde{S}^{-1} $ which is then
184 * used as the preconditioner for computing $ S^{-1} $.
185 * @code
186 * // Construction of approximate inverse of Schur complement
187 * const auto A_inv_approx = linear_operator(preconditioner_A);
188 * const auto S_approx = schur_complement(A_inv_approx,B,C,D);
189 *
190 * // D and S_approx operate on same space
191 * const auto S_approx_prec = PreconditionSelector<...>(D);
192 *
193 * // Inner solver: Typically limited to few iterations
194 * // using IterationNumberControl
195 * auto S_inv_approx = inverse_operator(S_approx,...,S_approx_prec);
196 *
197 * // Construction of exact inverse of Schur complement
198 * const auto S = schur_complement(A_inv,B,C,D);
199 *
200 * // Outer solver
201 * const auto S_inv = inverse_operator(S,...,S_inv_approx);
202 *
203 * // Solve reduced block system
204 * auto rhs = condense_schur_rhs (A_inv,C,f,g);
205 *
206 * // Solve for y
207 * y = S_inv * rhs;
208 * x = postprocess_schur_solution (A_inv,B,y,f);
209 * @endcode
210 * Note that due to the construction of @c S_inv_approx and subsequently @c
211 * S_inv, there are a pair of nested iterative solvers which could
212 * collectively consume a lot of resources. Therefore care should be taken in
213 * the choices leading to the construction of the iterative inverse_operators.
214 * One might consider the use of a IterationNumberControl (or a similar
215 * mechanism) to limit the number of inner solver iterations. This controls
216 * the accuracy of the approximate inverse operation $ \tilde{S}^{-1} $ which
217 * acts only as the preconditioner for $ S^{-1} $. Furthermore, the
218 * preconditioner to $ \tilde{S}^{-1} $, which in this example is $
219 * \text{prec}(D) $, should ideally be computationally inexpensive.
220 *
221 * However, if an iterative solver based on IterationNumberControl is used as
222 * a preconditioner then the preconditioning operation is not a linear
223 * operation. Here a flexible solver like SolverFGMRES (flexible GMRES) is
224 * best employed as an outer solver in order to deal with the variable
225 * behavior of the preconditioner. Otherwise the iterative solver can
226 * stagnate somewhere near the tolerance of the preconditioner or generally
227 * behave erratically. Alternatively, using a ReductionControl would ensure
228 * that the preconditioner always solves to the same tolerance, thereby
229 * rendering its behavior constant.
230 *
231 * Further examples of this functionality can be found in the test-suite, such
232 * as <code>tests/lac/schur_complement_01.cc</code>. The solution of a
233 * multi-component problem (namely step-22) using the schur_complement can be
234 * found in <code>tests/lac/schur_complement_03.cc</code>.
235 *
236 * @see
237 * @ref GlossBlockLA "Block (linear algebra)"
238 *
239 * @ingroup LAOperators
240 */
241 template <typename Range_1,
242 typename Domain_1,
243 typename Range_2,
244 typename Domain_2,
245 typename Payload>
246 LinearOperator<Range_2, Domain_2, Payload>
247 schur_complement(const LinearOperator<Domain_1, Range_1, Payload> &A_inv,
248 const LinearOperator<Range_1, Domain_2, Payload> &B,
249 const LinearOperator<Range_2, Domain_1, Payload> &C,
250 const LinearOperator<Range_2, Domain_2, Payload> &D)
251 {
252 // We return the result of the compound LinearOperator
253 // directly, so as to ensure that the underlying Payload
254 // definition aligns with the operations expressed here.
255 // All of the memory allocations etc. are taken care of
256 // internally.
257 if (D.is_null_operator == false)
258 return D - C * A_inv * B;
259 else
260 return -1.0 * C * A_inv * B;
261 }
262
263 /** @} */
264
265
266 /**
267 * @name Creation of PackagedOperation objects related to the Schur Complement
268 */
269 /** @{ */
270
271 /**
272 * @relatesalso PackagedOperation
273 *
274 * For the system of equations
275 * @f{eqnarray*}{
276 * Ax + By &=& f \\
277 * Cx + Dy &=& g \quad ,
278 * @f}
279 * this operation performs the pre-processing (condensation) step on the RHS
280 * subvector @p g so that the Schur complement can be used to solve this
281 * system of equations. More specifically, it produces an object that
282 * represents the condensed form of the subvector @p g, namely
283 * @f[
284 * g' = g - C \: A^{-1} \: f
285 * @f]
286 *
287 * @see
288 * @ref GlossBlockLA "Block (linear algebra)"
289 *
290 * @ingroup LAOperators
291 */
292 template <typename Range_1,
293 typename Domain_1,
294 typename Range_2,
295 typename Payload>
296 PackagedOperation<Range_2>
297 condense_schur_rhs(const LinearOperator<Range_1, Domain_1, Payload> &A_inv,
298 const LinearOperator<Range_2, Domain_1, Payload> &C,
299 const Range_1 &f,
300 const Range_2 &g)
301 {
302 // We return the result of the compound PackagedOperation
303 // directly, so as to ensure that the underlying Payload
304 // definition aligns with the operations expressed here.
305 // All of the memory allocations etc. are taken care of
306 // internally.
307 return g - C * A_inv * f;
308 }
309
310 /**
311 * @relatesalso PackagedOperation
312 *
313 * For the system of equations
314 * @f{eqnarray*}{
315 * Ax + By &=& f \\
316 * Cx + Dy &=& g \quad ,
317 * @f}
318 * this operation performs the post-processing step of the Schur complement to
319 * solve for the second subvector @p x once subvector @p y is known, with the
320 * result that
321 * @f[
322 * x = A^{-1}(f - By)
323 * @f]
324 *
325 * @see
326 * @ref GlossBlockLA "Block (linear algebra)"
327 *
328 * @ingroup LAOperators
329 */
330 template <typename Range_1,
331 typename Domain_1,
332 typename Domain_2,
333 typename Payload>
334 PackagedOperation<Domain_1>
335 postprocess_schur_solution(
336 const LinearOperator<Range_1, Domain_1, Payload> &A_inv,
337 const LinearOperator<Range_1, Domain_2, Payload> &B,
338 const Domain_2 &y,
339 const Range_1 &f)
340 {
341 // We return the result of the compound PackagedOperation
342 // directly, so as to ensure that the underlying Payload
343 // definition aligns with the operations expressed here.
344 // All of the memory allocations etc. are taken care of
345 // internally.
346 return A_inv * (f - B * y);
347 }
348
349 /** @} */
350
351 DEAL_II_NAMESPACE_CLOSE
352
353 #endif