1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 2005 - 2020 by the deal.II authors
4 //
5 // This file is part of the deal.II library.
6 //
7 // The deal.II library is free software; you can use it, redistribute
8 // it, and/or modify it under the terms of the GNU Lesser General
9 // Public License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
11 // The full text of the license can be found in the file LICENSE.md at
12 // the top level directory of deal.II.
13 //
14 // ---------------------------------------------------------------------
15
16 #ifndef dealii_tridiagonal_matrix_h
17 #define dealii_tridiagonal_matrix_h
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/subscriptor.h>
22
23 #include <deal.II/lac/lapack_support.h>
24
25 #include <iomanip>
26 #include <vector>
27
28 DEAL_II_NAMESPACE_OPEN
29
30 // forward declarations
31 #ifndef DOXYGEN
32 template <typename number>
33 class Vector;
34 #endif
35
36 /*! @addtogroup Matrix1
37 *@{
38 */
39
40
41 /**
42 * A quadratic tridiagonal matrix. That is, a matrix where all entries are
43 * zero, except the diagonal and the entries left and right of it.
44 *
45 * The matrix has an additional symmetric mode, in which case only the upper
46 * triangle of the matrix is stored and mirrored to the lower one for matrix
47 * vector operations.
48 *
49 * @ingroup Matrix1
50 */
51 template <typename number>
52 class TridiagonalMatrix
53 {
54 public:
55 ///@name Constructors
56 //@{
57 /**
58 * Declare type for container size.
59 */
60 using size_type = types::global_dof_index;
61
62 /**
63 * @name Constructors and initialization
64 */
65 /**
66 * Constructor generating an empty matrix of dimension <tt>n</tt>.
67 */
68 TridiagonalMatrix(size_type n = 0, bool symmetric = false);
69
70 /**
71 * Reinitialize the matrix to a new size and reset all entries to zero. The
72 * symmetry properties may be set as well.
73 */
74 void
75 reinit(size_type n, bool symmetric = false);
76
77
78 //@}
79
80 ///@name Non-modifying operators
81 //@{
82
83 /**
84 * Number of rows of this matrix. Note that the matrix is an <i>m x
85 * m</i> matrix.
86 */
87 size_type
88 m() const;
89
90 /**
91 * Number of columns of this matrix. Note that the matrix is an <i>n x
92 * n</i> matrix.
93 */
94 size_type
95 n() const;
96
97 /**
98 * Return whether the matrix contains only elements with value zero. This
99 * function is mainly for internal consistency checks and should seldom be
100 * used when not in debug mode since it uses quite some time.
101 */
102 bool
103 all_zero() const;
104
105 //@}
106
107 ///@name Element access
108 //@{
109 /**
110 * Read-only access to a value. This is restricted to the case where
111 * <i>|i-j| <= 1</i>.
112 */
113 number
114 operator()(size_type i, size_type j) const;
115
116 /**
117 * Read-write access to a value. This is restricted to the case where
118 * <i>|i-j| <= 1</i>.
119 *
120 * @note In case of symmetric storage technique, the entries <i>(i,j)</i>
121 * and <i>(j,i)</i> are identified and <b>both</b> exist. This must be taken
122 * into account if adding up is used for matrix assembling in order not to
123 * obtain doubled entries.
124 */
125 number &
126 operator()(size_type i, size_type j);
127
128 //@}
129
130 ///@name Multiplications with vectors
131 //@{
132
133 /**
134 * Matrix-vector-multiplication. Multiplies <tt>v</tt> from the right and
135 * stores the result in <tt>w</tt>.
136 *
137 * If the optional parameter <tt>adding</tt> is <tt>true</tt>, the result is
138 * added to <tt>w</tt>.
139 *
140 * Source and destination must not be the same vector.
141 */
142 void
143 vmult(Vector<number> & w,
144 const Vector<number> &v,
145 const bool adding = false) const;
146
147 /**
148 * Adding Matrix-vector-multiplication. Same as vmult() with parameter
149 * <tt>adding=true</tt>, but widely used in <tt>deal.II</tt> classes.
150 *
151 * Source and destination must not be the same vector.
152 */
153 void
154 vmult_add(Vector<number> &w, const Vector<number> &v) const;
155
156 /**
157 * Transpose matrix-vector-multiplication. Multiplies <tt>v<sup>T</sup></tt>
158 * from the left and stores the result in <tt>w</tt>.
159 *
160 * If the optional parameter <tt>adding</tt> is <tt>true</tt>, the result is
161 * added to <tt>w</tt>.
162 *
163 * Source and destination must not be the same vector.
164 */
165 void
166 Tvmult(Vector<number> & w,
167 const Vector<number> &v,
168 const bool adding = false) const;
169
170 /**
171 * Adding transpose matrix-vector-multiplication. Same as Tvmult() with
172 * parameter <tt>adding=true</tt>, but widely used in <tt>deal.II</tt>
173 * classes.
174 *
175 * Source and destination must not be the same vector.
176 */
177 void
178 Tvmult_add(Vector<number> &w, const Vector<number> &v) const;
179
180 /**
181 * Build the matrix scalar product <tt>u^T M v</tt>. This function is mostly
182 * useful when building the cellwise scalar product of two functions in the
183 * finite element context.
184 */
185 number
186 matrix_scalar_product(const Vector<number> &u, const Vector<number> &v) const;
187
188 /**
189 * Return the square of the norm of the vector <tt>v</tt> with respect to
190 * the norm induced by this matrix, i.e. <i>(v,Mv)</i>. This is useful, e.g.
191 * in the finite element context, where the <i>L<sup>2</sup></i> norm of a
192 * function equals the matrix norm with respect to the mass matrix of the
193 * vector representing the nodal values of the finite element function.
194 *
195 * Obviously, the matrix needs to be quadratic for this operation.
196 */
197 number
198 matrix_norm_square(const Vector<number> &v) const;
199
200 //@}
201
202 ///@name LAPACK operations
203 //@{
204 /**
205 * Compute the eigenvalues of the symmetric tridiagonal matrix.
206 *
207 * @note This function requires configuration of deal.II with LAPACK
208 * support. Additionally, the matrix must use symmetric storage technique.
209 */
210 void
211 compute_eigenvalues();
212 /**
213 * After calling compute_eigenvalues(), you can access each eigenvalue here.
214 */
215 number
216 eigenvalue(const size_type i) const;
217 //@}
218
219 ///@name Miscellanea
220 //@{
221 /**
222 * Output of the matrix in user-defined format.
223 */
224 template <class OutputStream>
225 void
226 print(OutputStream & s,
227 const unsigned int width = 5,
228 const unsigned int precision = 2) const;
229 //@}
230
231 private:
232 /**
233 * The diagonal entries.
234 */
235 std::vector<number> diagonal;
236 /**
237 * The entries left of the diagonal. The entry with index zero is always
238 * zero, since the first row has no entry left of the diagonal. Therefore,
239 * the length of this vector is the same as that of #diagonal.
240 *
241 * The length of this vector is zero for symmetric storage. In this case,
242 * the second element of #left is identified with the first element of
243 * #right.
244 */
245 std::vector<number> left;
246 /**
247 * The entries right of the diagonal. The last entry is always zero, since
248 * the last row has no entry right of the diagonal. Therefore, the length of
249 * this vector is the same as that of #diagonal.
250 */
251 std::vector<number> right;
252
253 /**
254 * If this flag is true, only the entries to the right of the diagonal are
255 * stored and the matrix is assumed symmetric.
256 */
257 bool is_symmetric;
258
259 /**
260 * The state of the matrix. Normally, the state is LAPACKSupport::matrix,
261 * indicating that the object can be used for regular matrix operations.
262 *
263 * See explanation of this data type for details.
264 */
265 LAPACKSupport::State state;
266 };
267
268 /**@}*/
269
270 //---------------------------------------------------------------------------
271 #ifndef DOXYGEN
272
273 template <typename number>
274 types::global_dof_index
m()275 TridiagonalMatrix<number>::m() const
276 {
277 return diagonal.size();
278 }
279
280
281
282 template <typename number>
283 types::global_dof_index
n()284 TridiagonalMatrix<number>::n() const
285 {
286 return diagonal.size();
287 }
288
289
290 template <typename number>
291 inline number
operator()292 TridiagonalMatrix<number>::operator()(size_type i, size_type j) const
293 {
294 AssertIndexRange(i, n());
295 AssertIndexRange(j, n());
296 Assert(i <= j + 1, ExcIndexRange(i, j - 1, j + 2));
297 Assert(j <= i + 1, ExcIndexRange(j, i - 1, i + 2));
298
299 if (j == i)
300 return diagonal[i];
301 if (j == i - 1)
302 {
303 if (is_symmetric)
304 return right[i - 1];
305 else
306 return left[i];
307 }
308
309 if (j == i + 1)
310 return right[i];
311
312 Assert(false, ExcInternalError());
313 return 0;
314 }
315
316
317 template <typename number>
318 inline number &
operator()319 TridiagonalMatrix<number>::operator()(size_type i, size_type j)
320 {
321 AssertIndexRange(i, n());
322 AssertIndexRange(j, n());
323 Assert(i <= j + 1, ExcIndexRange(i, j - 1, j + 2));
324 Assert(j <= i + 1, ExcIndexRange(j, i - 1, i + 2));
325
326 if (j == i)
327 return diagonal[i];
328 if (j == i - 1)
329 {
330 if (is_symmetric)
331 return right[i - 1];
332 else
333 return left[i];
334 }
335
336 if (j == i + 1)
337 return right[i];
338
339 Assert(false, ExcInternalError());
340 return diagonal[0];
341 }
342
343
344 template <typename number>
345 template <class OutputStream>
346 void
print(OutputStream & s,const unsigned int width,const unsigned int)347 TridiagonalMatrix<number>::print(OutputStream & s,
348 const unsigned int width,
349 const unsigned int) const
350 {
351 for (size_type i = 0; i < n(); ++i)
352 {
353 if (i > 0)
354 s << std::setw(width) << (*this)(i, i - 1);
355 else
356 s << std::setw(width) << "";
357
358 s << ' ' << (*this)(i, i) << ' ';
359
360 if (i < n() - 1)
361 s << std::setw(width) << (*this)(i, i + 1);
362
363 s << std::endl;
364 }
365 }
366
367
368 #endif // DOXYGEN
369
370 DEAL_II_NAMESPACE_CLOSE
371
372 #endif
373