Debian Codegraph @

include/deal.II/lac/sparse_matrix_ez.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2002 - 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_sparse_matrix_ez_h
16 #define dealii_sparse_matrix_ez_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/enable_observer_pointer.h>
22 #include <deal.II/base/exceptions.h>
23 #include <deal.II/base/numbers.h>
24 #include <deal.II/base/observer_pointer.h>
25 #include <deal.II/base/types.h>
26
27 #include <deal.II/lac/exceptions.h>
28
29 #include <vector>
30
31 DEAL_II_NAMESPACE_OPEN
32
33 // Forward declarations
34 #ifndef DOXYGEN
35 template <typename number>
36 class Vector;
37 template <typename number>
38 class FullMatrix;
39 #endif
40
41 /**
42 * @addtogroup Matrix1
43 * @{
44 */
45
46 /**
47 * Sparse matrix without sparsity pattern.
48 *
49 * Instead of using a pre-assembled sparsity pattern, this matrix builds the
50 * pattern on the fly. Filling the matrix may consume more time than for
51 * @p SparseMatrix, since large memory movements may be involved when new
52 * matrix elements are inserted somewhere in the middle of the matrix and no
53 * currently unused memory locations are available for the row into which
54 * the new entry is to be inserted. To help
55 * optimize things, an expected row-length may be provided to the
56 * constructor, as well as an increment size for rows.
57 *
58 * This class uses a storage structure that, similar to the usual sparse matrix
59 * format, only stores non-zero elements. These are stored in a single data
60 * array for the entire matrix, and are ordered by row and, within each row, by
61 * column number. A separate array describes where in the long data array each
62 * row starts and how long it is.
63 *
64 * Due to this structure, gaps may occur between rows. Whenever a new entry
65 * must be created, an attempt is made to use the gap in its row. If no gap
66 * is left, the row must be extended and all subsequent rows must be shifted
67 * backwards. This is a very expensive operation and explains the inefficiency
68 * of this data structure and why it is useful to pre-allocate a sparsity
69 * pattern as the SparseMatrix class does.
70 *
71 * This is where the optimization parameters, provided to the constructor or
72 * to the reinit() functions come in. @p default_row_length is the number of
73 * entries that will be allocated for each row on initialization (the actual
74 * length of the rows is still zero). This means, that @p default_row_length
75 * entries can be added to this row without shifting other rows. If fewer
76 * entries are added, the additional memory will of course be wasted.
77 *
78 * If the space for a row is not sufficient, then it is enlarged by
79 * @p default_increment entries. This way, subsequent rows are not shifted by
80 * single entries very often.
81 *
82 * Finally, the @p default_reserve allocates extra space at the end of the
83 * data array. This space is used whenever any row must be enlarged. It is
84 * important because otherwise not only the following rows must be moved, but
85 * in fact <i>all</i> rows after allocating sufficiently much space for the
86 * entire data array.
87 *
88 * Suggested settings: @p default_row_length should be the length of a typical
89 * row, for instance the size of the stencil in regular parts of the grid.
90 * Then, @p default_increment may be the expected amount of entries added to
91 * the row by having one hanging node. This way, a good compromise between
92 * memory consumption and speed should be achieved. @p default_reserve should
93 * then be an estimate for the number of hanging nodes times @p
94 * default_increment.
95 *
96 * Letting @p default_increment be zero causes an exception whenever a row
97 * overflows.
98 *
99 * If the rows are expected to be filled more or less from first to last,
100 * using a @p default_row_length of zero may not be such a bad idea.
101 *
102 * @note The name of the class makes sense by pronouncing it the American way,
103 * where "EZ" is pronounced the same way as the word "easy".
104 */
105 template <typename number>
106 class SparseMatrixEZ : public EnableObserverPointer
107 {
108 public:
109 /**
110 * Declare type for container size.
111 */
112 using size_type = types::global_dof_index;
113
114 /**
115 * The class for storing the column number of an entry together with its
116 * value.
117 */
118 struct Entry
119 {
120 /**
121 * Standard constructor. Sets @p column to @p invalid.
122 */
123 Entry();
124
125 /**
126 * Constructor. Fills column and value.
127 */
128 Entry(const size_type column, const number &value);
129
130 /**
131 * The column number.
132 */
133 size_type column;
134
135 /**
136 * The value there.
137 */
138 number value;
139
140 /**
141 * Non-existent column number.
142 */
143 static const size_type invalid = numbers::invalid_size_type;
144 };
145
146 /**
147 * Structure for storing information on a matrix row. One object for each
148 * row will be stored in the matrix.
149 */
150 struct RowInfo
151 {
152 /**
153 * Constructor.
154 */
155 RowInfo(const size_type start = Entry::invalid);
156
157 /**
158 * Index of first entry of the row in the data field.
159 */
160 size_type start;
161 /**
162 * Number of entries in this row.
163 */
164 unsigned short length;
165 /**
166 * Position of the diagonal element relative to the start index.
167 */
168 unsigned short diagonal;
169 /**
170 * Value for non-existing diagonal.
171 */
172 static const unsigned short invalid_diagonal =
173 static_cast<unsigned short>(-1);
174 };
175
176 public:
177 /**
178 * Standard-conforming iterator.
179 */
180 class const_iterator
181 {
182 private:
183 /**
184 * Accessor class for iterators
185 */
186 class Accessor
187 {
188 public:
189 /**
190 * Constructor. Since we use accessors only for read access, a const
191 * matrix pointer is sufficient.
192 */
193 Accessor(const SparseMatrixEZ<number> *matrix,
194 const size_type row,
195 const unsigned short index);
196
197 /**
198 * Row number of the element represented by this object.
199 */
200 size_type
201 row() const;
202
203 /**
204 * Index in row of the element represented by this object.
205 */
206 unsigned short
207 index() const;
208
209 /**
210 * Column number of the element represented by this object.
211 */
212 size_type
213 column() const;
214
215 /**
216 * Value of this matrix entry.
217 */
218 number
219 value() const;
220
221 protected:
222 /**
223 * The matrix accessed.
224 */
225 const SparseMatrixEZ<number> *matrix;
226
227 /**
228 * Current row number.
229 */
230 size_type a_row;
231
232 /**
233 * Current index in row.
234 */
235 unsigned short a_index;
236
237 // Make enclosing class a friend.
238 friend class const_iterator;
239 };
240
241 public:
242 /**
243 * Constructor.
244 */
245 const_iterator(const SparseMatrixEZ<number> *matrix,
246 const size_type row,
247 const unsigned short index);
248
249 /**
250 * Prefix increment. This always returns a valid entry or <tt>end()</tt>.
251 */
252 const_iterator &
253 operator++();
254
255 /**
256 * Dereferencing operator.
257 */
258 const Accessor &
259 operator*() const;
260
261 /**
262 * Dereferencing operator.
263 */
264 const Accessor *
265 operator->() const;
266
267 /**
268 * Comparison. True, if both iterators point to the same matrix position.
269 */
270 bool
271 operator==(const const_iterator &) const;
272 /**
273 * Inverse of <tt>==</tt>.
274 */
275 bool
276 operator!=(const const_iterator &) const;
277
278 /**
279 * Comparison operator. Result is true if either the first row number is
280 * smaller or if the row numbers are equal and the first index is smaller.
281 */
282 bool
283 operator<(const const_iterator &) const;
284
285 private:
286 /**
287 * Store an object of the accessor class.
288 */
289 Accessor accessor;
290 };
291
292 /**
293 * Type of matrix entries. This alias is analogous to <tt>value_type</tt>
294 * in the standard library containers.
295 */
296 using value_type = number;
297
298 /**
299 * @name Constructors and initialization
300 */
301 /** @{ */
302 /**
303 * Constructor. Initializes an empty matrix of dimension zero times zero.
304 */
305 SparseMatrixEZ();
306
307 /**
308 * Dummy copy constructor. This is here for use in containers. It may only
309 * be called for empty objects.
310 *
311 * If you really want to copy a whole matrix, you can do so by using the @p
312 * copy_from function.
313 */
314 SparseMatrixEZ(const SparseMatrixEZ &);
315
316 /**
317 * Constructor. Generates a matrix of the given size, ready to be filled.
318 * The optional parameters @p default_row_length and @p default_increment
319 * allow for preallocating memory. Providing these properly is essential for
320 * an efficient assembling of the matrix.
321 */
322 explicit SparseMatrixEZ(const size_type n_rows,
323 const size_type n_columns,
324 const size_type default_row_length = 0,
325 const unsigned int default_increment = 1);
326
327 /**
328 * Destructor. Free all memory.
329 */
330 ~SparseMatrixEZ() override = default;
331
332 /**
333 * Pseudo operator only copying empty objects.
334 */
335 SparseMatrixEZ<number> &
336 operator=(const SparseMatrixEZ<number> &);
337
338 /**
339 * This operator assigns a scalar to a matrix. Since this does usually not
340 * make much sense (should we set all matrix entries to this value? Only the
341 * nonzero entries of the sparsity pattern?), this operation is only allowed
342 * if the actual value to be assigned is zero. This operator only exists to
343 * allow for the obvious notation <tt>matrix=0</tt>, which sets all elements
344 * of the matrix to zero, but keep the sparsity pattern previously used.
345 */
346 SparseMatrixEZ<number> &
347 operator=(const double d);
348
349 /**
350 * Reinitialize the sparse matrix to the dimensions provided. The matrix
351 * will have no entries at this point. The optional parameters @p
352 * default_row_length, @p default_increment and @p reserve allow for
353 * preallocating memory. Providing these properly is essential for an
354 * efficient assembling of the matrix.
355 */
356 void
357 reinit(const size_type n_rows,
358 const size_type n_columns,
359 const size_type default_row_length = 0,
360 const unsigned int default_increment = 1,
361 const size_type reserve = 0);
362
363 /**
364 * Release all memory and return to a state just like after having called
365 * the default constructor. It also forgets its sparsity pattern.
366 */
367 void
368 clear();
369 /** @} */
370 /**
371 * @name Information on the matrix
372 */
373 /** @{ */
374 /**
375 * Return whether the object is empty. It is empty if both dimensions are
376 * zero.
377 */
378 bool
379 empty() const;
380
381 /**
382 * Return the dimension of the codomain (or range) space. Note that the
383 * matrix is of dimension $m \times n$.
384 */
385 size_type
386 m() const;
387
388 /**
389 * Return the dimension of the domain space. Note that the matrix is of
390 * dimension $m \times n$.
391 */
392 size_type
393 n() const;
394
395 /**
396 * Return the number of entries in a specific row.
397 */
398 size_type
399 get_row_length(const size_type row) const;
400
401 /**
402 * Return the number of nonzero elements of this matrix.
403 */
404 size_type
405 n_nonzero_elements() const;
406
407 /**
408 * Determine an estimate for the memory consumption (in bytes) of this
409 * object.
410 */
411 std::size_t
412 memory_consumption() const;
413
414 /**
415 * Print statistics. If @p full is @p true, prints a histogram of all
416 * existing row lengths and allocated row lengths. Otherwise, just the
417 * relation of allocated and used entries is shown.
418 */
419 template <typename StreamType>
420 void
421 print_statistics(StreamType &s, bool full = false);
422
423 /**
424 * Compute numbers of entries.
425 *
426 * In the first three arguments, this function returns the number of entries
427 * used, allocated and reserved by this matrix.
428 *
429 * If the final argument is true, the number of entries in each line is
430 * printed as well.
431 */
432 void
433 compute_statistics(size_type &used,
434 size_type &allocated,
435 size_type &reserved,
436 std::vector<size_type> &used_by_line,
437 const bool compute_by_line) const;
438 /** @} */
439 /**
440 * @name Modifying entries
441 */
442 /** @{ */
443 /**
444 * Set the element <tt>(i,j)</tt> to @p value.
445 *
446 * If <tt>value</tt> is not a finite number an exception is thrown.
447 *
448 * The optional parameter <tt>elide_zero_values</tt> can be used to specify
449 * whether zero values should be added anyway or these should be filtered
450 * away and only non-zero data is added. The default value is <tt>true</tt>,
451 * i.e., zero values won't be added into the matrix.
452 *
453 * If this function sets the value of an element that does not yet exist,
454 * then it allocates an entry for it. (Unless `elide_zero_values` is `true`
455 * as mentioned above.)
456 *
457 * @note You may need to insert zero elements if you want to keep a symmetric
458 * sparsity pattern for the matrix.
459 */
460 void
461 set(const size_type i,
462 const size_type j,
463 const number value,
464 const bool elide_zero_values = true);
465
466 /**
467 * Add @p value to the element <tt>(i,j)</tt>.
468 *
469 * If this function adds to the value of an element that does not yet exist,
470 * then it allocates an entry for it.
471 *
472 * The function filters out zeroes automatically, i.e., it does not create
473 * new entries when adding zero to a matrix element for which no entry
474 * currently exists.
475 */
476 void
477 add(const size_type i, const size_type j, const number value);
478
479 /**
480 * Add all elements given in a FullMatrix<double> into sparse matrix
481 * locations given by <tt>indices</tt>. In other words, this function adds
482 * the elements in <tt>full_matrix</tt> to the respective entries in calling
483 * matrix, using the local-to-global indexing specified by <tt>indices</tt>
484 * for both the rows and the columns of the matrix. This function assumes a
485 * quadratic sparse matrix and a quadratic full_matrix, the usual situation
486 * in FE calculations.
487 *
488 * The optional parameter <tt>elide_zero_values</tt> can be used to specify
489 * whether zero values should be added anyway or these should be filtered
490 * away and only non-zero data is added. The default value is <tt>true</tt>,
491 * i.e., zero values won't be added into the matrix.
492 */
493 template <typename number2>
494 void
495 add(const std::vector<size_type> &indices,
496 const FullMatrix<number2> &full_matrix,
497 const bool elide_zero_values = true);
498
499 /**
500 * Same function as before, but now including the possibility to use
501 * rectangular full_matrices and different local-to-global indexing on rows
502 * and columns, respectively.
503 */
504 template <typename number2>
505 void
506 add(const std::vector<size_type> &row_indices,
507 const std::vector<size_type> &col_indices,
508 const FullMatrix<number2> &full_matrix,
509 const bool elide_zero_values = true);
510
511 /**
512 * Set several elements in the specified row of the matrix with column
513 * indices as given by <tt>col_indices</tt> to the respective value.
514 *
515 * The optional parameter <tt>elide_zero_values</tt> can be used to specify
516 * whether zero values should be added anyway or these should be filtered
517 * away and only non-zero data is added. The default value is <tt>true</tt>,
518 * i.e., zero values won't be added into the matrix.
519 */
520 template <typename number2>
521 void
522 add(const size_type row,
523 const std::vector<size_type> &col_indices,
524 const std::vector<number2> &values,
525 const bool elide_zero_values = true);
526
527 /**
528 * Add an array of values given by <tt>values</tt> in the given global
529 * matrix row at columns specified by col_indices in the sparse matrix.
530 *
531 * The optional parameter <tt>elide_zero_values</tt> can be used to specify
532 * whether zero values should be added anyway or these should be filtered
533 * away and only non-zero data is added. The default value is <tt>true</tt>,
534 * i.e., zero values won't be added into the matrix.
535 */
536 template <typename number2>
537 void
538 add(const size_type row,
539 const size_type n_cols,
540 const size_type *col_indices,
541 const number2 *values,
542 const bool elide_zero_values = true,
543 const bool col_indices_are_sorted = false);
544
545 /**
546 * Copy the matrix given as argument into the current object.
547 *
548 * Copying matrices is an expensive operation that we do not want to happen
549 * by accident through compiler generated code for <code>operator=</code>.
550 * (This would happen, for example, if one accidentally declared a function
551 * argument of the current type <i>by value</i> rather than <i>by
552 * reference</i>.) The functionality of copying matrices is implemented in
553 * this member function instead. All copy operations of objects of this type
554 * therefore require an explicit function call.
555 *
556 * The source matrix may be a matrix of arbitrary type, as long as its data
557 * type is convertible to the data type of this matrix.
558 *
559 * The optional parameter <tt>elide_zero_values</tt> can be used to specify
560 * whether zero values should be added anyway or these should be filtered
561 * away and only non-zero data is added. The default value is <tt>true</tt>,
562 * i.e., zero values won't be added into the matrix.
563 *
564 * The function returns a reference to @p this.
565 */
566 template <typename MatrixType>
567 SparseMatrixEZ<number> &
568 copy_from(const MatrixType &source, const bool elide_zero_values = true);
569
570 /**
571 * Add @p matrix scaled by @p factor to this matrix.
572 *
573 * The source matrix may be a matrix of arbitrary type, as long as its data
574 * type is convertible to the data type of this matrix and it has the
575 * standard @p const_iterator.
576 */
577 template <typename MatrixType>
578 void
579 add(const number factor, const MatrixType &matrix);
580 /** @} */
581 /**
582 * @name Entry Access
583 */
584 /** @{ */
585 /**
586 * Return the value of the entry (i,j). This may be an expensive operation
587 * and you should always take care where to call this function. In order to
588 * avoid abuse, this function throws an exception if the required element
589 * does not exist in the matrix.
590 *
591 * In case you want a function that returns zero instead (for entries that
592 * are not in the sparsity pattern of the matrix), use the @p el function.
593 */
594 number
595 operator()(const size_type i, const size_type j) const;
596
597 /**
598 * Return the value of the entry (i,j). Returns zero for all non-existing
599 * entries.
600 */
601 number
602 el(const size_type i, const size_type j) const;
603 /** @} */
604 /**
605 * @name Multiplications
606 */
607 /** @{ */
608 /**
609 * Matrix-vector multiplication: let $dst = M*src$ with $M$ being this
610 * matrix.
611 */
612 template <typename somenumber>
613 void
614 vmult(Vector<somenumber> &dst, const Vector<somenumber> &src) const;
615
616 /**
617 * Matrix-vector multiplication: let $dst = M^T*src$ with $M$ being this
618 * matrix. This function does the same as @p vmult but takes the transposed
619 * matrix.
620 */
621 template <typename somenumber>
622 void
623 Tvmult(Vector<somenumber> &dst, const Vector<somenumber> &src) const;
624
625 /**
626 * Adding Matrix-vector multiplication. Add $M*src$ on $dst$ with $M$ being
627 * this matrix.
628 */
629 template <typename somenumber>
630 void
631 vmult_add(Vector<somenumber> &dst, const Vector<somenumber> &src) const;
632
633 /**
634 * Adding Matrix-vector multiplication. Add $M^T*src$ to $dst$ with $M$
635 * being this matrix. This function does the same as @p vmult_add but takes
636 * the transposed matrix.
637 */
638 template <typename somenumber>
639 void
640 Tvmult_add(Vector<somenumber> &dst, const Vector<somenumber> &src) const;
641 /** @} */
642 /**
643 * @name Matrix norms
644 */
645 /** @{ */
646 /**
647 * Frobenius-norm of the matrix.
648 */
649 number
650 l2_norm() const;
651 /** @} */
652 /**
653 * @name Preconditioning methods
654 */
655 /** @{ */
656 /**
657 * Apply the Jacobi preconditioner, which multiplies every element of the @p
658 * src vector by the inverse of the respective diagonal element and
659 * multiplies the result with the damping factor @p omega.
660 */
661 template <typename somenumber>
662 void
663 precondition_Jacobi(Vector<somenumber> &dst,
664 const Vector<somenumber> &src,
665 const number omega = 1.) const;
666
667 /**
668 * Apply SSOR preconditioning to @p src.
669 */
670 template <typename somenumber>
671 void
672 precondition_SSOR(Vector<somenumber> &dst,
673 const Vector<somenumber> &src,
674 const number om = 1.,
675 const std::vector<std::size_t> &pos_right_of_diagonal =
676 std::vector<std::size_t>()) const;
677
678 /**
679 * Apply SOR preconditioning matrix to @p src. The result of this method is
680 * $dst = (om D - L)^{-1} src$.
681 */
682 template <typename somenumber>
683 void
684 precondition_SOR(Vector<somenumber> &dst,
685 const Vector<somenumber> &src,
686 const number om = 1.) const;
687
688 /**
689 * Apply transpose SOR preconditioning matrix to @p src. The result of this
690 * method is $dst = (om D - U)^{-1} src$.
691 */
692 template <typename somenumber>
693 void
694 precondition_TSOR(Vector<somenumber> &dst,
695 const Vector<somenumber> &src,
696 const number om = 1.) const;
697
698 /**
699 * Add the matrix @p A conjugated by @p B, that is, $B A B^T$ to this
700 * object. If the parameter @p transpose is true, compute $B^T A B$.
701 *
702 * This function requires that @p B has a @p const_iterator traversing all
703 * matrix entries and that @p A has a function <tt>el(i,j)</tt> for access
704 * to a specific entry.
705 */
706 template <typename MatrixTypeA, typename MatrixTypeB>
707 void
708 conjugate_add(const MatrixTypeA &A,
709 const MatrixTypeB &B,
710 const bool transpose = false);
711 /** @} */
712 /**
713 * @name Iterators
714 */
715 /** @{ */
716 /**
717 * Iterator starting at the first existing entry.
718 */
719 const_iterator
720 begin() const;
721
722 /**
723 * Final iterator.
724 */
725 const_iterator
726 end() const;
727
728 /**
729 * Iterator starting at the first entry of row @p r. If this row is empty,
730 * the result is <tt>end(r)</tt>, which does NOT point into row @p r.
731 */
732 const_iterator
733 begin(const size_type r) const;
734
735 /**
736 * Final iterator of row @p r. The result may be different from
737 * <tt>end()</tt>!
738 */
739 const_iterator
740 end(const size_type r) const;
741 /** @} */
742 /**
743 * @name Input/Output
744 */
745 /** @{ */
746 /**
747 * Print the matrix to the given stream, using the format <tt>(line,col)
748 * value</tt>, i.e. one nonzero entry of the matrix per line.
749 */
750 void
751 print(std::ostream &out) const;
752
753 /**
754 * Print the matrix in the usual format, i.e., as a matrix and not as a list
755 * of nonzero elements. For better readability, elements not in the matrix
756 * are displayed as empty space, while matrix elements which are explicitly
757 * set to zero are displayed as such.
758 *
759 * The parameters allow for a flexible setting of the output format:
760 * @p precision and @p scientific are used to determine the number format,
761 * where <code>scientific = false</code> means fixed point notation. A zero
762 * entry for @p width makes the function compute a width, but it may be
763 * changed to a positive value, if output is crude.
764 *
765 * Additionally, a character for an empty value may be specified in
766 * @p zero_string, and a character to separate row entries can be set in
767 * @p separator.
768 *
769 * Finally, the whole matrix can be multiplied with a common @p denominator
770 * to produce more readable output, even integers.
771 *
772 * @attention This function may produce @em large amounts of output if
773 * applied to a large matrix!
774 */
775 void
776 print_formatted(std::ostream &out,
777 const unsigned int precision = 3,
778 const bool scientific = true,
779 const unsigned int width = 0,
780 const char *zero_string = " ",
781 const double denominator = 1.,
782 const char *separator = " ") const;
783
784 /**
785 * Write the data of this object in binary mode to a file.
786 *
787 * Note that this binary format is platform dependent.
788 */
789 void
790 block_write(std::ostream &out) const;
791
792 /**
793 * Read data that has previously been written by @p block_write.
794 *
795 * The object is resized on this operation, and all previous contents are
796 * lost.
797 *
798 * A primitive form of error checking is performed which will recognize the
799 * bluntest attempts to interpret some data as a vector stored bitwise to a
800 * file, but not more.
801 */
802 void
803 block_read(std::istream &in);
804 /** @} */
805
806 /**
807 * @addtogroup Exceptions
808 * @{
809 */
810
811 /**
812 * Exception for missing diagonal entry.
813 */
814 DeclException0(ExcNoDiagonal);
815
816 /**
817 * Exception
818 */
819 DeclException2(ExcInvalidEntry,
820 int,
821 int,
822 << "The entry with index (" << arg1 << ',' << arg2
823 << ") does not exist.");
824
825 DeclException2(ExcEntryAllocationFailure,
826 int,
827 int,
828 << "An entry with index (" << arg1 << ',' << arg2
829 << ") cannot be allocated.");
830 /** @} */
831 private:
832 /**
833 * Find an entry and return a const pointer. Return a zero-pointer if the
834 * entry does not exist.
835 */
836 const Entry *
837 locate(const size_type row, const size_type col) const;
838
839 /**
840 * Find an entry and return a writable pointer. Return a zero-pointer if the
841 * entry does not exist.
842 */
843 Entry *
844 locate(const size_type row, const size_type col);
845
846 /**
847 * Find an entry or generate it.
848 */
849 Entry *
850 allocate(const size_type row, const size_type col);
851
852 /**
853 * Version of @p vmult which only performs its actions on the region defined
854 * by <tt>[begin_row,end_row)</tt>. This function is called by @p vmult in
855 * the case of enabled multithreading.
856 */
857 template <typename somenumber>
858 void
859 threaded_vmult(Vector<somenumber> &dst,
860 const Vector<somenumber> &src,
861 const size_type begin_row,
862 const size_type end_row) const;
863
864 /**
865 * Version of @p matrix_norm_square which only performs its actions on the
866 * region defined by <tt>[begin_row,end_row)</tt>. This function is called
867 * by @p matrix_norm_square in the case of enabled multithreading.
868 */
869 template <typename somenumber>
870 void
871 threaded_matrix_norm_square(const Vector<somenumber> &v,
872 const size_type begin_row,
873 const size_type end_row,
874 somenumber *partial_sum) const;
875
876 /**
877 * Version of @p matrix_scalar_product which only performs its actions on
878 * the region defined by <tt>[begin_row,end_row)</tt>. This function is
879 * called by @p matrix_scalar_product in the case of enabled multithreading.
880 */
881 template <typename somenumber>
882 void
883 threaded_matrix_scalar_product(const Vector<somenumber> &u,
884 const Vector<somenumber> &v,
885 const size_type begin_row,
886 const size_type end_row,
887 somenumber *partial_sum) const;
888
889 /**
890 * Number of columns. This is used to check vector dimensions only.
891 */
892 size_type n_columns;
893
894 /**
895 * Info structure for each row.
896 */
897 std::vector<RowInfo> row_info;
898
899 /**
900 * Data storage.
901 */
902 std::vector<Entry> data;
903
904 /**
905 * Increment when a row grows.
906 */
907 unsigned int increment;
908
909 /**
910 * Remember the user provided default row length.
911 */
912 unsigned int saved_default_row_length;
913 };
914
915 /**
916 * @}
917 */
918 /*---------------------- Inline functions -----------------------------------*/
919
920 template <typename number>
921 inline SparseMatrixEZ<number>::Entry::Entry(const size_type column,
922 const number &value)
923 : column(column)
924 , value(value)
925 {}
926
927
928
929 template <typename number>
930 inline SparseMatrixEZ<number>::Entry::Entry()
931 : column(invalid)
932 , value(0)
933 {}
934
935
936 template <typename number>
937 inline SparseMatrixEZ<number>::RowInfo::RowInfo(const size_type start)
938 : start(start)
939 , length(0)
940 , diagonal(invalid_diagonal)
941 {}
942
943
944 //---------------------------------------------------------------------------
945 template <typename number>
946 inline SparseMatrixEZ<number>::const_iterator::Accessor::Accessor(
947 const SparseMatrixEZ<number> *matrix,
948 const size_type r,
949 const unsigned short i)
950 : matrix(matrix)
951 , a_row(r)
952 , a_index(i)
953 {}
954
955
956 template <typename number>
957 inline typename SparseMatrixEZ<number>::size_type
958 SparseMatrixEZ<number>::const_iterator::Accessor::row() const
959 {
960 return a_row;
961 }
962
963
964 template <typename number>
965 inline typename SparseMatrixEZ<number>::size_type
966 SparseMatrixEZ<number>::const_iterator::Accessor::column() const
967 {
968 return matrix->data[matrix->row_info[a_row].start + a_index].column;
969 }
970
971
972 template <typename number>
973 inline unsigned short
974 SparseMatrixEZ<number>::const_iterator::Accessor::index() const
975 {
976 return a_index;
977 }
978
979
980
981 template <typename number>
982 inline number
983 SparseMatrixEZ<number>::const_iterator::Accessor::value() const
984 {
985 return matrix->data[matrix->row_info[a_row].start + a_index].value;
986 }
987
988
989 template <typename number>
990 inline SparseMatrixEZ<number>::const_iterator::const_iterator(
991 const SparseMatrixEZ<number> *matrix,
992 const size_type r,
993 const unsigned short i)
994 : accessor(matrix, r, i)
995 {
996 // Finish if this is the end()
997 if (r == accessor.matrix->m() && i == 0)
998 return;
999
1000 // Make sure we never construct an
1001 // iterator pointing to a
1002 // non-existing entry
1003
1004 // If the index points beyond the
1005 // end of the row, try the next
1006 // row.
1007 if (accessor.a_index >= accessor.matrix->row_info[accessor.a_row].length)
1008 {
1009 do
1010 {
1011 ++accessor.a_row;
1012 }
1013 // Beware! If the next row is
1014 // empty, iterate until a
1015 // non-empty row is found or we
1016 // hit the end of the matrix.
1017 while (accessor.a_row < accessor.matrix->m() &&
1018 accessor.matrix->row_info[accessor.a_row].length == 0);
1019 }
1020 }
1021
1022
1023 template <typename number>
1024 inline typename SparseMatrixEZ<number>::const_iterator &
1025 SparseMatrixEZ<number>::const_iterator::operator++()
1026 {
1027 Assert(accessor.a_row < accessor.matrix->m(), ExcIteratorPastEnd());
1028
1029 // Increment column index
1030 ++(accessor.a_index);
1031 // If index exceeds number of
1032 // entries in this row, proceed
1033 // with next row.
1034 if (accessor.a_index >= accessor.matrix->row_info[accessor.a_row].length)
1035 {
1036 accessor.a_index = 0;
1037 // Do this loop to avoid
1038 // elements in empty rows
1039 do
1040 {
1041 ++accessor.a_row;
1042 }
1043 while (accessor.a_row < accessor.matrix->m() &&
1044 accessor.matrix->row_info[accessor.a_row].length == 0);
1045 }
1046 return *this;
1047 }
1048
1049
1050 template <typename number>
1051 inline const typename SparseMatrixEZ<number>::const_iterator::Accessor &
1052 SparseMatrixEZ<number>::const_iterator::operator*() const
1053 {
1054 return accessor;
1055 }
1056
1057
1058 template <typename number>
1059 inline const typename SparseMatrixEZ<number>::const_iterator::Accessor *
1060 SparseMatrixEZ<number>::const_iterator::operator->() const
1061 {
1062 return &accessor;
1063 }
1064
1065
1066 template <typename number>
1067 inline bool
1068 SparseMatrixEZ<number>::const_iterator::operator==(
1069 const const_iterator &other) const
1070 {
1071 return (accessor.row() == other.accessor.row() &&
1072 accessor.index() == other.accessor.index());
1073 }
1074
1075
1076 template <typename number>
1077 inline bool
1078 SparseMatrixEZ<number>::const_iterator::operator!=(
1079 const const_iterator &other) const
1080 {
1081 return !(*this == other);
1082 }
1083
1084
1085 template <typename number>
1086 inline bool
1087 SparseMatrixEZ<number>::const_iterator::operator<(
1088 const const_iterator &other) const
1089 {
1090 return (accessor.row() < other.accessor.row() ||
1091 (accessor.row() == other.accessor.row() &&
1092 accessor.index() < other.accessor.index()));
1093 }
1094
1095
1096 //---------------------------------------------------------------------------
1097 template <typename number>
1098 inline typename SparseMatrixEZ<number>::size_type
1099 SparseMatrixEZ<number>::m() const
1100 {
1101 return row_info.size();
1102 }
1103
1104
1105 template <typename number>
1106 inline typename SparseMatrixEZ<number>::size_type
1107 SparseMatrixEZ<number>::n() const
1108 {
1109 return n_columns;
1110 }
1111
1112
1113 template <typename number>
1114 inline typename SparseMatrixEZ<number>::Entry *
1115 SparseMatrixEZ<number>::locate(const size_type row, const size_type col)
1116 {
1117 AssertIndexRange(row, m());
1118 AssertIndexRange(col, n());
1119
1120 const RowInfo &r = row_info[row];
1121 const size_type end = r.start + r.length;
1122 for (size_type i = r.start; i < end; ++i)
1123 {
1124 Entry *const entry = &data[i];
1125 if (entry->column == col)
1126 return entry;
1127 if (entry->column == Entry::invalid)
1128 return nullptr;
1129 }
1130 return nullptr;
1131 }
1132
1133
1134
1135 template <typename number>
1136 inline const typename SparseMatrixEZ<number>::Entry *
1137 SparseMatrixEZ<number>::locate(const size_type row, const size_type col) const
1138 {
1139 SparseMatrixEZ<number> *t = const_cast<SparseMatrixEZ<number> *>(this);
1140 return t->locate(row, col);
1141 }
1142
1143
1144 template <typename number>
1145 inline typename SparseMatrixEZ<number>::Entry *
1146 SparseMatrixEZ<number>::allocate(const size_type row, const size_type col)
1147 {
1148 AssertIndexRange(row, m());
1149 AssertIndexRange(col, n());
1150
1151 RowInfo &r = row_info[row];
1152 const size_type end = r.start + r.length;
1153
1154 size_type i = r.start;
1155 // If diagonal exists and this
1156 // column is higher, start only
1157 // after diagonal.
1158 if (r.diagonal != RowInfo::invalid_diagonal && col >= row)
1159 i += r.diagonal;
1160 // Find position of entry
1161 while (i < end && data[i].column < col)
1162 ++i;
1163
1164 // entry found
1165 if (i != end && data[i].column == col)
1166 return &data[i];
1167
1168 // Now, we must insert the new
1169 // entry and move all successive
1170 // entries back.
1171
1172 // If no more space is available
1173 // for this row, insert new
1174 // elements into the vector.
1175 // TODO:[GK] We should not extend this row if i<end
1176 if (row != row_info.size() - 1)
1177 {
1178 if (end >= row_info[row + 1].start)
1179 {
1180 // Failure if increment 0
1181 Assert(increment != 0, ExcEntryAllocationFailure(row, col));
1182
1183 // Insert new entries
1184 data.insert(data.begin() + end, increment, Entry());
1185 // Update starts of
1186 // following rows
1187 for (size_type rn = row + 1; rn < row_info.size(); ++rn)
1188 row_info[rn].start += increment;
1189 }
1190 }
1191 else
1192 {
1193 if (end >= data.size())
1194 {
1195 // Here, appending a block
1196 // does not increase
1197 // performance.
1198 data.push_back(Entry());
1199 }
1200 }
1201
1202 Entry *entry = &data[i];
1203 // Save original entry
1204 Entry temp = *entry;
1205 // Insert new entry here to
1206 // make sure all entries
1207 // are ordered by column
1208 // index
1209 entry->column = col;
1210 entry->value = 0;
1211 // Update row_info
1212 ++r.length;
1213 if (col == row)
1214 r.diagonal = i - r.start;
1215 else if (col < row && r.diagonal != RowInfo::invalid_diagonal)
1216 ++r.diagonal;
1217
1218 if (i == end)
1219 return entry;
1220
1221 // Move all entries in this
1222 // row up by one
1223 for (size_type j = i + 1; j < end; ++j)
1224 {
1225 // There should be no invalid
1226 // entry below end
1227 Assert(data[j].column != Entry::invalid, ExcInternalError());
1228
1229 // TODO[GK]: This could be done more efficiently by moving starting at the
1230 // top rather than swapping starting at the bottom
1231 std::swap(data[j], temp);
1232 }
1233 Assert(data[end].column == Entry::invalid, ExcInternalError());
1234
1235 data[end] = temp;
1236
1237 return entry;
1238 }
1239
1240
1241
1242 template <typename number>
1243 inline void
1244 SparseMatrixEZ<number>::set(const size_type i,
1245 const size_type j,
1246 const number value,
1247 const bool elide_zero_values)
1248 {
1249 AssertIsFinite(value);
1250
1251 AssertIndexRange(i, m());
1252 AssertIndexRange(j, n());
1253
1254 if (elide_zero_values && value == 0.)
1255 {
1256 Entry *entry = locate(i, j);
1257 if (entry != nullptr)
1258 entry->value = 0.;
1259 }
1260 else
1261 {
1262 Entry *entry = allocate(i, j);
1263 entry->value = value;
1264 }
1265 }
1266
1267
1268
1269 template <typename number>
1270 inline void
1271 SparseMatrixEZ<number>::add(const size_type i,
1272 const size_type j,
1273 const number value)
1274 {
1275 AssertIsFinite(value);
1276
1277 AssertIndexRange(i, m());
1278 AssertIndexRange(j, n());
1279
1280 // ignore zero additions
1281 if (std::abs(value) == 0.)
1282 return;
1283
1284 Entry *entry = allocate(i, j);
1285 entry->value += value;
1286 }
1287
1288
1289 template <typename number>
1290 template <typename number2>
1291 void
1292 SparseMatrixEZ<number>::add(const std::vector<size_type> &indices,
1293 const FullMatrix<number2> &full_matrix,
1294 const bool elide_zero_values)
1295 {
1296 // TODO: This function can surely be made more efficient
1297 for (size_type i = 0; i < indices.size(); ++i)
1298 for (size_type j = 0; j < indices.size(); ++j)
1299 if ((full_matrix(i, j) != 0) || (elide_zero_values == false))
1300 add(indices[i], indices[j], full_matrix(i, j));
1301 }
1302
1303
1304
1305 template <typename number>
1306 template <typename number2>
1307 void
1308 SparseMatrixEZ<number>::add(const std::vector<size_type> &row_indices,
1309 const std::vector<size_type> &col_indices,
1310 const FullMatrix<number2> &full_matrix,
1311 const bool elide_zero_values)
1312 {
1313 // TODO: This function can surely be made more efficient
1314 for (size_type i = 0; i < row_indices.size(); ++i)
1315 for (size_type j = 0; j < col_indices.size(); ++j)
1316 if ((full_matrix(i, j) != 0) || (elide_zero_values == false))
1317 add(row_indices[i], col_indices[j], full_matrix(i, j));
1318 }
1319
1320
1321
1322 template <typename number>
1323 template <typename number2>
1324 void
1325 SparseMatrixEZ<number>::add(const size_type row,
1326 const std::vector<size_type> &col_indices,
1327 const std::vector<number2> &values,
1328 const bool elide_zero_values)
1329 {
1330 // TODO: This function can surely be made more efficient
1331 for (size_type j = 0; j < col_indices.size(); ++j)
1332 if ((values[j] != 0) || (elide_zero_values == false))
1333 add(row, col_indices[j], values[j]);
1334 }
1335
1336
1337
1338 template <typename number>
1339 template <typename number2>
1340 void
1341 SparseMatrixEZ<number>::add(const size_type row,
1342 const size_type n_cols,
1343 const size_type *col_indices,
1344 const number2 *values,
1345 const bool elide_zero_values,
1346 const bool /*col_indices_are_sorted*/)
1347 {
1348 // TODO: This function can surely be made more efficient
1349 for (size_type j = 0; j < n_cols; ++j)
1350 if ((std::abs(values[j]) != 0) || (elide_zero_values == false))
1351 add(row, col_indices[j], values[j]);
1352 }
1353
1354
1355
1356 template <typename number>
1357 inline number
1358 SparseMatrixEZ<number>::el(const size_type i, const size_type j) const
1359 {
1360 const Entry *entry = locate(i, j);
1361 if (entry)
1362 return entry->value;
1363 return 0.;
1364 }
1365
1366
1367
1368 template <typename number>
1369 inline number
1370 SparseMatrixEZ<number>::operator()(const size_type i, const size_type j) const
1371 {
1372 const Entry *entry = locate(i, j);
1373 if (entry)
1374 return entry->value;
1375 Assert(false, ExcInvalidEntry(i, j));
1376 return 0.;
1377 }
1378
1379
1380 template <typename number>
1381 inline typename SparseMatrixEZ<number>::const_iterator
1382 SparseMatrixEZ<number>::begin() const
1383 {
1384 const_iterator result(this, 0, 0);
1385 return result;
1386 }
1387
1388 template <typename number>
1389 inline typename SparseMatrixEZ<number>::const_iterator
1390 SparseMatrixEZ<number>::end() const
1391 {
1392 return const_iterator(this, m(), 0);
1393 }
1394
1395 template <typename number>
1396 inline typename SparseMatrixEZ<number>::const_iterator
1397 SparseMatrixEZ<number>::begin(const size_type r) const
1398 {
1399 AssertIndexRange(r, m());
1400 const_iterator result(this, r, 0);
1401 return result;
1402 }
1403
1404 template <typename number>
1405 inline typename SparseMatrixEZ<number>::const_iterator
1406 SparseMatrixEZ<number>::end(const size_type r) const
1407 {
1408 AssertIndexRange(r, m());
1409 const_iterator result(this, r + 1, 0);
1410 return result;
1411 }
1412
1413 template <typename number>
1414 template <typename MatrixType>
1415 inline SparseMatrixEZ<number> &
1416 SparseMatrixEZ<number>::copy_from(const MatrixType &M,
1417 const bool elide_zero_values)
1418 {
1419 reinit(M.m(), M.n(), this->saved_default_row_length, this->increment);
1420
1421 // loop over the elements of the argument matrix row by row, as suggested
1422 // in the documentation of the sparse matrix iterator class, and
1423 // copy them into the current object
1424 for (size_type row = 0; row < M.m(); ++row)
1425 {
1426 const typename MatrixType::const_iterator end_row = M.end(row);
1427 for (typename MatrixType::const_iterator entry = M.begin(row);
1428 entry != end_row;
1429 ++entry)
1430 set(row, entry->column(), entry->value(), elide_zero_values);
1431 }
1432
1433 return *this;
1434 }
1435
1436 template <typename number>
1437 template <typename MatrixType>
1438 inline void
1439 SparseMatrixEZ<number>::add(const number factor, const MatrixType &M)
1440 {
1441 Assert(M.m() == m(), ExcDimensionMismatch(M.m(), m()));
1442 Assert(M.n() == n(), ExcDimensionMismatch(M.n(), n()));
1443
1444 if (factor == 0.)
1445 return;
1446
1447 // loop over the elements of the argument matrix row by row, as suggested
1448 // in the documentation of the sparse matrix iterator class, and
1449 // add them into the current object
1450 for (size_type row = 0; row < M.m(); ++row)
1451 {
1452 const typename MatrixType::const_iterator end_row = M.end(row);
1453 for (typename MatrixType::const_iterator entry = M.begin(row);
1454 entry != end_row;
1455 ++entry)
1456 if (entry->value() != 0)
1457 add(row, entry->column(), factor * entry->value());
1458 }
1459 }
1460
1461
1462
1463 template <typename number>
1464 template <typename MatrixTypeA, typename MatrixTypeB>
1465 inline void
1466 SparseMatrixEZ<number>::conjugate_add(const MatrixTypeA &A,
1467 const MatrixTypeB &B,
1468 const bool transpose)
1469 {
1470 // Compute the result
1471 // r_ij = \sum_kl b_ik b_jl a_kl
1472
1473 // Assert (n() == B.m(), ExcDimensionMismatch(n(), B.m()));
1474 // Assert (m() == B.m(), ExcDimensionMismatch(m(), B.m()));
1475 // Assert (A.n() == B.n(), ExcDimensionMismatch(A.n(), B.n()));
1476 // Assert (A.m() == B.n(), ExcDimensionMismatch(A.m(), B.n()));
1477
1478 // Somehow, we have to avoid making
1479 // this an operation of complexity
1480 // n^2. For the transpose case, we
1481 // can go through the non-zero
1482 // elements of A^-1 and use the
1483 // corresponding rows of B only.
1484 // For the non-transpose case, we
1485 // must find a trick.
1486 typename MatrixTypeB::const_iterator b1 = B.begin();
1487 const typename MatrixTypeB::const_iterator b_final = B.end();
1488 if (transpose)
1489 while (b1 != b_final)
1490 {
1491 const size_type i = b1->column();
1492 const size_type k = b1->row();
1493 typename MatrixTypeB::const_iterator b2 = B.begin();
1494 while (b2 != b_final)
1495 {
1496 const size_type j = b2->column();
1497 const size_type l = b2->row();
1498
1499 const typename MatrixTypeA::value_type a = A.el(k, l);
1500
1501 if (a != 0.)
1502 add(i, j, a * b1->value() * b2->value());
1503 ++b2;
1504 }
1505 ++b1;
1506 }
1507 else
1508 {
1509 // Determine minimal and
1510 // maximal row for a column in
1511 // advance.
1512
1513 std::vector<size_type> minrow(B.n(), B.m());
1514 std::vector<size_type> maxrow(B.n(), 0);
1515 while (b1 != b_final)
1516 {
1517 const size_type r = b1->row();
1518 if (r < minrow[b1->column()])
1519 minrow[b1->column()] = r;
1520 if (r > maxrow[b1->column()])
1521 maxrow[b1->column()] = r;
1522 ++b1;
1523 }
1524
1525 typename MatrixTypeA::const_iterator ai = A.begin();
1526 const typename MatrixTypeA::const_iterator ae = A.end();
1527
1528 while (ai != ae)
1529 {
1530 const typename MatrixTypeA::value_type a = ai->value();
1531 // Don't do anything if
1532 // this entry is zero.
1533 if (a == 0.)
1534 continue;
1535
1536 // Now, loop over all rows
1537 // having possibly a
1538 // nonzero entry in column
1539 // ai->row()
1540 b1 = B.begin(minrow[ai->row()]);
1541 const typename MatrixTypeB::const_iterator be1 =
1542 B.end(maxrow[ai->row()]);
1543 const typename MatrixTypeB::const_iterator be2 =
1544 B.end(maxrow[ai->column()]);
1545
1546 while (b1 != be1)
1547 {
1548 const double b1v = b1->value();
1549 // We need the product
1550 // of both. If it is
1551 // zero, we can save
1552 // the work
1553 if (b1->column() == ai->row() && (b1v != 0.))
1554 {
1555 const size_type i = b1->row();
1556
1557 typename MatrixTypeB::const_iterator b2 =
1558 B.begin(minrow[ai->column()]);
1559 while (b2 != be2)
1560 {
1561 if (b2->column() == ai->column())
1562 {
1563 const size_type j = b2->row();
1564 add(i, j, a * b1v * b2->value());
1565 }
1566 ++b2;
1567 }
1568 }
1569 ++b1;
1570 }
1571 ++ai;
1572 }
1573 }
1574 }
1575
1576
1577 template <typename number>
1578 template <typename StreamType>
1579 inline void
1580 SparseMatrixEZ<number>::print_statistics(StreamType &out, bool full)
1581 {
1582 size_type used;
1583 size_type allocated;
1584 size_type reserved;
1585 std::vector<size_type> used_by_line;
1586
1587 compute_statistics(used, allocated, reserved, used_by_line, full);
1588
1589 out << "SparseMatrixEZ:used entries:" << used << std::endl
1590 << "SparseMatrixEZ:allocated entries:" << allocated << std::endl
1591 << "SparseMatrixEZ:reserved entries:" << reserved << std::endl;
1592
1593 if (full)
1594 {
1595 for (size_type i = 0; i < used_by_line.size(); ++i)
1596 if (used_by_line[i] != 0)
1597 out << "SparseMatrixEZ:entries\t" << i << "\trows\t"
1598 << used_by_line[i] << std::endl;
1599 }
1600 }
1601
1602
1603 DEAL_II_NAMESPACE_CLOSE
1604
1605 #endif