| 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 |