Debian Codegraph @

include/deal.II/lac/householder.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2005 - 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_householder_h
16 #define dealii_householder_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/lac/full_matrix.h>
22
23 #include <cmath>
24 #include <vector>
25
26 DEAL_II_NAMESPACE_OPEN
27
28
29 // forward declarations
30 #ifndef DOXYGEN
31 template <typename number>
32 class Vector;
33 #endif
34
35 /**
36 * @addtogroup Matrix2
37 * @{
38 */
39
40
41 /**
42 * QR-decomposition of a full matrix.
43 *
44 * This class computes the QR-decomposition of given matrix by the
45 * Householder algorithm. Then, the function least_squares() can be
46 * used to compute the vector $x$ minimizing $\|Ax-b\|$ for a given
47 * vector $b$. The QR decomposition of $A$ is useful for this purpose
48 * because the minimizer is given by the equation
49 * $x=(A^TA)^{-1}A^Tb=(R^TQ^TQR)^{-1}R^TQ^Tb$ which is easy to compute
50 * because $Q$ is an orthogonal matrix, and consequently
51 * $Q^TQ=I$. Thus,
52 * $x=(R^TR)^{-1}R^TQ^Tb=R^{-1}R^{-T}R^TQ^Tb=R^{-1}Q^Tb$. Furthermore,
53 * $R$ is triangular, so applying $R^{-1}$ to a vector only involves a
54 * backward or forward solve.
55 *
56 *
57 * <h3>Implementation details</h3>
58 *
59 * The class does not in fact store the $Q$ and $R$ factors explicitly
60 * as matrices. It does store $R$, but the $Q$ factor is stored as the
61 * product of Householder reflections of the form $Q_i = I-v_i v_i^T$
62 * where the vectors $v_i$ are so that they can be stored in the
63 * lower-triangular part of an underlying matrix object, whereas $R$
64 * is stored in the upper triangular part.
65 *
66 * The $v_i$ vectors and the $R$ matrix now are in conflict because they
67 * both want to use the diagonal entry of the matrix, but we can only
68 * store one in these positions, of course. Consequently, the entries
69 * $(v_i)_i$ are stored separately in the `diagonal` member variable.
70 *
71 * @note Instantiations for this template are provided for <tt>@<float@> and
72 * @<double@></tt>; others can be generated in application programs (see the
73 * section on
74 * @ref Instantiations
75 * in the manual).
76 */
77 template <typename number>
78 class Householder
79 {
80 public:
81 /**
82 * Declare type of container size type.
83 */
84 using size_type = types::global_dof_index;
85
86 /**
87 * Create an empty object.
88 */
89 Householder() = default;
90
91 /**
92 * Create an object holding the QR-decomposition of the matrix $A$.
93 */
94 template <typename number2>
95 Householder(const FullMatrix<number2> &A);
96
97 /**
98 * Compute the QR-decomposition of the given matrix $A$.
99 *
100 * This overwrites any previously computed QR decomposition.
101 */
102 template <typename number2>
103 void
104 initialize(const FullMatrix<number2> &A);
105
106 /**
107 * Solve the least-squares problem for the right hand side <tt>src</tt>. The
108 * returned scalar value is the Euclidean norm of the approximation error.
109 *
110 * @arg @c dst contains the solution of the least squares problem on return.
111 *
112 * @arg @c src contains the right hand side <i>b</i> of the least squares
113 * problem. It will be changed during the algorithm and is unusable on
114 * return.
115 */
116 template <typename number2>
117 number2
118 least_squares(Vector<number2> &dst, const Vector<number2> &src) const;
119
120 /**
121 * This function does the same as the previous one, but for BlockVectors.
122 */
123 template <typename number2>
124 double
125 least_squares(BlockVector<number2> &dst,
126 const BlockVector<number2> &src) const;
127
128 /**
129 * A wrapper to least_squares(), implementing the standard MatrixType
130 * interface.
131 */
132 template <typename VectorType>
133 void
134 vmult(VectorType &dst, const VectorType &src) const;
135
136 /**
137 * A wrapper to least_squares() that implements multiplication with
138 * the transpose matrix.
139 */
140 template <typename VectorType>
141 void
142 Tvmult(VectorType &dst, const VectorType &src) const;
143
144
145 private:
146 /**
147 * Storage for the diagonal elements of the orthogonal
148 * transformation. See the class documentation for more information.
149 */
150 std::vector<number> diagonal;
151
152 /**
153 * Storage that is internally used for the Householder transformation.
154 */
155 FullMatrix<number> storage;
156 };
157
158 /** @} */
159
160 #ifndef DOXYGEN
161 /*-------------------------Inline functions -------------------------------*/
162
163 // QR-transformation cf. Stoer 1 4.8.2 (p. 191)
164
165 template <typename number>
166 template <typename number2>
167 void
168 Householder<number>::initialize(const FullMatrix<number2> &M)
169 {
170 const size_type m = M.n_rows(), n = M.n_cols();
171 storage.reinit(m, n);
172 storage.fill(M);
173 Assert(!storage.empty(), typename FullMatrix<number2>::ExcEmptyMatrix());
174 diagonal.resize(m);
175
176 // m > n, src.n() = m
177 Assert(storage.n_cols() <= storage.n_rows(),
178 ExcDimensionMismatch(storage.n_cols(), storage.n_rows()));
179
180 for (size_type j = 0; j < n; ++j)
181 {
182 number2 sigma = 0;
183 size_type i;
184 // sigma = ||v||^2
185 for (i = j; i < m; ++i)
186 sigma += storage(i, j) * storage(i, j);
187 // We are ready if the column is
188 // empty. Are we?
189 if (std::abs(sigma) < 1.e-15)
190 return;
191
192 number2 s;
193 if constexpr (numbers::NumberTraits<number2>::is_complex)
194 s = storage(j, j).real() < 0 ? std::sqrt(sigma) : -std::sqrt(sigma);
195 else
196 s = storage(j, j) < 0 ? std::sqrt(sigma) : -std::sqrt(sigma);
197 //
198 number2 beta = std::sqrt(1. / (sigma - s * storage(j, j)));
199
200 // Make column j the Householder
201 // vector, store first entry in
202 // diagonal
203 diagonal[j] = beta * (storage(j, j) - s);
204 storage(j, j) = s;
205
206 for (i = j + 1; i < m; ++i)
207 storage(i, j) *= beta;
208
209
210 // For all subsequent columns do
211 // the Householder reflection
212 for (size_type k = j + 1; k < n; ++k)
213 {
214 number2 sum = diagonal[j] * storage(j, k);
215 for (i = j + 1; i < m; ++i)
216 sum += storage(i, j) * storage(i, k);
217
218 storage(j, k) -= sum * this->diagonal[j];
219 for (i = j + 1; i < m; ++i)
220 storage(i, k) -= sum * storage(i, j);
221 }
222 }
223 }
224
225
226
227 template <typename number>
228 template <typename number2>
229 Householder<number>::Householder(const FullMatrix<number2> &M)
230 {
231 initialize(M);
232 }
233
234
235
236 template <typename number>
237 template <typename number2>
238 number2
239 Householder<number>::least_squares(Vector<number2> &dst,
240 const Vector<number2> &src) const
241 {
242 Assert(!storage.empty(), typename FullMatrix<number2>::ExcEmptyMatrix());
243 AssertDimension(dst.size(), storage.n());
244 AssertDimension(src.size(), storage.m());
245
246 const size_type m = storage.m(), n = storage.n();
247
248 Vector<number2> aux(src);
249 // m > n, m = src.n, n = dst.n
250
251 // Multiply Q_n ... Q_2 Q_1 src
252 // Where Q_i = I - v_i v_i^T
253 for (size_type j = 0; j < n; ++j)
254 {
255 // sum = v_i^T dst
256 number2 sum = diagonal[j] * aux(j);
257 for (size_type i = j + 1; i < m; ++i)
258 sum += static_cast<number2>(storage(i, j)) * aux(i);
259 // dst -= v * sum
260 aux(j) -= sum * diagonal[j];
261 for (size_type i = j + 1; i < m; ++i)
262 aux(i) -= sum * static_cast<number2>(storage(i, j));
263 }
264 // Compute norm of residual
265 number2 sum = 0.;
266 for (size_type i = n; i < m; ++i)
267 sum += aux(i) * aux(i);
268 AssertIsFinite(sum);
269
270 // Compute solution
271 storage.backward(dst, aux);
272
273 return std::sqrt(sum);
274 }
275
276
277
278 template <typename number>
279 template <typename number2>
280 double
281 Householder<number>::least_squares(BlockVector<number2> &dst,
282 const BlockVector<number2> &src) const
283 {
284 Assert(!storage.empty(), typename FullMatrix<number2>::ExcEmptyMatrix());
285 AssertDimension(dst.size(), storage.n());
286 AssertDimension(src.size(), storage.m());
287
288 const size_type m = storage.m(), n = storage.n();
289
290 BlockVector<number2> aux;
291 aux.reinit(src, true);
292 aux = src;
293 // m > n, m = src.n, n = dst.n
294
295 // Multiply Q_n ... Q_2 Q_1 src
296 // Where Q_i = I-v_i v_i^T
297 for (size_type j = 0; j < n; ++j)
298 {
299 // sum = v_i^T dst
300 number2 sum = diagonal[j] * aux(j);
301 for (size_type i = j + 1; i < m; ++i)
302 sum += storage(i, j) * aux(i);
303 // dst -= v * sum
304 aux(j) -= sum * diagonal[j];
305 for (size_type i = j + 1; i < m; ++i)
306 aux(i) -= sum * storage(i, j);
307 }
308 // Compute norm of residual
309 number2 sum = 0.;
310 for (size_type i = n; i < m; ++i)
311 sum += *aux(i) * aux(i);
312 AssertIsFinite(sum);
313
314 // backward works for Vectors only, so copy them before
315 Vector<number2> v_dst, v_aux;
316 v_dst = dst;
317 v_aux = aux;
318 // Compute solution
319 storage.backward(v_dst, v_aux);
320 // copy the result back to the BlockVector
321 dst = v_dst;
322
323 return std::sqrt(sum);
324 }
325
326
327 template <typename number>
328 template <typename VectorType>
329 void
330 Householder<number>::vmult(VectorType &dst, const VectorType &src) const
331 {
332 least_squares(dst, src);
333 }
334
335
336 template <typename number>
337 template <typename VectorType>
338 void
339 Householder<number>::Tvmult(VectorType &, const VectorType &) const
340 {
341 DEAL_II_NOT_IMPLEMENTED();
342 }
343
344
345
346 #endif // DOXYGEN
347
348 DEAL_II_NAMESPACE_CLOSE
349
350 #endif