Debian Codegraph @

include/deal.II/lac/lapack_full_matrix.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_lapack_full_matrix_h
16 #define dealii_lapack_full_matrix_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/mutex.h>
22 #include <deal.II/base/observer_pointer.h>
23 #include <deal.II/base/table.h>
24
25 #include <deal.II/lac/lapack_support.h>
26 #include <deal.II/lac/vector_memory.h>
27
28 #include <complex>
29 #include <memory>
30 #include <vector>
31
32 DEAL_II_NAMESPACE_OPEN
33
34 // forward declarations
35 #ifndef DOXYGEN
36 template <typename number>
37 class Vector;
38 template <typename number>
39 class BlockVector;
40 template <typename number>
41 class FullMatrix;
42 template <typename number>
43 class SparseMatrix;
44 #endif
45
46 /**
47 * A variant of FullMatrix using LAPACK functions wherever possible. In order
48 * to do this, the matrix is stored in transposed order. The element access
49 * functions hide this fact by reverting the transposition.
50 *
51 * @note In order to perform LAPACK functions, the class contains a lot of
52 * auxiliary data in the private section. The names of these data vectors are
53 * usually the names chosen for the arguments in the LAPACK documentation.
54 *
55 * @ingroup Matrix1
56 */
57 template <typename number>
58 class LAPACKFullMatrix : public TransposeTable<number>
59 {
60 public:
61 /**
62 * Declare type for container size.
63 */
64 using size_type = std::make_unsigned_t<types::blas_int>;
65
66 /**
67 * Constructor. Initialize the matrix as a square matrix with dimension
68 * @p size.
69 *
70 * In order to avoid the implicit conversion of integers and other types to
71 * a matrix, this constructor is declared <tt>explicit</tt>.
72 *
73 * By default, no memory is allocated.
74 */
75 explicit LAPACKFullMatrix(const size_type size = 0);
76
77 /**
78 * Constructor. Initialize the matrix as a rectangular matrix $\rm{rows}
79 * \times \rm{cols}$.
80 */
81 LAPACKFullMatrix(const size_type rows, const size_type cols);
82
83 /**
84 * Copy constructor. This constructor does a deep copy of the matrix.
85 * Therefore, it poses a possible efficiency problem, if for example,
86 * function arguments are passed by value rather than by reference.
87 * Unfortunately, we can't mark this copy constructor <tt>explicit</tt>,
88 * since that prevents the use of this class in containers, such as
89 * <code>std::vector</code>. The responsibility to check performance of
90 * programs must therefore remain with the user of this class.
91 */
92 LAPACKFullMatrix(const LAPACKFullMatrix &);
93
94 /**
95 * Assignment operator.
96 */
97 LAPACKFullMatrix<number> &
98 operator=(const LAPACKFullMatrix<number> &);
99
100 /**
101 * Assignment operator from a regular FullMatrix.
102 *
103 * @note Since LAPACK expects matrices in transposed order, this
104 * transposition is included here.
105 */
106 template <typename number2>
107 LAPACKFullMatrix<number> &
108 operator=(const FullMatrix<number2> &);
109
110 /**
111 * Assignment operator from a regular SparseMatrix.
112 *
113 * @note Since LAPACK expects matrices in transposed order, this
114 * transposition is included here.
115 */
116 template <typename number2>
117 LAPACKFullMatrix<number> &
118 operator=(const SparseMatrix<number2> &);
119
120 /**
121 * This operator assigns a scalar to a matrix. To avoid confusion with
122 * constructors, zero (when cast to the @p number type) is the only
123 * value allowed for @p d.
124 */
125 LAPACKFullMatrix<number> &
126 operator=(const number d);
127
128 /**
129 * This operator multiplies all entries by a fixed @p factor.
130 */
131 LAPACKFullMatrix<number> &
132 operator*=(const number factor);
133
134 /**
135 * This operator divides all entries by a fixed @p factor.
136 */
137 LAPACKFullMatrix<number> &
138 operator/=(const number factor);
139
140 /**
141 * Set a particular entry of the matrix to a @p value.
142 * Thus, calling <code>A.set(1,2,3.141);</code> is entirely equivalent to the
143 * operation <code>A(1,2) = 3.141;</code>. This function exists for
144 * compatibility with the various sparse matrix objects.
145 *
146 * @param i The row index of the element to be set.
147 * @param j The column index of the element to be set.
148 * @param value The value to be written into the element.
149 */
150 void
151 set(const size_type i, const size_type j, const number value);
152
153 /**
154 * Simple addition of a scaled matrix, i.e. $\mathbf A \mathrel{+}= a \,
155 * \mathbf B$.
156 */
157 void
158 add(const number a, const LAPACKFullMatrix<number> &B);
159
160 /**
161 * Perform a rank-1 update of a symmetric matrix
162 * $ \mathbf A \leftarrow \mathbf A + a \, \mathbf v \mathbf v^T $.
163 *
164 * This function also works for Cholesky factorization.
165 * In that case, updating ($a>0$) is
166 * performed via Givens rotations, whereas downdating ($a<0$) via hyperbolic
167 * rotations. Note that the latter case might lead to a negative definite
168 * matrix in which case the error will be thrown (because Cholesky
169 * factorizations are only valid for symmetric and positive definite
170 * matrices).
171 */
172 void
173 rank1_update(const number a, const Vector<number> &v);
174
175 /**
176 * Apply <a href="https://en.wikipedia.org/wiki/Givens_rotation">Givens
177 * rotation</a>
178 * @p csr (a triplet of cosine, sine and radius, see
179 * Utilities::LinearAlgebra::givens_rotation() for the definition of the
180 * rotation matrix $\mathbf G$)
181 * to this matrix in the plane spanned by the @p i'th and @p k'th unit vectors.
182 * If @p left is <code>true</code>, the rotation is applied from left
183 * $\mathbf A \leftarrow \mathbf G \mathbf A$
184 * and only rows @p i and @p k are affected.
185 * Otherwise, transpose of the rotation matrix is applied from right
186 * $\mathbf A \leftarrow \mathbf A \mathbf G^T$
187 * and only columns @p i and @p k are affected.
188 */
189 void
190 apply_givens_rotation(const std::array<number, 3> &csr,
191 const size_type i,
192 const size_type k,
193 const bool left = true);
194
195 /**
196 * Assignment from different matrix classes, performing the usual conversion
197 * to the transposed format expected by LAPACK. This assignment operator
198 * uses iterators of the typename MatrixType. Therefore, sparse matrices are
199 * possible sources.
200 */
201 template <typename MatrixType>
202 void
203 copy_from(const MatrixType &);
204
205 /**
206 * Regenerate the current matrix by one that has the same properties as if
207 * it were created by the constructor of this class with the same argument
208 * list as this present function.
209 */
210 void
211 reinit(const size_type size);
212
213 /**
214 * Same as above but will preserve the values of matrix upon resizing.
215 * The original values
216 * of the matrix are kept on increasing the size
217 * \f[
218 * \mathbf A \rightarrow
219 * \left(
220 * \begin{array}{cc}
221 * \mathbf A & \mathbf 0 \\
222 * \mathbf 0 & \mathbf 0
223 * \end{array}
224 * \right)
225 * \f]
226 * Whereas if the new size is smaller, the matrix will contain the upper left
227 * block of the original one \f[ \left( \begin{array}{cc}
228 * \mathbf A_{11} & \mathbf A_{12} \\
229 * \mathbf A_{21} & \mathbf A_{22}
230 * \end{array}
231 * \right)
232 * \rightarrow \mathbf A_{11}
233 * \f]
234 */
235 void
236 grow_or_shrink(const size_type size);
237
238 /**
239 * Remove row @p row and column @p col from the matrix.
240 * \f[
241 * \left(
242 * \begin{array}{ccc}
243 * \mathbf A_{11} & \mathbf a_{12} & \mathbf A_{13} \\
244 * \mathbf a_{21}^T & a_{22} & \mathbf a_{23}^T \\
245 * \mathbf A_{31} & \mathbf a_{32} & \mathbf A_{33}
246 * \end{array}
247 * \right)
248 * \rightarrow
249 * \left(
250 * \begin{array}{cc}
251 * \mathbf A_{11} & \mathbf A_{13} \\
252 * \mathbf A_{31} & \mathbf A_{33}
253 * \end{array}
254 * \right)
255 * \f]
256 */
257 void
258 remove_row_and_column(const size_type row, const size_type col);
259
260 /**
261 * Regenerate the current matrix by one that has the same properties as if
262 * it were created by the constructor of this class with the same argument
263 * list as this present function.
264 */
265 void
266 reinit(const size_type rows, const size_type cols);
267
268 /**
269 * Assign @p property to this matrix.
270 */
271 void
272 set_property(const LAPACKSupport::Property property);
273
274 /**
275 * Return the dimension of the codomain (or range) space.
276 *
277 * @note The matrix is of dimension $m \times n$.
278 */
279 size_type
280 m() const;
281
282 /**
283 * Return the dimension of the domain space.
284 *
285 * @note The matrix is of dimension $m \times n$.
286 */
287 size_type
288 n() const;
289
290 /**
291 * Fill rectangular block.
292 *
293 * A rectangular block of the matrix <tt>src</tt> is copied into
294 * <tt>this</tt>. The upper left corner of the block being copied is
295 * <tt>(src_offset_i,src_offset_j)</tt>. The upper left corner of the
296 * copied block is <tt>(dst_offset_i,dst_offset_j)</tt>. The size of the
297 * rectangular block being copied is the maximum size possible, determined
298 * either by the size of <tt>this</tt> or <tt>src</tt>.
299 *
300 * The final two arguments allow to enter a multiple of the source or its
301 * transpose.
302 */
303 template <typename MatrixType>
304 void
305 fill(const MatrixType &src,
306 const size_type dst_offset_i = 0,
307 const size_type dst_offset_j = 0,
308 const size_type src_offset_i = 0,
309 const size_type src_offset_j = 0,
310 const number factor = 1.,
311 const bool transpose = false);
312
313
314 /**
315 * Matrix-vector-multiplication.
316 *
317 * Depending on previous transformations recorded in #state, the result of
318 * this function is one of
319 * <ul>
320 * <li> If #state is LAPACKSupport::matrix or LAPACKSupport::inverse_matrix,
321 * this will be a regular matrix vector product using LAPACK gemv().
322 * <li> If #state is LAPACKSupport::svd or LAPACKSupport::inverse_svd, this
323 * function first multiplies with the right transformation matrix, then with
324 * the diagonal matrix of singular values or their reciprocal values, and
325 * finally with the left transformation matrix.
326 * </ul>
327 *
328 * The optional parameter @p adding determines, whether the result is
329 * stored in the vector
330 * $\mathbf w = \mathbf A \cdot \mathbf v$
331 * or added to it
332 * $\mathbf w \mathrel{+}= \mathbf A \cdot \mathbf v$.
333 *
334 * @note Source and destination must not be the same vector.
335 *
336 * @note The template with @p number2 only exists for compile-time
337 * compatibility with FullMatrix. Only the case @p number2 = @p number is
338 * implemented due to limitations in the underlying LAPACK interface. All
339 * other variants throw an error upon invocation.
340 */
341 template <typename number2>
342 void
343 vmult(Vector<number2> &w,
344 const Vector<number2> &v,
345 const bool adding = false) const;
346
347 /**
348 * Specialization of above function for compatible Vector::value_type.
349 */
350 void
351 vmult(Vector<number> &w,
352 const Vector<number> &v,
353 const bool adding = false) const;
354
355 /**
356 * Adding Matrix-vector-multiplication $\mathbf w \mathrel{+}= \mathbf A \cdot
357 * \mathbf v$.
358 *
359 * See the documentation of vmult() for details on the implementation.
360 */
361 template <typename number2>
362 void
363 vmult_add(Vector<number2> &w, const Vector<number2> &v) const;
364
365 /**
366 * Specialization of above function for compatible Vector::value_type.
367 */
368 void
369 vmult_add(Vector<number> &w, const Vector<number> &v) const;
370
371 /**
372 * Transpose matrix-vector-multiplication.
373 *
374 * The optional parameter @p adding determines, whether the result is
375 * stored in the vector
376 * $\mathbf w = \mathbf A^T \cdot \mathbf v$
377 * or added to it
378 * $\mathbf w \mathrel{+}= \mathbf A^T \cdot \mathbf v$.
379 *
380 * See the documentation of vmult() for details on the implementation.
381 */
382 template <typename number2>
383 void
384 Tvmult(Vector<number2> &w,
385 const Vector<number2> &v,
386 const bool adding = false) const;
387
388 /**
389 * Specialization of above function for compatible Vector::value_type.
390 */
391 void
392 Tvmult(Vector<number> &w,
393 const Vector<number> &v,
394 const bool adding = false) const;
395
396 /**
397 * Adding transpose matrix-vector-multiplication $\mathbf w \mathrel{+}=
398 * \mathbf A^T \cdot \mathbf v$.
399 *
400 * See the documentation of vmult() for details on the implementation.
401 */
402 template <typename number2>
403 void
404 Tvmult_add(Vector<number2> &w, const Vector<number2> &v) const;
405
406 /**
407 * Specialization of above function for compatible Vector::value_type.
408 */
409 void
410 Tvmult_add(Vector<number> &w, const Vector<number> &v) const;
411
412
413 /**
414 * Matrix-matrix-multiplication.
415 *
416 * The optional parameter @p adding determines, whether the result is
417 * stored in the matrix
418 * $\mathbf C = \mathbf A \cdot \mathbf B$
419 * or added to it
420 * $\mathbf C \mathrel{+}= \mathbf A \cdot \mathbf B$.
421 *
422 * @note It is assumed that @p A and @p B have compatible sizes and that
423 * @p C already has the right size.
424 *
425 * @p This function uses the BLAS function Xgemm.
426 */
427 void
428 mmult(LAPACKFullMatrix<number> &C,
429 const LAPACKFullMatrix<number> &B,
430 const bool adding = false) const;
431
432 /**
433 * Same as before, but stores the result in a FullMatrix, not in a
434 * LAPACKFullMatrix.
435 */
436 void
437 mmult(FullMatrix<number> &C,
438 const LAPACKFullMatrix<number> &B,
439 const bool adding = false) const;
440
441 /**
442 * Matrix-matrix-multiplication using transpose of <tt>this</tt>.
443 *
444 * The optional parameter @p adding determines, whether the result is
445 * stored in the matrix
446 * $\mathbf C = \mathbf A^T \cdot \mathbf B$
447 * or added to it
448 * $\mathbf C \mathrel{+}= \mathbf A^T \cdot \mathbf B$.
449 *
450 * @note It is assumed that @p A and @p B have compatible sizes and that
451 * @p C already has the right size.
452 *
453 * @note This function uses the BLAS function Xgemm.
454 */
455 void
456 Tmmult(LAPACKFullMatrix<number> &C,
457 const LAPACKFullMatrix<number> &B,
458 const bool adding = false) const;
459
460 /**
461 * Same as before, but stores the result in a FullMatrix, not in a
462 * LAPACKFullMatrix.
463 */
464 void
465 Tmmult(FullMatrix<number> &C,
466 const LAPACKFullMatrix<number> &B,
467 const bool adding = false) const;
468
469 /**
470 * Matrix-matrix-multiplication using transpose of <tt>this</tt> and a
471 * diagonal vector @p V.
472 *
473 * If the <code>adding=false</code> then the result is stored in the matrix
474 * $\mathbf C = \mathbf A^T \cdot \rm{diag}(\mathbf V) \cdot \mathbf B$
475 * otherwise it is added $\mathbf C \mathrel{+}= \mathbf A^T \cdot
476 * \rm{diag}(\mathbf V) \cdot \mathbf B$.
477 *
478 * @note It is assumed that @p A, @p B and @p V have compatible sizes and that
479 * @p C already has the right size.
480 *
481 * @note This function is not provided by LAPACK. The function first forms
482 * $\rm{diag}(\mathbf V) \cdot \mathbf B$ product and then uses the Xgemm
483 * function.
484 */
485 void
486 Tmmult(LAPACKFullMatrix<number> &C,
487 const LAPACKFullMatrix<number> &B,
488 const Vector<number> &V,
489 const bool adding = false) const;
490
491 /**
492 * Matrix-matrix-multiplication using transpose of @p B.
493 *
494 * The optional parameter @p adding determines, whether the result is
495 * stored in the matrix
496 * $\mathbf C = \mathbf A \cdot \mathbf B^T$
497 * or added to it
498 * $\mathbf C \mathrel{+}= \mathbf A \cdot \mathbf B^T$.
499 *
500 * @note It is assumed that @p A and @p B have compatible sizes and that
501 * @p C already has the right size.
502 *
503 * @note This function uses the BLAS function Xgemm.
504 */
505 void
506 mTmult(LAPACKFullMatrix<number> &C,
507 const LAPACKFullMatrix<number> &B,
508 const bool adding = false) const;
509
510 /**
511 * Same as before, but stores the result in a FullMatrix, not in a
512 * LAPACKFullMatrix.
513 */
514 void
515 mTmult(FullMatrix<number> &C,
516 const LAPACKFullMatrix<number> &B,
517 const bool adding = false) const;
518
519 /**
520 * Matrix-matrix-multiplication using transpose of <tt>this</tt> and
521 * @p B.
522 *
523 * The optional parameter @p adding determines, whether the result is
524 * stored in the matrix
525 * $\mathbf C = \mathbf A^T \cdot \mathbf B^T$
526 * or added to it
527 * $\mathbf C \mathrel{+}= \mathbf A^T \cdot \mathbf B^T$.
528 *
529 * @note It is assumed that @p A and @p B have compatible sizes and that
530 * @p C already has the right size.
531 *
532 * @note This function uses the BLAS function Xgemm.
533 */
534 void
535 TmTmult(LAPACKFullMatrix<number> &C,
536 const LAPACKFullMatrix<number> &B,
537 const bool adding = false) const;
538
539 /**
540 * Same as before, but stores the result in a FullMatrix, not in a
541 * LAPACKFullMatrix.
542 */
543 void
544 TmTmult(FullMatrix<number> &C,
545 const LAPACKFullMatrix<number> &B,
546 const bool adding = false) const;
547
548 /**
549 * Performs out-place transposition.
550 * Matrix @p B should be appropriately sized.
551 *
552 * @note for complex number types, conjugate transpose will be performed.
553 *
554 * @note If deal.II is configured with Intel-MKL, `mkl_?omatcopy` will be used,
555 * otherwise transposition is done element by element.
556 */
557 void
558 transpose(LAPACKFullMatrix<number> &B) const;
559
560 /**
561 * Scale rows of this matrix by @p V . This is equivalent to premultiplication
562 * with a diagonal matrix $\mathbf A\leftarrow {\rm diag}(\mathbf V)\mathbf
563 * A$.
564 */
565 void
566 scale_rows(const Vector<number> &V);
567
568 /**
569 * Compute the LU factorization of the matrix using LAPACK function Xgetrf.
570 */
571 void
572 compute_lu_factorization();
573
574 /**
575 * Compute the Cholesky factorization of the matrix using LAPACK function
576 * Xpotrf.
577 *
578 * @note The factorization is stored in the lower-triangular part of the matrix.
579 */
580 void
581 compute_cholesky_factorization();
582
583 /**
584 * Estimate the reciprocal of the condition number $1/k(\mathbf A)$ in $L_1$
585 * norm ($1/(||\mathbf A||_1 \, ||\mathbf A^{-1}||_1)$) of a symmetric
586 * positive definite matrix using Cholesky factorization. This function can
587 * only be called if the matrix is already factorized.
588 *
589 * @note The condition number $k(\mathbf A)$ can be used to estimate the numerical
590 * error related to the matrix inversion or the solution of the
591 * system of linear algebraic equations as
592 * <code>error = std::numeric_limits<Number>::epsilon * k</code>.
593 * Alternatively one can get the number of accurate digits
594 * <code>std::floor(std::log10(k))</code>.
595 *
596 * @note The function computes reciprocal of the condition number to
597 * avoid possible overflow if the matrix is nearly singular.
598 *
599 * @param[in] l1_norm Is the $L_1$ norm of the matrix before calling Cholesky
600 * factorization. It can be obtained by calling l1_norm().
601 */
602 number
603 reciprocal_condition_number(const number l1_norm) const;
604
605 /**
606 * Estimate the reciprocal of the condition number $1/k(\mathbf A)$ in $L_1$
607 * norm for triangular matrices. The matrix has to have the
608 * LAPACKSupport::Property set to either
609 * LAPACKSupport::Property::upper_triangular or
610 * LAPACKSupport::Property::lower_triangular, see set_property().
611 */
612 number
613 reciprocal_condition_number() const;
614
615 /**
616 * Compute the determinant of a matrix. As it requires the LU factorization of
617 * the matrix, this function can only be called after
618 * compute_lu_factorization() has been called.
619 */
620 number
621 determinant() const;
622
623 /**
624 * Compute $L_1$ norm.
625 */
626 number
627 l1_norm() const;
628
629 /**
630 * Compute $L_\infty$ norm.
631 */
632 number
633 linfty_norm() const;
634
635 /**
636 * Compute Frobenius norm
637 */
638 number
639 frobenius_norm() const;
640
641 /**
642 * Compute trace of the matrix, i.e. the sum of the diagonal values.
643 * Obviously, the matrix needs to be quadratic for this function.
644 */
645 number
646 trace() const;
647
648 /**
649 * Invert the matrix by first computing an LU/Cholesky factorization with the
650 * LAPACK function Xgetrf/Xpotrf and then building the actual inverse using
651 * Xgetri/Xpotri.
652 */
653 void
654 invert();
655
656 /**
657 * Solve the linear system with right hand side @p v and put the solution
658 * back to @p v. The matrix should be either triangular or LU/Cholesky
659 * factorization should be previously computed.
660 *
661 * The flag transposed indicates whether the solution of the transposed
662 * system is to be performed.
663 */
664 void
665 solve(Vector<number> &v, const bool transposed = false) const;
666
667 /**
668 * Same as above but for multiple right hand sides (as many as there
669 * are columns in the matrix @p B).
670 */
671 void
672 solve(LAPACKFullMatrix<number> &B, const bool transposed = false) const;
673
674 /**
675 * Compute eigenvalues of the matrix. After this routine has been called,
676 * eigenvalues can be retrieved using the eigenvalue() function. The matrix
677 * itself will be LAPACKSupport::unusable after this operation.
678 *
679 * The optional arguments allow to compute left and right eigenvectors as
680 * well.
681 *
682 * Note that the function does not return the computed eigenvalues right
683 * away since that involves copying data around between the output arrays of
684 * the LAPACK functions and any return array. This is often unnecessary
685 * since one may not be interested in all eigenvalues at once, but for
686 * example only the extreme ones. In that case, it is cheaper to just have
687 * this function compute the eigenvalues and have a separate function that
688 * returns whatever eigenvalue is requested.
689 *
690 * @note Calls the LAPACK function Xgeev.
691 */
692 void
693 compute_eigenvalues(const bool right_eigenvectors = false,
694 const bool left_eigenvectors = false);
695
696 /**
697 * Compute eigenvalues and eigenvectors of a real symmetric matrix. Only
698 * eigenvalues in the interval $(\rm{lower\_bound}, \rm{upper\_bound}]$ are
699 * computed with the absolute tolerance $\rm abs\_accuracy$. An approximate
700 * eigenvalue is accepted as converged when it is determined to lie in an
701 * interval $[a,b]$ of width less than or equal to $\rm{abs\_accuracy} + eps *
702 * \rm{max}(|a|,|b|)$, where $eps$ is the machine precision. If
703 * $\rm{abs\_accuracy}$ is less than or equal to zero, then
704 * $eps\,|\mathbf{T}|_1$ will be used in its place, where $|\mathbf{T}|_1$ is
705 * the 1-norm of the tridiagonal matrix obtained by reducing $\mathbf A$ to
706 * tridiagonal form. Eigenvalues will be computed most accurately when
707 * $\rm{abs\_accuracy}$ is set to twice the underflow threshold, not zero.
708 * After this routine has been called, all eigenvalues in $(\rm{lower\_bound},
709 * \rm{upper\_bound}]$ will be stored in eigenvalues and the corresponding
710 * eigenvectors will be stored in the columns of eigenvectors, whose dimension
711 * is set accordingly.
712 *
713 * @note Calls the LAPACK function Xsyevx.
714 */
715 void
716 compute_eigenvalues_symmetric(const number lower_bound,
717 const number upper_bound,
718 const number abs_accuracy,
719 Vector<number> &eigenvalues,
720 FullMatrix<number> &eigenvectors);
721
722 /**
723 * Compute generalized eigenvalues and eigenvectors of a real generalized
724 * symmetric eigenproblem of the form
725 * - itype = 1: $\mathbf A \cdot \mathbf x=\lambda \mathbf B \cdot \mathbf x$
726 * - itype = 2: $\mathbf A \cdot \mathbf B \cdot \mathbf x=\lambda \mathbf x$
727 * - itype = 3: $\mathbf B \cdot \mathbf A \cdot \mathbf x=\lambda \mathbf x$
728 *
729 * where $\mathbf A$ is this matrix. $\mathbf A$
730 * and $\mathbf B$ are assumed to be symmetric, and $\mathbf B$ has to be
731 * positive definite. Only eigenvalues in the interval $(\rm{lower\_bound},
732 * \rm{upper\_bound}]$ are computed with the absolute tolerance
733 * $\rm{abs\_accuracy}$. An approximate eigenvalue is accepted as converged
734 * when it is determined to lie in an interval $[a,b]$ of width less than or
735 * equal to $\rm{abs\_accuracy} + eps * \rm{max}( |a|,|b| )$, where $eps$ is
736 * the machine precision. If $\rm{abs\_accuracy}$ is less than or equal to
737 * zero, then $eps \, |\mathbf{T}|_1$ will be used in its place, where
738 * $|\mathbf{T}|_1$ is the 1-norm of the tridiagonal matrix obtained by
739 * reducing $\mathbf A$ to tridiagonal form. Eigenvalues will be computed most
740 * accurately when $\rm{abs\_accuracy}$ is set to twice the underflow
741 * threshold, not zero. After this routine has been called, all eigenvalues in
742 * $(\rm{lower\_bound}, \rm{upper\_bound}]$ will be stored in eigenvalues and
743 * the corresponding eigenvectors will be stored in eigenvectors, whose
744 * dimension is set accordingly.
745 *
746 * @note Calls the LAPACK function Xsygvx.
747 */
748 void
749 compute_generalized_eigenvalues_symmetric(
750 LAPACKFullMatrix<number> &B,
751 const number lower_bound,
752 const number upper_bound,
753 const number abs_accuracy,
754 Vector<number> &eigenvalues,
755 std::vector<Vector<number>> &eigenvectors,
756 const types::blas_int itype = 1);
757
758 /**
759 * Same as the other compute_generalized_eigenvalues_symmetric function
760 * except that all eigenvalues are computed and the tolerance is set
761 * automatically. Note that this function does not return the computed
762 * eigenvalues right away since that involves copying data around between
763 * the output arrays of the LAPACK functions and any return array. This is
764 * often unnecessary since one may not be interested in all eigenvalues at
765 * once, but for example only the extreme ones. In that case, it is cheaper
766 * to just have this function compute the eigenvalues and have a separate
767 * function that returns whatever eigenvalue is requested. Eigenvalues can
768 * be retrieved using the eigenvalue() function. The number of computed
769 * eigenvectors is equal to `eigenvectors.size()`.
770 *
771 * @note Calls the LAPACK function Xsygv.
772 */
773 void
774 compute_generalized_eigenvalues_symmetric(
775 LAPACKFullMatrix<number> &B,
776 std::vector<Vector<number>> &eigenvectors,
777 const types::blas_int itype = 1);
778
779 /**
780 * Compute the singular value decomposition of the matrix using LAPACK
781 * function Xgesdd.
782 *
783 * Requires that the #state is LAPACKSupport::matrix, fills the data members
784 * #wr, #svd_u, and #svd_vt, and leaves the object in the #state
785 * LAPACKSupport::svd.
786 *
787 * The singular value decomposition factorizes the provided matrix (A) into
788 * three parts: U, sigma, and the transpose of V (V^T), such that A = U sigma
789 * V^T. Sigma is a MxN matrix which contains the singular values of A on
790 * the diagonal while all the other elements are zero. U is a MxM orthogonal
791 * matrix containing the left singular vectors corresponding to the singular
792 * values of A. V is a NxN orthonal matrix containing the right singular
793 * vectors corresponding the singular values of A.
794 *
795 * Note that the variable #svd_vt contains the transpose of V and can be
796 * accessed by get_svd_vt(), while U is accessed with get_svd_u().
797 */
798 void
799 compute_svd();
800
801 /**
802 * Compute the inverse of the matrix by singular value decomposition.
803 *
804 * Requires that #state is either LAPACKSupport::matrix or
805 * LAPACKSupport::svd. In the first case, this function calls compute_svd().
806 * After this function, the object will have the #state
807 * LAPACKSupport::inverse_svd.
808 *
809 * For a singular value decomposition, the inverse is simply computed by
810 * replacing all singular values by their reciprocal values. If the matrix
811 * does not have maximal rank, singular values 0 are not touched, thus
812 * computing the minimal norm right inverse of the matrix.
813 *
814 * The parameter @p threshold determines, when a singular value should
815 * be considered zero. It is the ratio of the smallest to the largest
816 * nonzero singular value $s_{max}$. Thus, the inverses of all
817 * singular values less than $s_{max}/\rm{threshold}$ will
818 * be set to zero.
819 */
820 void
821 compute_inverse_svd(const double threshold = 0.);
822
823 /**
824 * Same as above but provide the size of the kernel instead of a threshold,
825 * i.e. the @p kernel_size smallest eigenvalues.
826 */
827 void
828 compute_inverse_svd_with_kernel(const unsigned int kernel_size);
829
830 /**
831 * Retrieve eigenvalue after compute_eigenvalues() was called. The return
832 * type is always a complex number: In case the underlying matrix is
833 * real-valued, the type `std::complex<number>` is returned, whereas
834 * `number` is returned for complex numbers.
835 */
836 std::complex<typename numbers::NumberTraits<number>::real_type>
837 eigenvalue(const size_type i) const;
838
839 /**
840 * After a call to compute_eigenvalues(), this function returns the $n\times
841 * n$ matrix of (right) eigenvectors in a decomposition of the form $A V = V
842 * \Lambda$. Note that this function constructs the associated matrix on the
843 * fly, since LAPACK packs complex-conjugate eigenvalue/eigenvector pairs of
844 * real-valued matrices into a real-valued return matrix. This call only
845 * succeeds in case the respective flag `right_eigenvectors` in
846 * compute_eigenvalues() has been set to true.
847 */
848 FullMatrix<std::complex<typename numbers::NumberTraits<number>::real_type>>
849 get_right_eigenvectors() const;
850
851 /**
852 * Return the matrix of left eigenvectors after a call to
853 * compute_eigenvalues(), following the same principles as
854 * get_right_eigenvectors().
855 */
856 FullMatrix<std::complex<typename numbers::NumberTraits<number>::real_type>>
857 get_left_eigenvectors() const;
858
859 /**
860 * Retrieve singular values after compute_svd() or compute_inverse_svd() was
861 * called.
862 */
863 number
864 singular_value(const size_type i) const;
865
866 /**
867 * Retrieve the matrix #svd_u after compute_svd() or compute_inverse_svd() was
868 * called.
869 */
870 inline const LAPACKFullMatrix<number> &
871 get_svd_u() const;
872
873 /**
874 * Retrieve the matrix #svd_vt after compute_svd() or compute_inverse_svd()
875 * was called.
876 */
877 inline const LAPACKFullMatrix<number> &
878 get_svd_vt() const;
879
880 /**
881 * Print the matrix and allow formatting of entries.
882 *
883 * The parameters allow for a flexible setting of the output format:
884 *
885 * @param out This specifies the stream to write to.
886 *
887 * @param precision denotes the number of trailing digits.
888 *
889 * @param scientific is used to determine the number format, where
890 * <code>scientific = false</code> means fixed point notation.
891 *
892 * @param width denotes the with of each column. A zero entry for
893 * @p width makes the function compute a width, but it may be changed
894 * to a positive value, if output is crude.
895 *
896 * @param zero_string specifies a string printed for zero entries.
897 *
898 * @param denominator Multiply the whole matrix by this common
899 * denominator to get nicer numbers.
900 *
901 * @param threshold all entries with absolute value smaller than
902 * this are considered zero.
903 *
904 * @param separator specifies a string printed to separate row entries.
905 *
906 * @note The entries stored resemble a matrix only if the state is either
907 * LAPACKSupport::matrix or LAPACK::inverse_matrix. Otherwise, calling this
908 * function is not allowed.
909 */
910 void
911 print_formatted(std::ostream &out,
912 const unsigned int precision = 3,
913 const bool scientific = true,
914 const unsigned int width = 0,
915 const char *zero_string = " ",
916 const double denominator = 1.,
917 const double threshold = 0.,
918 const char *separator = " ") const;
919
920 /**
921 * Return current state after the last operation here.
922 */
923 LAPACKSupport::State
924 get_state() const;
925
926 private:
927 /**
928 * Internal function to compute various norms.
929 */
930 number
931 norm(const char type) const;
932
933 /**
934 * Since LAPACK operations notoriously change the meaning of the matrix
935 * entries, we record the current state after the last operation here.
936 */
937 LAPACKSupport::State state;
938
939 /**
940 * Additional property of the matrix which may help to select more
941 * efficient LAPACK functions.
942 */
943 LAPACKSupport::Property property;
944
945 /**
946 * The working array used for some LAPACK functions.
947 */
948 mutable std::vector<number> work;
949
950 /**
951 * Integer working array used for some LAPACK functions.
952 */
953 mutable std::vector<types::blas_int> iwork;
954
955 /**
956 * The vector storing the permutations applied for pivoting in the LU-
957 * factorization.
958 *
959 * Also used as the scratch array IWORK for LAPACK functions needing it.
960 */
961 std::vector<types::blas_int> ipiv;
962
963 /**
964 * Workspace for calculating the inverse matrix from an LU factorization.
965 */
966 std::vector<number> inv_work;
967
968 /**
969 * Real parts of eigenvalues or the singular values. Filled by
970 * compute_eigenvalues() or compute_svd().
971 */
972 std::vector<typename numbers::NumberTraits<number>::real_type> wr;
973
974 /**
975 * Imaginary parts of eigenvalues, or, in the complex scalar case, the
976 * eigenvalues themselves. Filled by compute_eigenvalues.
977 */
978 std::vector<number> wi;
979
980 /**
981 * Space where left eigenvectors can be stored.
982 */
983 std::vector<number> vl;
984
985 /**
986 * Space where right eigenvectors can be stored.
987 */
988 std::vector<number> vr;
989
990 /**
991 * The matrix $\mathbf U$ in the singular value decomposition
992 * $\mathbf U \cdot \mathbf S \cdot \mathbf V^T$.
993 */
994 std::unique_ptr<LAPACKFullMatrix<number>> svd_u;
995
996 /**
997 * The matrix $\mathbf V^T$ in the singular value decomposition
998 * $\mathbf U \cdot \mathbf S \cdot \mathbf V^T$.
999 */
1000 std::unique_ptr<LAPACKFullMatrix<number>> svd_vt;
1001
1002 /**
1003 * Thread mutex.
1004 */
1005 mutable Threads::Mutex mutex;
1006 };
1007
1008
1009
1010 /**
1011 * A preconditioner based on the LU-factorization of LAPACKFullMatrix.
1012 *
1013 * @ingroup Preconditioners
1014 */
1015 template <typename number>
1016 class PreconditionLU : public EnableObserverPointer
1017 {
1018 public:
1019 void
1020 initialize(const LAPACKFullMatrix<number> &);
1021 void
1022 initialize(const LAPACKFullMatrix<number> &, VectorMemory<Vector<number>> &);
1023 void
1024 vmult(Vector<number> &, const Vector<number> &) const;
1025 void
1026 Tvmult(Vector<number> &, const Vector<number> &) const;
1027 void
1028 vmult(BlockVector<number> &, const BlockVector<number> &) const;
1029 void
1030 Tvmult(BlockVector<number> &, const BlockVector<number> &) const;
1031
1032 private:
1033 ObserverPointer<const LAPACKFullMatrix<number>, PreconditionLU<number>>
1034 matrix;
1035 ObserverPointer<VectorMemory<Vector<number>>, PreconditionLU<number>> mem;
1036 };
1037
1038 /*---------------------- Inline functions -----------------------------------*/
1039
1040 template <typename number>
1041 inline void
1042 LAPACKFullMatrix<number>::set(const size_type i,
1043 const size_type j,
1044 const number value)
1045 {
1046 (*this)(i, j) = value;
1047 }
1048
1049
1050
1051 template <typename number>
1052 inline typename LAPACKFullMatrix<number>::size_type
1053 LAPACKFullMatrix<number>::m() const
1054 {
1055 return static_cast<size_type>(this->n_rows());
1056 }
1057
1058
1059
1060 template <typename number>
1061 inline typename LAPACKFullMatrix<number>::size_type
1062 LAPACKFullMatrix<number>::n() const
1063 {
1064 return static_cast<size_type>(this->n_cols());
1065 }
1066
1067
1068
1069 template <typename number>
1070 template <typename MatrixType>
1071 inline void
1072 LAPACKFullMatrix<number>::copy_from(const MatrixType &M)
1073 {
1074 this->reinit(M.m(), M.n());
1075
1076 // loop over the elements of the argument matrix row by row, as suggested
1077 // in the documentation of the sparse matrix iterator class, and
1078 // copy them into the current object
1079 for (size_type row = 0; row < M.m(); ++row)
1080 {
1081 const typename MatrixType::const_iterator end_row = M.end(row);
1082 for (typename MatrixType::const_iterator entry = M.begin(row);
1083 entry != end_row;
1084 ++entry)
1085 this->el(row, entry->column()) = entry->value();
1086 }
1087
1088 state = LAPACKSupport::matrix;
1089 }
1090
1091
1092
1093 template <typename number>
1094 template <typename MatrixType>
1095 inline void
1096 LAPACKFullMatrix<number>::fill(const MatrixType &M,
1097 const size_type dst_offset_i,
1098 const size_type dst_offset_j,
1099 const size_type src_offset_i,
1100 const size_type src_offset_j,
1101 const number factor,
1102 const bool transpose)
1103 {
1104 // loop over the elements of the argument matrix row by row, as suggested
1105 // in the documentation of the sparse matrix iterator class
1106 for (size_type row = src_offset_i; row < M.m(); ++row)
1107 {
1108 const typename MatrixType::const_iterator end_row = M.end(row);
1109 for (typename MatrixType::const_iterator entry = M.begin(row);
1110 entry != end_row;
1111 ++entry)
1112 {
1113 const size_type i = transpose ? entry->column() : row;
1114 const size_type j = transpose ? row : entry->column();
1115
1116 const size_type dst_i = dst_offset_i + i - src_offset_i;
1117 const size_type dst_j = dst_offset_j + j - src_offset_j;
1118 if (dst_i < this->n_rows() && dst_j < this->n_cols())
1119 (*this)(dst_i, dst_j) = factor * entry->value();
1120 }
1121 }
1122
1123 state = LAPACKSupport::matrix;
1124 }
1125
1126
1127
1128 template <typename number>
1129 template <typename number2>
1130 void
1131 LAPACKFullMatrix<number>::vmult(Vector<number2> &,
1132 const Vector<number2> &,
1133 const bool) const
1134 {
1135 Assert(false,
1136 ExcMessage("LAPACKFullMatrix<number>::vmult must be called with a "
1137 "matching Vector<double> vector type."));
1138 }
1139
1140
1141
1142 template <typename number>
1143 template <typename number2>
1144 void
1145 LAPACKFullMatrix<number>::vmult_add(Vector<number2> &,
1146 const Vector<number2> &) const
1147 {
1148 Assert(false,
1149 ExcMessage("LAPACKFullMatrix<number>::vmult_add must be called with a "
1150 "matching Vector<double> vector type."));
1151 }
1152
1153
1154
1155 template <typename number>
1156 template <typename number2>
1157 void
1158 LAPACKFullMatrix<number>::Tvmult(Vector<number2> &,
1159 const Vector<number2> &,
1160 const bool) const
1161 {
1162 Assert(false,
1163 ExcMessage("LAPACKFullMatrix<number>::Tvmult must be called with a "
1164 "matching Vector<double> vector type."));
1165 }
1166
1167
1168
1169 template <typename number>
1170 template <typename number2>
1171 void
1172 LAPACKFullMatrix<number>::Tvmult_add(Vector<number2> &,
1173 const Vector<number2> &) const
1174 {
1175 Assert(false,
1176 ExcMessage("LAPACKFullMatrix<number>::Tvmult_add must be called "
1177 "with a matching Vector<double> vector type."));
1178 }
1179
1180
1181
1182 namespace internal
1183 {
1184 namespace LAPACKFullMatrixImplementation
1185 {
1186 template <typename RealNumber>
1187 std::complex<RealNumber>
1188 pack_complex(const RealNumber &real_part, const RealNumber &imaginary_part)
1189 {
1190 return std::complex<RealNumber>(real_part, imaginary_part);
1191 }
1192
1193 // The eigenvalues in LAPACKFullMatrix with complex-valued matrices are
1194 // contained in the 'wi' array, ignoring the 'wr' array.
1195 template <typename Number>
1196 std::complex<Number>
1197 pack_complex(const Number &, const std::complex<Number> &complex_number)
1198 {
1199 return complex_number;
1200 }
1201 } // namespace LAPACKFullMatrixImplementation
1202 } // namespace internal
1203
1204
1205
1206 template <typename number>
1207 inline std::complex<typename numbers::NumberTraits<number>::real_type>
1208 LAPACKFullMatrix<number>::eigenvalue(const size_type i) const
1209 {
1210 Assert(state & LAPACKSupport::eigenvalues, ExcInvalidState());
1211 Assert(wr.size() == this->n_rows(), ExcInternalError());
1212 Assert(wi.size() == this->n_rows(), ExcInternalError());
1213 AssertIndexRange(i, this->n_rows());
1214
1215 return internal::LAPACKFullMatrixImplementation::pack_complex(wr[i], wi[i]);
1216 }
1217
1218
1219
1220 template <typename number>
1221 inline number
1222 LAPACKFullMatrix<number>::singular_value(const size_type i) const
1223 {
1224 Assert(state == LAPACKSupport::svd || state == LAPACKSupport::inverse_svd,
1225 LAPACKSupport::ExcState(state));
1226 AssertIndexRange(i, wr.size());
1227
1228 return wr[i];
1229 }
1230
1231
1232
1233 template <typename number>
1234 inline const LAPACKFullMatrix<number> &
1235 LAPACKFullMatrix<number>::get_svd_u() const
1236 {
1237 Assert(state == LAPACKSupport::svd || state == LAPACKSupport::inverse_svd,
1238 LAPACKSupport::ExcState(state));
1239
1240 return *svd_u;
1241 }
1242
1243
1244
1245 template <typename number>
1246 inline const LAPACKFullMatrix<number> &
1247 LAPACKFullMatrix<number>::get_svd_vt() const
1248 {
1249 Assert(state == LAPACKSupport::svd || state == LAPACKSupport::inverse_svd,
1250 LAPACKSupport::ExcState(state));
1251
1252 return *svd_vt;
1253 }
1254
1255
1256
1257 DEAL_II_NAMESPACE_CLOSE
1258
1259 #endif