Debian Codegraph @

include/deal.II/lac/chunk_sparse_matrix.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2008 - 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_chunk_sparse_matrix_h
16 #define dealii_chunk_sparse_matrix_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/observer_pointer.h>
23
24 #include <deal.II/lac/chunk_sparsity_pattern.h>
25 #include <deal.II/lac/exceptions.h>
26 #include <deal.II/lac/identity_matrix.h>
27
28 #include <iterator>
29 #include <memory>
30
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 FullMatrix;
40 #endif
41
42 /**
43 * @addtogroup Matrix1
44 * @{
45 */
46
47 /**
48 * A namespace in which we declare iterators over the elements of sparse
49 * matrices.
50 */
51 namespace ChunkSparseMatrixIterators
52 {
53 // forward declaration
54 template <typename number, bool Constness>
55 class Iterator;
56
57 /**
58 * General template for sparse matrix accessors. The first template argument
59 * denotes the underlying numeric type, the second the constness of the
60 * matrix.
61 *
62 * The general template is not implemented, only the specializations for the
63 * two possible values of the second template argument. Therefore, the
64 * interface listed here only serves as a template provided since doxygen
65 * does not link the specializations.
66 */
67 template <typename number, bool Constness>
68 class Accessor : public ChunkSparsityPatternIterators::Accessor
69 {
70 public:
71 /**
72 * Value of this matrix entry.
73 */
74 number
75 value() const;
76
77 /**
78 * Value of this matrix entry.
79 */
80 number &
81 value();
82
83 /**
84 * Return a reference to the matrix into which this accessor points. Note
85 * that in the present case, this is a constant reference.
86 */
87 const ChunkSparseMatrix<number> &
88 get_matrix() const;
89 };
90
91
92
93 /**
94 * Accessor class for constant matrices, used in the const_iterators. This
95 * class builds on the accessor classes used for sparsity patterns to loop
96 * over all nonzero entries, and only adds the accessor functions to gain
97 * access to the actual value stored at a certain location.
98 */
99 template <typename number>
100 class Accessor<number, true> : public ChunkSparsityPatternIterators::Accessor
101 {
102 public:
103 /**
104 * Typedef for the type (including constness) of the matrix to be used
105 * here.
106 */
107 using MatrixType = const ChunkSparseMatrix<number>;
108
109 /**
110 * Constructor.
111 */
112 Accessor(MatrixType *matrix, const unsigned int row);
113
114 /**
115 * Constructor. Construct the end accessor for the given matrix.
116 */
117 Accessor(MatrixType *matrix);
118
119 /**
120 * Copy constructor to get from a non-const accessor to a const accessor.
121 */
122 Accessor(const ChunkSparseMatrixIterators::Accessor<number, false> &a);
123
124 /**
125 * Value of this matrix entry.
126 */
127 number
128 value() const;
129
130 /**
131 * Return a reference to the matrix into which this accessor points. Note
132 * that in the present case, this is a constant reference.
133 */
134 const MatrixType &
135 get_matrix() const;
136
137 private:
138 /**
139 * Pointer to the matrix we use.
140 */
141 MatrixType *matrix;
142
143 /**
144 * Make the advance function of the base class available.
145 */
146 using ChunkSparsityPatternIterators::Accessor::advance;
147
148 // Make iterator class a friend.
149 template <typename, bool>
150 friend class Iterator;
151 };
152
153
154 /**
155 * Accessor class for non-constant matrices, used in the iterators. This
156 * class builds on the accessor classes used for sparsity patterns to loop
157 * over all nonzero entries, and only adds the accessor functions to gain
158 * access to the actual value stored at a certain location.
159 */
160 template <typename number>
161 class Accessor<number, false> : public ChunkSparsityPatternIterators::Accessor
162 {
163 private:
164 /**
165 * Reference class. This is what the accessor class returns when you call
166 * the value() function. The reference acts just as if it were a reference
167 * to the actual value of a matrix entry, i.e. you can read and write it,
168 * you can add and multiply to it, etc, but since the matrix does not give
169 * away the address of this matrix entry, we have to go through functions
170 * to do all this.
171 *
172 * The constructor takes a pointer to an accessor object that describes
173 * which element of the matrix it points to. This creates an ambiguity
174 * when one writes code like iterator->value()=0 (instead of
175 * iterator->value()=0.0), since the right hand side is an integer that
176 * can both be converted to a <tt>number</tt> (i.e., most commonly a
177 * double) or to another object of type <tt>Reference</tt>. The compiler
178 * then complains about not knowing which conversion to take.
179 *
180 * For some reason, adding another overload operator=(int) doesn't seem to
181 * cure the problem. We avoid it, however, by adding a second, dummy
182 * argument to the Reference constructor, that is unused, but makes sure
183 * there is no second matching conversion sequence using a one-argument
184 * right hand side.
185 */
186 class Reference
187 {
188 public:
189 /**
190 * Constructor. For the second argument, see the general class
191 * documentation.
192 */
193 Reference(const Accessor *accessor, const bool dummy);
194
195 /**
196 * Conversion operator to the data type of the matrix.
197 */
198 operator number() const;
199
200 /**
201 * Set the element of the matrix we presently point to to @p n.
202 */
203 const Reference &
204 operator=(const number n) const;
205
206 /**
207 * Add @p n to the element of the matrix we presently point to.
208 */
209 const Reference &
210 operator+=(const number n) const;
211
212 /**
213 * Subtract @p n from the element of the matrix we presently point to.
214 */
215 const Reference &
216 operator-=(const number n) const;
217
218 /**
219 * Multiply the element of the matrix we presently point to by @p n.
220 */
221 const Reference &
222 operator*=(const number n) const;
223
224 /**
225 * Divide the element of the matrix we presently point to by @p n.
226 */
227 const Reference &
228 operator/=(const number n) const;
229
230 private:
231 /**
232 * Pointer to the accessor that denotes which element we presently point
233 * to.
234 */
235 const Accessor *accessor;
236 };
237
238 public:
239 /**
240 * Typedef for the type (including constness) of the matrix to be used
241 * here.
242 */
243 using MatrixType = ChunkSparseMatrix<number>;
244
245 /**
246 * Constructor.
247 */
248 Accessor(MatrixType *matrix, const unsigned int row);
249
250 /**
251 * Constructor. Construct the end accessor for the given matrix.
252 */
253 Accessor(MatrixType *matrix);
254
255 /**
256 * Value of this matrix entry, returned as a read- and writable reference.
257 */
258 Reference
259 value() const;
260
261 /**
262 * Return a reference to the matrix into which this accessor points. Note
263 * that in the present case, this is a non-constant reference.
264 */
265 MatrixType &
266 get_matrix() const;
267
268 private:
269 /**
270 * Pointer to the matrix we use.
271 */
272 MatrixType *matrix;
273
274 /**
275 * Make the advance function of the base class available.
276 */
277 using ChunkSparsityPatternIterators::Accessor::advance;
278
279 // Make iterator class a friend.
280 template <typename, bool>
281 friend class Iterator;
282 };
283
284
285
286 /**
287 * Iterator for constant and non-constant matrices.
288 *
289 * The first template argument denotes the underlying numeric type, the
290 * second the constness of the matrix.
291 *
292 * Since there is a specialization of this class for
293 * <tt>Constness=false</tt>, this class is for iterators to constant
294 * matrices.
295 */
296 template <typename number, bool Constness>
297 class Iterator
298 {
299 public:
300 /**
301 * Typedef for the matrix type (including constness) we are to operate on.
302 */
303 using MatrixType = typename Accessor<number, Constness>::MatrixType;
304
305 /**
306 * An alias for the type you get when you dereference an iterator of the
307 * current kind.
308 */
309 using value_type = const Accessor<number, Constness> &;
310
311 /**
312 * A type that denotes what data types is used to express the difference
313 * between two iterators.
314 */
315 using difference_type = types::global_dof_index;
316
317 /**
318 * Constructor. Create an iterator into the matrix @p matrix for the given
319 * row and the index within it.
320 */
321 Iterator(MatrixType *matrix, const unsigned int row);
322
323 /**
324 * Constructor. Create the end iterator for the given matrix.
325 */
326 Iterator(MatrixType *matrix);
327
328 /**
329 * Conversion constructor to get from a non-const iterator to a const
330 * iterator.
331 */
332 Iterator(const ChunkSparseMatrixIterators::Iterator<number, false> &i);
333
334 /**
335 * Prefix increment.
336 */
337 Iterator &
338 operator++();
339
340 /**
341 * Postfix increment.
342 */
343 Iterator
344 operator++(int);
345
346 /**
347 * Dereferencing operator.
348 */
349 const Accessor<number, Constness> &
350 operator*() const;
351
352 /**
353 * Dereferencing operator.
354 */
355 const Accessor<number, Constness> *
356 operator->() const;
357
358 /**
359 * Comparison. True, if both iterators point to the same matrix position.
360 */
361 bool
362 operator==(const Iterator &) const;
363
364 /**
365 * Inverse of <tt>==</tt>.
366 */
367 bool
368 operator!=(const Iterator &) const;
369
370 /**
371 * Comparison operator. Result is true if either the first row number is
372 * smaller or if the row numbers are equal and the first index is smaller.
373 *
374 * This function is only valid if both iterators point into the same
375 * matrix.
376 */
377 bool
378 operator<(const Iterator &) const;
379
380 /**
381 * Comparison operator. Works in the same way as above operator, just the
382 * other way round.
383 */
384 bool
385 operator>(const Iterator &) const;
386
387 /**
388 * Return the distance between the current iterator and the argument. The
389 * distance is given by how many times one has to apply operator++ to the
390 * current iterator to get the argument (for a positive return value), or
391 * operator-- (for a negative return value).
392 */
393 int
394 operator-(const Iterator &p) const;
395
396 /**
397 * Return an iterator that is @p n ahead of the current one.
398 */
399 Iterator
400 operator+(const unsigned int n) const;
401
402 private:
403 /**
404 * Store an object of the accessor class.
405 */
406 Accessor<number, Constness> accessor;
407 };
408
409 } // namespace ChunkSparseMatrixIterators
410
411 DEAL_II_NAMESPACE_CLOSE // Do not convert for module purposes
412
413 namespace std
414 {
415 template <typename number, bool Constness>
416 struct iterator_traits<
417 dealii::ChunkSparseMatrixIterators::Iterator<number, Constness>>
418 {
419 using iterator_category = forward_iterator_tag;
420 using value_type = typename dealii::ChunkSparseMatrixIterators::
421 Iterator<number, Constness>::value_type;
422 using difference_type = typename dealii::ChunkSparseMatrixIterators::
423 Iterator<number, Constness>::difference_type;
424 };
425 } // namespace std
426
427 DEAL_II_NAMESPACE_OPEN // Do not convert for module purposes
428
429
430
431 /**
432 * Sparse matrix. This class implements the function to store values in the
433 * locations of a sparse matrix denoted by a SparsityPattern. The separation
434 * of sparsity pattern and values is done since one can store data elements of
435 * different type in these locations without the SparsityPattern having to
436 * know this, and more importantly one can associate more than one matrix with
437 * the same sparsity pattern.
438 *
439 * The use of this class is demonstrated in step-51.
440 *
441 * @note Instantiations for this template are provided for <tt>@<float@> and
442 * @<double@></tt>; others can be generated in application programs (see the
443 * section on
444 * @ref Instantiations
445 * in the manual).
446 */
447 template <typename number>
448 class ChunkSparseMatrix : public virtual EnableObserverPointer
449 {
450 public:
451 /**
452 * Declare the type for container size.
453 */
454 using size_type = types::global_dof_index;
455
456 /**
457 * Type of matrix entries. This alias is analogous to <tt>value_type</tt>
458 * in the standard library containers.
459 */
460 using value_type = number;
461
462 /**
463 * Declare a type that has holds real-valued numbers with the same precision
464 * as the template argument to this class. If the template argument of this
465 * class is a real data type, then real_type equals the template argument.
466 * If the template argument is a std::complex type then real_type equals the
467 * type underlying the complex numbers.
468 *
469 * This alias is used to represent the return type of norms.
470 */
471 using real_type = typename numbers::NumberTraits<number>::real_type;
472
473 /**
474 * Typedef of an iterator class walking over all the nonzero entries of this
475 * matrix. This iterator cannot change the values of the matrix.
476 */
477 using const_iterator = ChunkSparseMatrixIterators::Iterator<number, true>;
478
479 /**
480 * Typedef of an iterator class walking over all the nonzero entries of this
481 * matrix. This iterator @em can change the values of the matrix, but of
482 * course can't change the sparsity pattern as this is fixed once a sparse
483 * matrix is attached to it.
484 */
485 using iterator = ChunkSparseMatrixIterators::Iterator<number, false>;
486
487 /**
488 * A structure that describes some of the traits of this class in terms of
489 * its run-time behavior. Some other classes (such as the block matrix
490 * classes) that take one or other of the matrix classes as its template
491 * parameters can tune their behavior based on the variables in this class.
492 */
493 struct Traits
494 {
495 /**
496 * It is safe to elide additions of zeros to individual elements of this
497 * matrix.
498 */
499 static const bool zero_addition_can_be_elided = true;
500 };
501
502 /**
503 * @name Constructors and initialization.
504 */
505 /** @{ */
506 /**
507 * Constructor; initializes the matrix to be empty, without any structure,
508 * i.e. the matrix is not usable at all. This constructor is therefore only
509 * useful for matrices which are members of a class. All other matrices
510 * should be created at a point in the data flow where all necessary
511 * information is available.
512 *
513 * You have to initialize the matrix before usage with reinit(const
514 * ChunkSparsityPattern&).
515 */
516 ChunkSparseMatrix();
517
518 /**
519 * Copy constructor. This constructor is only allowed to be called if the
520 * matrix to be copied is empty. This is for the same reason as for the
521 * ChunkSparsityPattern, see there for the details.
522 *
523 * If you really want to copy a whole matrix, you can do so by using the
524 * copy_from() function.
525 */
526 ChunkSparseMatrix(const ChunkSparseMatrix &);
527
528 /**
529 * Constructor. Takes the given matrix sparsity structure to represent the
530 * sparsity pattern of this matrix. You can change the sparsity pattern
531 * later on by calling the reinit(const ChunkSparsityPattern&) function.
532 *
533 * You have to make sure that the lifetime of the sparsity structure is at
534 * least as long as that of this matrix or as long as reinit(const
535 * ChunkSparsityPattern&) is not called with a new sparsity pattern.
536 *
537 * The constructor is marked explicit so as to disallow that someone passes
538 * a sparsity pattern in place of a sparse matrix to some function, where an
539 * empty matrix would be generated then.
540 */
541 explicit ChunkSparseMatrix(const ChunkSparsityPattern &sparsity);
542
543 /**
544 * Copy constructor: initialize the matrix with the identity matrix. This
545 * constructor will throw an exception if the sizes of the sparsity pattern
546 * and the identity matrix do not coincide, or if the sparsity pattern does
547 * not provide for nonzero entries on the entire diagonal.
548 */
549 ChunkSparseMatrix(const ChunkSparsityPattern &sparsity,
550 const IdentityMatrix &id);
551
552 /**
553 * Destructor. Free all memory, but do not release the memory of the
554 * sparsity structure.
555 */
556 virtual ~ChunkSparseMatrix() override;
557
558 /**
559 * Copy operator. Since copying entire sparse matrices is a very expensive
560 * operation, we disallow doing so except for the special case of empty
561 * matrices of size zero. This doesn't seem particularly useful, but is
562 * exactly what one needs if one wanted to have a
563 * <code>std::vector@<ChunkSparseMatrix@<double@> @></code>: in that case,
564 * one can create a vector (which needs the ability to copy objects) of
565 * empty matrices that are then later filled with something useful.
566 */
567 ChunkSparseMatrix<number> &
568 operator=(const ChunkSparseMatrix<number> &);
569
570 /**
571 * Copy operator: initialize the matrix with the identity matrix. This
572 * operator will throw an exception if the sizes of the sparsity pattern and
573 * the identity matrix do not coincide, or if the sparsity pattern does not
574 * provide for nonzero entries on the entire diagonal.
575 */
576 ChunkSparseMatrix<number> &
577 operator=(const IdentityMatrix &id);
578
579 /**
580 * This operator assigns a scalar to a matrix. Since this does usually not
581 * make much sense (should we set all matrix entries to this value? Only
582 * the nonzero entries of the sparsity pattern?), this operation is only
583 * allowed if the actual value to be assigned is zero. This operator only
584 * exists to allow for the obvious notation <tt>matrix=0</tt>, which sets
585 * all elements of the matrix to zero, but keep the sparsity pattern
586 * previously used.
587 */
588 ChunkSparseMatrix &
589 operator=(const double d);
590
591 /**
592 * Reinitialize the sparse matrix with the given sparsity pattern. The
593 * latter tells the matrix how many nonzero elements there need to be
594 * reserved.
595 *
596 * Regarding memory allocation, the same applies as said above.
597 *
598 * You have to make sure that the lifetime of the sparsity structure is at
599 * least as long as that of this matrix or as long as reinit(const
600 * ChunkSparsityPattern &) is not called with a new sparsity structure.
601 *
602 * The elements of the matrix are set to zero by this function.
603 */
604 virtual void
605 reinit(const ChunkSparsityPattern &sparsity);
606
607 /**
608 * Release all memory and return to a state just like after having called
609 * the default constructor. It also forgets the sparsity pattern it was
610 * previously tied to.
611 */
612 virtual void
613 clear();
614 /** @} */
615 /**
616 * @name Information on the matrix
617 */
618 /** @{ */
619 /**
620 * Return whether the object is empty. It is empty if either both dimensions
621 * are zero or no ChunkSparsityPattern is associated.
622 */
623 bool
624 empty() const;
625
626 /**
627 * Return the dimension of the codomain (or range) space. Note that the
628 * matrix is of dimension $m \times n$.
629 */
630 size_type
631 m() const;
632
633 /**
634 * Return the dimension of the domain space. Note that the matrix is of
635 * dimension $m \times n$.
636 */
637 size_type
638 n() const;
639
640 /**
641 * Return the number of nonzero elements of this matrix. Actually, it
642 * returns the number of entries in the sparsity pattern; if any of the
643 * entries should happen to be zero, it is counted anyway.
644 */
645 size_type
646 n_nonzero_elements() const;
647
648 /**
649 * Return the number of actually nonzero elements of this matrix.
650 *
651 * Note, that this function does (in contrary to n_nonzero_elements()) not
652 * count all entries of the sparsity pattern but only the ones that are
653 * nonzero.
654 */
655 size_type
656 n_actually_nonzero_elements() const;
657
658 /**
659 * Return a (constant) reference to the underlying sparsity pattern of this
660 * matrix.
661 *
662 * Though the return value is declared <tt>const</tt>, you should be aware
663 * that it may change if you call any nonconstant function of objects which
664 * operate on it.
665 */
666 const ChunkSparsityPattern &
667 get_sparsity_pattern() const;
668
669 /**
670 * Determine an estimate for the memory consumption (in bytes) of this
671 * object. See MemoryConsumption.
672 */
673 std::size_t
674 memory_consumption() const;
675
676 /** @} */
677 /**
678 * @name Modifying entries
679 */
680 /** @{ */
681 /**
682 * Set the element (<i>i,j</i>) to <tt>value</tt>. Throws an error if the
683 * entry does not exist or if <tt>value</tt> is not a finite number. Still,
684 * it is allowed to store zero values in non-existent fields.
685 */
686 void
687 set(const size_type i, const size_type j, const number value);
688
689 /**
690 * Add <tt>value</tt> to the element (<i>i,j</i>). Throws an error if the
691 * entry does not exist or if <tt>value</tt> is not a finite number. Still,
692 * it is allowed to store zero values in non-existent fields.
693 */
694 void
695 add(const size_type i, const size_type j, const number value);
696
697 /**
698 * Add an array of values given by <tt>values</tt> in the given global
699 * matrix row at columns specified by col_indices in the sparse matrix.
700 *
701 * The optional parameter <tt>elide_zero_values</tt> can be used to specify
702 * whether zero values should be added anyway or these should be filtered
703 * away and only non-zero data is added. The default value is <tt>true</tt>,
704 * i.e., zero values won't be added into the matrix.
705 */
706 template <typename number2>
707 void
708 add(const size_type row,
709 const size_type n_cols,
710 const size_type *col_indices,
711 const number2 *values,
712 const bool elide_zero_values = true,
713 const bool col_indices_are_sorted = false);
714
715 /**
716 * Multiply the entire matrix by a fixed factor.
717 */
718 ChunkSparseMatrix &
719 operator*=(const number factor);
720
721 /**
722 * Divide the entire matrix by a fixed factor.
723 */
724 ChunkSparseMatrix &
725 operator/=(const number factor);
726
727 /**
728 * Symmetrize the matrix by forming the mean value between the existing
729 * matrix and its transpose, $A = \frac 12(A+A^T)$.
730 *
731 * This operation assumes that the underlying sparsity pattern represents a
732 * symmetric object. If this is not the case, then the result of this
733 * operation will not be a symmetric matrix, since it only explicitly
734 * symmetrizes by looping over the lower left triangular part for efficiency
735 * reasons; if there are entries in the upper right triangle, then these
736 * elements are missed in the symmetrization. Symmetrization of the sparsity
737 * pattern can be obtain by ChunkSparsityPattern::symmetrize().
738 */
739 void
740 symmetrize();
741
742 /**
743 * Copy the matrix given as argument into the current object.
744 *
745 * Copying matrices is an expensive operation that we do not want to happen
746 * by accident through compiler generated code for <code>operator=</code>.
747 * (This would happen, for example, if one accidentally declared a function
748 * argument of the current type <i>by value</i> rather than <i>by
749 * reference</i>.) The functionality of copying matrices is implemented in
750 * this member function instead. All copy operations of objects of this type
751 * therefore require an explicit function call.
752 *
753 * The source matrix may be a matrix of arbitrary type, as long as its data
754 * type is convertible to the data type of this matrix.
755 *
756 * The function returns a reference to <tt>*this</tt>.
757 */
758 template <typename somenumber>
759 ChunkSparseMatrix<number> &
760 copy_from(const ChunkSparseMatrix<somenumber> &source);
761
762 /**
763 * This function is complete analogous to the
764 * ChunkSparsityPattern::copy_from() function in that it allows to
765 * initialize a whole matrix in one step. See there for more information on
766 * argument types and their meaning. You can also find a small example on
767 * how to use this function there.
768 *
769 * The only difference to the cited function is that the objects which the
770 * inner iterator points to need to be of type <tt>std::pair<unsigned int,
771 * value</tt>, where <tt>value</tt> needs to be convertible to the element
772 * type of this class, as specified by the <tt>number</tt> template
773 * argument.
774 *
775 * Previous content of the matrix is overwritten. Note that the entries
776 * specified by the input parameters need not necessarily cover all elements
777 * of the matrix. Elements not covered remain untouched.
778 */
779 template <typename ForwardIterator>
780 void
781 copy_from(const ForwardIterator begin, const ForwardIterator end);
782
783 /**
784 * Copy the nonzero entries of a full matrix into this object. Previous
785 * content is deleted. Note that the underlying sparsity pattern must be
786 * appropriate to hold the nonzero entries of the full matrix.
787 */
788 template <typename somenumber>
789 void
790 copy_from(const FullMatrix<somenumber> &matrix);
791
792 /**
793 * Add <tt>matrix</tt> scaled by <tt>factor</tt> to this matrix, i.e. the
794 * matrix <tt>factor*matrix</tt> is added to <tt>this</tt>. This function
795 * throws an error if the sparsity patterns of the two involved matrices do
796 * not point to the same object, since in this case the operation is
797 * cheaper.
798 *
799 * The source matrix may be a sparse matrix over an arbitrary underlying
800 * scalar type, as long as its data type is convertible to the data type of
801 * this matrix.
802 */
803 template <typename somenumber>
804 void
805 add(const number factor, const ChunkSparseMatrix<somenumber> &matrix);
806
807 /** @} */
808 /**
809 * @name Entry Access
810 */
811 /** @{ */
812
813 /**
814 * Return the value of the entry (<i>i,j</i>). This may be an expensive
815 * operation and you should always take care where to call this function. In
816 * order to avoid abuse, this function throws an exception if the required
817 * element does not exist in the matrix.
818 *
819 * In case you want a function that returns zero instead (for entries that
820 * are not in the sparsity pattern of the matrix), use the el() function.
821 *
822 * If you are looping over all elements, consider using one of the iterator
823 * classes instead, since they are tailored better to a sparse matrix
824 * structure.
825 */
826 number
827 operator()(const size_type i, const size_type j) const;
828
829 /**
830 * This function is mostly like operator()() in that it returns the value of
831 * the matrix entry (<i>i,j</i>). The only difference is that if this entry
832 * does not exist in the sparsity pattern, then instead of raising an
833 * exception, zero is returned. While this may be convenient in some cases,
834 * note that it is simple to write algorithms that are slow compared to an
835 * optimal solution, since the sparsity of the matrix is not used.
836 *
837 * If you are looping over all elements, consider using one of the iterator
838 * classes instead, since they are tailored better to a sparse matrix
839 * structure.
840 */
841 number
842 el(const size_type i, const size_type j) const;
843
844 /**
845 * Return the main diagonal element in the <i>i</i>th row. This function
846 * throws an error if the matrix is not quadratic.
847 *
848 * This function is considerably faster than the operator()(), since for
849 * quadratic matrices, the diagonal entry may be the first to be stored in
850 * each row and access therefore does not involve searching for the right
851 * column number.
852 */
853 number
854 diag_element(const size_type i) const;
855
856 /**
857 * Extracts a copy of the values and indices in the given matrix row.
858 *
859 * The user is expected to pass the length of the arrays column_indices and
860 * values, which gives a means for checking that we do not write to
861 * unallocated memory. This method is motivated by a similar method in
862 * Trilinos row matrices and gives faster access to entries in the matrix as
863 * compared to iterators which are quite slow for this matrix type.
864 */
865 void
866 extract_row_copy(const size_type row,
867 const size_type array_length,
868 size_type &row_length,
869 size_type *column_indices,
870 number *values) const;
871
872 /** @} */
873 /**
874 * @name Matrix vector multiplications
875 */
876 /** @{ */
877 /**
878 * Matrix-vector multiplication: let <i>dst = M*src</i> with <i>M</i> being
879 * this matrix.
880 *
881 * Note that while this function can operate on all vectors that offer
882 * iterator classes, it is only really effective for objects of type
883 * @ref Vector.
884 * For all classes for which iterating over elements, or random member
885 * access is expensive, this function is not efficient. In particular, if
886 * you want to multiply with BlockVector objects, you should consider using
887 * a BlockChunkSparseMatrix as well.
888 *
889 * Source and destination must not be the same vector.
890 */
891 template <class OutVector, class InVector>
892 void
893 vmult(OutVector &dst, const InVector &src) const;
894
895 /**
896 * Matrix-vector multiplication: let <i>dst = M<sup>T</sup>*src</i> with
897 * <i>M</i> being this matrix. This function does the same as vmult() but
898 * takes the transposed matrix.
899 *
900 * Note that while this function can operate on all vectors that offer
901 * iterator classes, it is only really effective for objects of type
902 * @ref Vector.
903 * For all classes for which iterating over elements, or random member
904 * access is expensive, this function is not efficient. In particular, if
905 * you want to multiply with BlockVector objects, you should consider using
906 * a BlockChunkSparseMatrix as well.
907 *
908 * Source and destination must not be the same vector.
909 */
910 template <class OutVector, class InVector>
911 void
912 Tvmult(OutVector &dst, const InVector &src) const;
913
914 /**
915 * Adding Matrix-vector multiplication. Add <i>M*src</i> on <i>dst</i> with
916 * <i>M</i> being this matrix.
917 *
918 * Note that while this function can operate on all vectors that offer
919 * iterator classes, it is only really effective for objects of type
920 * @ref Vector.
921 * For all classes for which iterating over elements, or random member
922 * access is expensive, this function is not efficient. In particular, if
923 * you want to multiply with BlockVector objects, you should consider using
924 * a BlockChunkSparseMatrix as well.
925 *
926 * Source and destination must not be the same vector.
927 */
928 template <class OutVector, class InVector>
929 void
930 vmult_add(OutVector &dst, const InVector &src) const;
931
932 /**
933 * Adding Matrix-vector multiplication. Add <i>M<sup>T</sup>*src</i> to
934 * <i>dst</i> with <i>M</i> being this matrix. This function does the same
935 * as vmult_add() but takes the transposed matrix.
936 *
937 * Note that while this function can operate on all vectors that offer
938 * iterator classes, it is only really effective for objects of type
939 * @ref Vector.
940 * For all classes for which iterating over elements, or random member
941 * access is expensive, this function is not efficient. In particular, if
942 * you want to multiply with BlockVector objects, you should consider using
943 * a BlockChunkSparseMatrix as well.
944 *
945 * Source and destination must not be the same vector.
946 */
947 template <class OutVector, class InVector>
948 void
949 Tvmult_add(OutVector &dst, const InVector &src) const;
950
951 /**
952 * Return the square of the norm of the vector $v$ with respect to the norm
953 * induced by this matrix, i.e. $\left(v,Mv\right)$. This is useful, e.g. in
954 * the finite element context, where the $L_2$ norm of a function equals the
955 * matrix norm with respect to the @ref GlossMassMatrix "mass matrix" of the vector representing
956 * the nodal values of the finite element function.
957 *
958 * Obviously, the matrix needs to be quadratic for this operation, and for
959 * the result to actually be a norm it also needs to be either real
960 * symmetric or complex hermitian.
961 *
962 * The underlying template types of both this matrix and the given vector
963 * should either both be real or complex-valued, but not mixed, for this
964 * function to make sense.
965 */
966 template <typename somenumber>
967 somenumber
968 matrix_norm_square(const Vector<somenumber> &v) const;
969
970 /**
971 * Compute the matrix scalar product $\left(u,Mv\right)$.
972 */
973 template <typename somenumber>
974 somenumber
975 matrix_scalar_product(const Vector<somenumber> &u,
976 const Vector<somenumber> &v) const;
977 /**
978 * Compute the residual of an equation <i>Mx=b</i>, where the residual is
979 * defined to be <i>r=b-Mx</i>. Write the residual into <tt>dst</tt>. The
980 * <i>l<sub>2</sub></i> norm of the residual vector is returned.
981 *
982 * Source <i>x</i> and destination <i>dst</i> must not be the same vector.
983 */
984 template <typename somenumber>
985 somenumber
986 residual(Vector<somenumber> &dst,
987 const Vector<somenumber> &x,
988 const Vector<somenumber> &b) const;
989
990 /** @} */
991 /**
992 * @name Matrix norms
993 */
994 /** @{ */
995
996 /**
997 * Return the l1-norm of the matrix, that is $|M|_1=max_{all columns
998 * j}\sum_{all rows i} |M_ij|$, (max. sum of columns). This is the natural
999 * matrix norm that is compatible to the l1-norm for vectors, i.e.
1000 * $|Mv|_1\leq |M|_1 |v|_1$. (cf. Haemmerlin-Hoffmann : Numerische
1001 * Mathematik)
1002 */
1003 real_type
1004 l1_norm() const;
1005
1006 /**
1007 * Return the linfty-norm of the matrix, that is $|M|_infty=max_{all rows
1008 * i}\sum_{all columns j} |M_ij|$, (max. sum of rows). This is the natural
1009 * matrix norm that is compatible to the linfty-norm of vectors, i.e.
1010 * $|Mv|_infty \leq |M|_infty |v|_infty$. (cf. Haemmerlin-Hoffmann :
1011 * Numerische Mathematik)
1012 */
1013 real_type
1014 linfty_norm() const;
1015
1016 /**
1017 * Return the frobenius norm of the matrix, i.e. the square root of the sum
1018 * of squares of all entries in the matrix.
1019 */
1020 real_type
1021 frobenius_norm() const;
1022 /** @} */
1023 /**
1024 * @name Preconditioning methods
1025 */
1026 /** @{ */
1027
1028 /**
1029 * Apply the Jacobi preconditioner, which multiplies every element of the
1030 * <tt>src</tt> vector by the inverse of the respective diagonal element and
1031 * multiplies the result with the relaxation factor <tt>omega</tt>.
1032 */
1033 template <typename somenumber>
1034 void
1035 precondition_Jacobi(Vector<somenumber> &dst,
1036 const Vector<somenumber> &src,
1037 const number omega = 1.) const;
1038
1039 /**
1040 * Apply SSOR preconditioning to <tt>src</tt>.
1041 */
1042 template <typename somenumber>
1043 void
1044 precondition_SSOR(Vector<somenumber> &dst,
1045 const Vector<somenumber> &src,
1046 const number om = 1.) const;
1047
1048 /**
1049 * Apply SOR preconditioning matrix to <tt>src</tt>.
1050 */
1051 template <typename somenumber>
1052 void
1053 precondition_SOR(Vector<somenumber> &dst,
1054 const Vector<somenumber> &src,
1055 const number om = 1.) const;
1056
1057 /**
1058 * Apply transpose SOR preconditioning matrix to <tt>src</tt>.
1059 */
1060 template <typename somenumber>
1061 void
1062 precondition_TSOR(Vector<somenumber> &dst,
1063 const Vector<somenumber> &src,
1064 const number om = 1.) const;
1065
1066 /**
1067 * Perform SSOR preconditioning in-place. Apply the preconditioner matrix
1068 * without copying to a second vector. <tt>omega</tt> is the relaxation
1069 * parameter.
1070 */
1071 template <typename somenumber>
1072 void
1073 SSOR(Vector<somenumber> &v, const number omega = 1.) const;
1074
1075 /**
1076 * Perform an SOR preconditioning in-place. <tt>omega</tt> is the
1077 * relaxation parameter.
1078 */
1079 template <typename somenumber>
1080 void
1081 SOR(Vector<somenumber> &v, const number om = 1.) const;
1082
1083 /**
1084 * Perform a transpose SOR preconditioning in-place. <tt>omega</tt> is the
1085 * relaxation parameter.
1086 */
1087 template <typename somenumber>
1088 void
1089 TSOR(Vector<somenumber> &v, const number om = 1.) const;
1090
1091 /**
1092 * Perform a permuted SOR preconditioning in-place.
1093 *
1094 * The standard SOR method is applied in the order prescribed by
1095 * <tt>permutation</tt>, that is, first the row <tt>permutation[0]</tt>,
1096 * then <tt>permutation[1]</tt> and so on. For efficiency reasons, the
1097 * permutation as well as its inverse are required.
1098 *
1099 * <tt>omega</tt> is the relaxation parameter.
1100 */
1101 template <typename somenumber>
1102 void
1103 PSOR(Vector<somenumber> &v,
1104 const std::vector<size_type> &permutation,
1105 const std::vector<size_type> &inverse_permutation,
1106 const number om = 1.) const;
1107
1108 /**
1109 * Perform a transposed permuted SOR preconditioning in-place.
1110 *
1111 * The transposed SOR method is applied in the order prescribed by
1112 * <tt>permutation</tt>, that is, first the row <tt>permutation[m()-1]</tt>,
1113 * then <tt>permutation[m()-2]</tt> and so on. For efficiency reasons, the
1114 * permutation as well as its inverse are required.
1115 *
1116 * <tt>omega</tt> is the relaxation parameter.
1117 */
1118 template <typename somenumber>
1119 void
1120 TPSOR(Vector<somenumber> &v,
1121 const std::vector<size_type> &permutation,
1122 const std::vector<size_type> &inverse_permutation,
1123 const number om = 1.) const;
1124
1125 /**
1126 * Do one SOR step on <tt>v</tt>. Performs a direct SOR step with right
1127 * hand side <tt>b</tt>.
1128 */
1129 template <typename somenumber>
1130 void
1131 SOR_step(Vector<somenumber> &v,
1132 const Vector<somenumber> &b,
1133 const number om = 1.) const;
1134
1135 /**
1136 * Do one adjoint SOR step on <tt>v</tt>. Performs a direct TSOR step with
1137 * right hand side <tt>b</tt>.
1138 */
1139 template <typename somenumber>
1140 void
1141 TSOR_step(Vector<somenumber> &v,
1142 const Vector<somenumber> &b,
1143 const number om = 1.) const;
1144
1145 /**
1146 * Do one SSOR step on <tt>v</tt>. Performs a direct SSOR step with right
1147 * hand side <tt>b</tt> by performing TSOR after SOR.
1148 */
1149 template <typename somenumber>
1150 void
1151 SSOR_step(Vector<somenumber> &v,
1152 const Vector<somenumber> &b,
1153 const number om = 1.) const;
1154 /** @} */
1155 /**
1156 * @name Iterators
1157 */
1158 /** @{ */
1159
1160 /**
1161 * Iterator starting at first entry of the matrix. This is the version for
1162 * constant matrices.
1163 *
1164 * Note that due to the layout in ChunkSparseMatrix, iterating over matrix
1165 * entries is considerably slower than for a sparse matrix, as the iterator
1166 * is travels row-by-row, whereas data is stored in chunks of several rows
1167 * and columns.
1168 */
1169 const_iterator
1170 begin() const;
1171
1172 /**
1173 * Final iterator. This is the version for constant matrices.
1174 *
1175 * Note that due to the layout in ChunkSparseMatrix, iterating over matrix
1176 * entries is considerably slower than for a sparse matrix, as the iterator
1177 * is travels row-by-row, whereas data is stored in chunks of several rows
1178 * and columns.
1179 */
1180 const_iterator
1181 end() const;
1182
1183 /**
1184 * Iterator starting at the first entry of the matrix. This is the version
1185 * for non-constant matrices.
1186 *
1187 * Note that due to the layout in ChunkSparseMatrix, iterating over matrix
1188 * entries is considerably slower than for a sparse matrix, as the iterator
1189 * is travels row-by-row, whereas data is stored in chunks of several rows
1190 * and columns.
1191 */
1192 iterator
1193 begin();
1194
1195 /**
1196 * Final iterator. This is the version for non-constant matrices.
1197 *
1198 * Note that due to the layout in ChunkSparseMatrix, iterating over matrix
1199 * entries is considerably slower than for a sparse matrix, as the iterator
1200 * is travels row-by-row, whereas data is stored in chunks of several rows
1201 * and columns.
1202 */
1203 iterator
1204 end();
1205
1206 /**
1207 * Iterator starting at the first entry of row <tt>r</tt>. This is the
1208 * version for constant matrices.
1209 *
1210 * Note that if the given row is empty, i.e. does not contain any nonzero
1211 * entries, then the iterator returned by this function equals
1212 * <tt>end(r)</tt>. Note also that the iterator may not be dereferenceable in
1213 * that case.
1214 *
1215 * Note that due to the layout in ChunkSparseMatrix, iterating over matrix
1216 * entries is considerably slower than for a sparse matrix, as the iterator
1217 * is travels row-by-row, whereas data is stored in chunks of several rows
1218 * and columns.
1219 */
1220 const_iterator
1221 begin(const unsigned int r) const;
1222
1223 /**
1224 * Final iterator of row <tt>r</tt>. It points to the first element past the
1225 * end of line @p r, or past the end of the entire sparsity pattern. This is
1226 * the version for constant matrices.
1227 *
1228 * Note that the end iterator is not necessarily dereferenceable. This is in
1229 * particular the case if it is the end iterator for the last row of a
1230 * matrix.
1231 *
1232 * Note that due to the layout in ChunkSparseMatrix, iterating over matrix
1233 * entries is considerably slower than for a sparse matrix, as the iterator
1234 * is travels row-by-row, whereas data is stored in chunks of several rows
1235 * and columns.
1236 */
1237 const_iterator
1238 end(const unsigned int r) const;
1239
1240 /**
1241 * Iterator starting at the first entry of row <tt>r</tt>. This is the
1242 * version for non-constant matrices.
1243 *
1244 * Note that if the given row is empty, i.e. does not contain any nonzero
1245 * entries, then the iterator returned by this function equals
1246 * <tt>end(r)</tt>. Note also that the iterator may not be dereferenceable in
1247 * that case.
1248 *
1249 * Note that due to the layout in ChunkSparseMatrix, iterating over matrix
1250 * entries is considerably slower than for a sparse matrix, as the iterator
1251 * is travels row-by-row, whereas data is stored in chunks of several rows
1252 * and columns.
1253 */
1254 iterator
1255 begin(const unsigned int r);
1256
1257 /**
1258 * Final iterator of row <tt>r</tt>. It points to the first element past the
1259 * end of line @p r, or past the end of the entire sparsity pattern. This is
1260 * the version for non-constant matrices.
1261 *
1262 * Note that the end iterator is not necessarily dereferenceable. This is in
1263 * particular the case if it is the end iterator for the last row of a
1264 * matrix.
1265 *
1266 * Note that due to the layout in ChunkSparseMatrix, iterating over matrix
1267 * entries is considerably slower than for a sparse matrix, as the iterator
1268 * is travels row-by-row, whereas data is stored in chunks of several rows
1269 * and columns.
1270 */
1271 iterator
1272 end(const unsigned int r);
1273 /** @} */
1274 /**
1275 * @name Input/Output
1276 */
1277 /** @{ */
1278
1279 /**
1280 * Print the matrix to the given stream, using the format <tt>(line,col)
1281 * value</tt>, i.e. one nonzero entry of the matrix per line.
1282 */
1283 void
1284 print(std::ostream &out) const;
1285
1286 /**
1287 * Print the matrix in the usual format, i.e., as a matrix and not as a list
1288 * of nonzero elements. For better readability, elements not in the matrix
1289 * are displayed as empty space, while matrix elements which are explicitly
1290 * set to zero are displayed as such.
1291 *
1292 * The parameters allow for a flexible setting of the output format:
1293 * @p precision and @p scientific are used to determine the number format,
1294 * where <code>scientific = false</code> means fixed point notation. A zero
1295 * entry for @p width makes the function compute a width, but it may be
1296 * changed to a positive value, if output is crude.
1297 *
1298 * Additionally, a character for an empty value may be specified in
1299 * @p zero_string, and a character to separate row entries can be set in
1300 * @p separator.
1301 *
1302 * Finally, the whole matrix can be multiplied with a common @p denominator
1303 * to produce more readable output, even integers.
1304 *
1305 * @attention This function may produce @em large amounts of output if
1306 * applied to a large matrix!
1307 */
1308 void
1309 print_formatted(std::ostream &out,
1310 const unsigned int precision = 3,
1311 const bool scientific = true,
1312 const unsigned int width = 0,
1313 const char *zero_string = " ",
1314 const double denominator = 1.,
1315 const char *separator = " ") const;
1316
1317 /**
1318 * Print the actual pattern of the matrix. For each entry with an absolute
1319 * value larger than threshold, a '*' is printed, a ':' for every value
1320 * smaller and a '.' for every entry not allocated.
1321 */
1322 void
1323 print_pattern(std::ostream &out, const double threshold = 0.) const;
1324
1325 /**
1326 * Write the data of this object en bloc to a file. This is done in a binary
1327 * mode, so the output is neither readable by humans nor (probably) by other
1328 * computers using a different operating system or number format.
1329 *
1330 * The purpose of this function is that you can swap out matrices and
1331 * sparsity pattern if you are short of memory, want to communicate between
1332 * different programs, or allow objects to be persistent across different
1333 * runs of the program.
1334 */
1335 void
1336 block_write(std::ostream &out) const;
1337
1338 /**
1339 * Read data that has previously been written by block_write() from a file.
1340 * This is done using the inverse operations to the above function, so it is
1341 * reasonably fast because the bitstream is not interpreted except for a few
1342 * numbers up front.
1343 *
1344 * The object is resized on this operation, and all previous contents are
1345 * lost. Note, however, that no checks are performed whether new data and
1346 * the underlying ChunkSparsityPattern object fit together. It is your
1347 * responsibility to make sure that the sparsity pattern and the data to be
1348 * read match.
1349 *
1350 * A primitive form of error checking is performed which will recognize the
1351 * bluntest attempts to interpret some data as a matrix stored bitwise to a
1352 * file that wasn't actually created that way, but not more.
1353 */
1354 void
1355 block_read(std::istream &in);
1356 /** @} */
1357 /**
1358 * @addtogroup Exceptions
1359 * @{
1360 */
1361
1362 /**
1363 * Exception
1364 */
1365 DeclException2(ExcInvalidIndex,
1366 int,
1367 int,
1368 << "You are trying to access the matrix entry with index <"
1369 << arg1 << ',' << arg2
1370 << ">, but this entry does not exist in the sparsity pattern "
1371 "of this matrix."
1372 "\n\n"
1373 "The most common cause for this problem is that you used "
1374 "a method to build the sparsity pattern that did not "
1375 "(completely) take into account all of the entries you "
1376 "will later try to write into. An example would be "
1377 "building a sparsity pattern that does not include "
1378 "the entries you will write into due to constraints "
1379 "on degrees of freedom such as hanging nodes or periodic "
1380 "boundary conditions. In such cases, building the "
1381 "sparsity pattern will succeed, but you will get errors "
1382 "such as the current one at one point or other when "
1383 "trying to write into the entries of the matrix.");
1384 /**
1385 * Exception
1386 */
1387 DeclException0(ExcDifferentChunkSparsityPatterns);
1388 /**
1389 * Exception
1390 */
1391 DeclException2(ExcIteratorRange,
1392 int,
1393 int,
1394 << "The iterators denote a range of " << arg1
1395 << " elements, but the given number of rows was " << arg2);
1396 /**
1397 * Exception
1398 */
1399 DeclExceptionMsg(ExcSourceEqualsDestination,
1400 "You are attempting an operation on two vectors that "
1401 "are the same object, but the operation requires that the "
1402 "two objects are in fact different.");
1403 /** @} */
1404 private:
1405 /**
1406 * Pointer to the sparsity pattern used for this matrix. In order to
1407 * guarantee that it is not deleted while still in use, we subscribe to it
1408 * using the ObserverPointer class.
1409 */
1410 ObserverPointer<const ChunkSparsityPattern, ChunkSparseMatrix<number>> cols;
1411
1412 /**
1413 * Array of values for all the nonzero entries. The position of an
1414 * entry within the matrix, i.e., the row and column number for a
1415 * given value in this array can only be deduced using the sparsity
1416 * pattern. The same holds for the more common operation of finding
1417 * an entry by its coordinates.
1418 */
1419 std::unique_ptr<number[]> val;
1420
1421 /**
1422 * Allocated size of #val. This can be larger than the actually used part if
1423 * the size of the matrix was reduced sometime in the past by associating a
1424 * sparsity pattern with a smaller size to this object, using the reinit()
1425 * function.
1426 */
1427 size_type max_len;
1428
1429 /**
1430 * Return the location of entry $(i,j)$ within the val array.
1431 */
1432 size_type
1433 compute_location(const size_type i, const size_type j) const;
1434
1435 // make all other sparse matrices friends
1436 template <typename somenumber>
1437 friend class ChunkSparseMatrix;
1438
1439 // Also give access to internal details to the iterator/accessor classes.
1440 template <typename, bool>
1441 friend class ChunkSparseMatrixIterators::Iterator;
1442 template <typename, bool>
1443 friend class ChunkSparseMatrixIterators::Accessor;
1444 };
1445
1446 /** @} */
1447
1448 #ifndef DOXYGEN
1449 /*---------------------- Inline functions -----------------------------------*/
1450
1451
1452
1453 template <typename number>
1454 inline typename ChunkSparseMatrix<number>::size_type
1455 ChunkSparseMatrix<number>::m() const
1456 {
1457 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1458 return cols->rows;
1459 }
1460
1461
1462 template <typename number>
1463 inline typename ChunkSparseMatrix<number>::size_type
1464 ChunkSparseMatrix<number>::n() const
1465 {
1466 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1467 return cols->cols;
1468 }
1469
1470
1471
1472 template <typename number>
1473 inline const ChunkSparsityPattern &
1474 ChunkSparseMatrix<number>::get_sparsity_pattern() const
1475 {
1476 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1477 return *cols;
1478 }
1479
1480
1481
1482 template <typename number>
1483 inline typename ChunkSparseMatrix<number>::size_type
1484 ChunkSparseMatrix<number>::compute_location(const size_type i,
1485 const size_type j) const
1486 {
1487 const size_type chunk_size = cols->get_chunk_size();
1488 const size_type chunk_index =
1489 cols->sparsity_pattern(i / chunk_size, j / chunk_size);
1490
1491 if (chunk_index == ChunkSparsityPattern::invalid_entry)
1492 return ChunkSparsityPattern::invalid_entry;
1493 else
1494 {
1495 return (chunk_index * chunk_size * chunk_size +
1496 (i % chunk_size) * chunk_size + (j % chunk_size));
1497 }
1498 }
1499
1500
1501 template <typename number>
1502 inline void
1503 ChunkSparseMatrix<number>::set(const size_type i,
1504 const size_type j,
1505 const number value)
1506 {
1507 AssertIsFinite(value);
1508
1509 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1510 // it is allowed to set elements of the matrix that are not part of the
1511 // sparsity pattern, if the value to which we set it is zero
1512 const size_type index = compute_location(i, j);
1513 Assert((index != SparsityPattern::invalid_entry) || (value == 0.),
1514 ExcInvalidIndex(i, j));
1515
1516 if (index != SparsityPattern::invalid_entry)
1517 val[index] = value;
1518 }
1519
1520
1521
1522 template <typename number>
1523 inline void
1524 ChunkSparseMatrix<number>::add(const size_type i,
1525 const size_type j,
1526 const number value)
1527 {
1528 AssertIsFinite(value);
1529
1530 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1531
1532 if (std::abs(value) != 0.)
1533 {
1534 const size_type index = compute_location(i, j);
1535 Assert((index != ChunkSparsityPattern::invalid_entry),
1536 ExcInvalidIndex(i, j));
1537
1538 val[index] += value;
1539 }
1540 }
1541
1542
1543
1544 template <typename number>
1545 template <typename number2>
1546 inline void
1547 ChunkSparseMatrix<number>::add(const size_type row,
1548 const size_type n_cols,
1549 const size_type *col_indices,
1550 const number2 *values,
1551 const bool /*elide_zero_values*/,
1552 const bool /*col_indices_are_sorted*/)
1553 {
1554 // TODO: could be done more efficiently...
1555 for (size_type col = 0; col < n_cols; ++col)
1556 add(row, col_indices[col], static_cast<number>(values[col]));
1557 }
1558
1559
1560
1561 template <typename number>
1562 inline ChunkSparseMatrix<number> &
1563 ChunkSparseMatrix<number>::operator*=(const number factor)
1564 {
1565 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1566 Assert(val != nullptr, ExcNotInitialized());
1567
1568 const size_type chunk_size = cols->get_chunk_size();
1569
1570 // multiply all elements of the matrix with the given factor. this includes
1571 // the padding elements in chunks that overlap the boundaries of the actual
1572 // matrix -- but since multiplication with a number does not violate the
1573 // invariant of keeping these elements at zero nothing can happen
1574 number *val_ptr = val.get();
1575 const number *const end_ptr =
1576 val.get() +
1577 cols->sparsity_pattern.n_nonzero_elements() * chunk_size * chunk_size;
1578 while (val_ptr != end_ptr)
1579 *val_ptr++ *= factor;
1580
1581 return *this;
1582 }
1583
1584
1585
1586 template <typename number>
1587 inline ChunkSparseMatrix<number> &
1588 ChunkSparseMatrix<number>::operator/=(const number factor)
1589 {
1590 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1591 Assert(val != nullptr, ExcNotInitialized());
1592 Assert(std::abs(factor) != 0, ExcDivideByZero());
1593
1594 const number factor_inv = 1. / factor;
1595
1596 const size_type chunk_size = cols->get_chunk_size();
1597
1598 // multiply all elements of the matrix with the given factor. this includes
1599 // the padding elements in chunks that overlap the boundaries of the actual
1600 // matrix -- but since multiplication with a number does not violate the
1601 // invariant of keeping these elements at zero nothing can happen
1602 number *val_ptr = val.get();
1603 const number *const end_ptr =
1604 val.get() +
1605 cols->sparsity_pattern.n_nonzero_elements() * chunk_size * chunk_size;
1606
1607 while (val_ptr != end_ptr)
1608 *val_ptr++ *= factor_inv;
1609
1610 return *this;
1611 }
1612
1613
1614
1615 template <typename number>
1616 inline number
1617 ChunkSparseMatrix<number>::operator()(const size_type i,
1618 const size_type j) const
1619 {
1620 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1621 AssertThrow(compute_location(i, j) != SparsityPattern::invalid_entry,
1622 ExcInvalidIndex(i, j));
1623 return val[compute_location(i, j)];
1624 }
1625
1626
1627
1628 template <typename number>
1629 inline number
1630 ChunkSparseMatrix<number>::el(const size_type i, const size_type j) const
1631 {
1632 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1633 const size_type index = compute_location(i, j);
1634
1635 if (index != ChunkSparsityPattern::invalid_entry)
1636 return val[index];
1637 else
1638 return 0;
1639 }
1640
1641
1642
1643 template <typename number>
1644 inline number
1645 ChunkSparseMatrix<number>::diag_element(const size_type i) const
1646 {
1647 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1648 Assert(m() == n(), ExcNotQuadratic());
1649 AssertIndexRange(i, m());
1650
1651 // Use that the first element in each row of a quadratic matrix is the main
1652 // diagonal of the chunk sparsity pattern
1653 const size_type chunk_size = cols->get_chunk_size();
1654 return val[cols->sparsity_pattern.rowstart[i / chunk_size] * chunk_size *
1655 chunk_size +
1656 (i % chunk_size) * chunk_size + (i % chunk_size)];
1657 }
1658
1659
1660
1661 template <typename number>
1662 template <typename ForwardIterator>
1663 inline void
1664 ChunkSparseMatrix<number>::copy_from(const ForwardIterator begin,
1665 const ForwardIterator end)
1666 {
1667 Assert(static_cast<size_type>(std::distance(begin, end)) == m(),
1668 ExcIteratorRange(std::distance(begin, end), m()));
1669
1670 // for use in the inner loop, we define an alias to the type of the inner
1671 // iterators
1672 using inner_iterator =
1673 typename std::iterator_traits<ForwardIterator>::value_type::const_iterator;
1674 size_type row = 0;
1675 for (ForwardIterator i = begin; i != end; ++i, ++row)
1676 {
1677 const inner_iterator end_of_row = i->end();
1678 for (inner_iterator j = i->begin(); j != end_of_row; ++j)
1679 // write entries
1680 set(row, j->first, j->second);
1681 }
1682 }
1683
1684
1685
1686 //---------------------------------------------------------------------------
1687
1688
1689 namespace ChunkSparseMatrixIterators
1690 {
1691 template <typename number>
1692 inline Accessor<number, true>::Accessor(const MatrixType *matrix,
1693 const unsigned int row)
1694 : ChunkSparsityPatternIterators::Accessor(&matrix->get_sparsity_pattern(),
1695 row)
1696 , matrix(matrix)
1697 {}
1698
1699
1700
1701 template <typename number>
1702 inline Accessor<number, true>::Accessor(const MatrixType *matrix)
1703 : ChunkSparsityPatternIterators::Accessor(&matrix->get_sparsity_pattern())
1704 , matrix(matrix)
1705 {}
1706
1707
1708
1709 template <typename number>
1710 inline Accessor<number, true>::Accessor(
1711 const ChunkSparseMatrixIterators::Accessor<number, false> &a)
1712 : ChunkSparsityPatternIterators::Accessor(a)
1713 , matrix(&a.get_matrix())
1714 {}
1715
1716
1717
1718 template <typename number>
1719 inline number
1720 Accessor<number, true>::value() const
1721 {
1722 const unsigned int chunk_size =
1723 matrix->get_sparsity_pattern().get_chunk_size();
1724 return matrix->val[reduced_index() * chunk_size * chunk_size +
1725 chunk_row * chunk_size + chunk_col];
1726 }
1727
1728
1729
1730 template <typename number>
1731 inline const typename Accessor<number, true>::MatrixType &
1732 Accessor<number, true>::get_matrix() const
1733 {
1734 return *matrix;
1735 }
1736
1737
1738
1739 template <typename number>
1740 inline Accessor<number, false>::Reference::Reference(const Accessor *accessor,
1741 const bool)
1742 : accessor(accessor)
1743 {}
1744
1745
1746 template <typename number>
1747 inline Accessor<number, false>::Reference::operator number() const
1748 {
1749 const unsigned int chunk_size =
1750 accessor->matrix->get_sparsity_pattern().get_chunk_size();
1751 return accessor->matrix
1752 ->val[accessor->reduced_index() * chunk_size * chunk_size +
1753 accessor->chunk_row * chunk_size + accessor->chunk_col];
1754 }
1755
1756
1757
1758 template <typename number>
1759 inline const typename Accessor<number, false>::Reference &
1760 Accessor<number, false>::Reference::operator=(const number n) const
1761 {
1762 const unsigned int chunk_size =
1763 accessor->matrix->get_sparsity_pattern().get_chunk_size();
1764 accessor->matrix
1765 ->val[accessor->reduced_index() * chunk_size * chunk_size +
1766 accessor->chunk_row * chunk_size + accessor->chunk_col] = n;
1767 return *this;
1768 }
1769
1770
1771
1772 template <typename number>
1773 inline const typename Accessor<number, false>::Reference &
1774 Accessor<number, false>::Reference::operator+=(const number n) const
1775 {
1776 const unsigned int chunk_size =
1777 accessor->matrix->get_sparsity_pattern().get_chunk_size();
1778 accessor->matrix
1779 ->val[accessor->reduced_index() * chunk_size * chunk_size +
1780 accessor->chunk_row * chunk_size + accessor->chunk_col] += n;
1781 return *this;
1782 }
1783
1784
1785
1786 template <typename number>
1787 inline const typename Accessor<number, false>::Reference &
1788 Accessor<number, false>::Reference::operator-=(const number n) const
1789 {
1790 const unsigned int chunk_size =
1791 accessor->matrix->get_sparsity_pattern().get_chunk_size();
1792 accessor->matrix
1793 ->val[accessor->reduced_index() * chunk_size * chunk_size +
1794 accessor->chunk_row * chunk_size + accessor->chunk_col] -= n;
1795 return *this;
1796 }
1797
1798
1799
1800 template <typename number>
1801 inline const typename Accessor<number, false>::Reference &
1802 Accessor<number, false>::Reference::operator*=(const number n) const
1803 {
1804 const unsigned int chunk_size =
1805 accessor->matrix->get_sparsity_pattern().get_chunk_size();
1806 accessor->matrix
1807 ->val[accessor->reduced_index() * chunk_size * chunk_size +
1808 accessor->chunk_row * chunk_size + accessor->chunk_col] *= n;
1809 return *this;
1810 }
1811
1812
1813
1814 template <typename number>
1815 inline const typename Accessor<number, false>::Reference &
1816 Accessor<number, false>::Reference::operator/=(const number n) const
1817 {
1818 const unsigned int chunk_size =
1819 accessor->matrix->get_sparsity_pattern().get_chunk_size();
1820 accessor->matrix
1821 ->val[accessor->reduced_index() * chunk_size * chunk_size +
1822 accessor->chunk_row * chunk_size + accessor->chunk_col] /= n;
1823 return *this;
1824 }
1825
1826
1827
1828 template <typename number>
1829 inline Accessor<number, false>::Accessor(MatrixType *matrix,
1830 const unsigned int row)
1831 : ChunkSparsityPatternIterators::Accessor(&matrix->get_sparsity_pattern(),
1832 row)
1833 , matrix(matrix)
1834 {}
1835
1836
1837
1838 template <typename number>
1839 inline Accessor<number, false>::Accessor(MatrixType *matrix)
1840 : ChunkSparsityPatternIterators::Accessor(&matrix->get_sparsity_pattern())
1841 , matrix(matrix)
1842 {}
1843
1844
1845
1846 template <typename number>
1847 inline typename Accessor<number, false>::Reference
1848 Accessor<number, false>::value() const
1849 {
1850 return Reference(this, true);
1851 }
1852
1853
1854
1855 template <typename number>
1856 inline typename Accessor<number, false>::MatrixType &
1857 Accessor<number, false>::get_matrix() const
1858 {
1859 return *matrix;
1860 }
1861
1862
1863
1864 template <typename number, bool Constness>
1865 inline Iterator<number, Constness>::Iterator(MatrixType *matrix,
1866 const unsigned int row)
1867 : accessor(matrix, row)
1868 {}
1869
1870
1871
1872 template <typename number, bool Constness>
1873 inline Iterator<number, Constness>::Iterator(MatrixType *matrix)
1874 : accessor(matrix)
1875 {}
1876
1877
1878
1879 template <typename number, bool Constness>
1880 inline Iterator<number, Constness>::Iterator(
1881 const ChunkSparseMatrixIterators::Iterator<number, false> &i)
1882 : accessor(*i)
1883 {}
1884
1885
1886
1887 template <typename number, bool Constness>
1888 inline Iterator<number, Constness> &
1889 Iterator<number, Constness>::operator++()
1890 {
1891 accessor.advance();
1892 return *this;
1893 }
1894
1895
1896 template <typename number, bool Constness>
1897 inline Iterator<number, Constness>
1898 Iterator<number, Constness>::operator++(int)
1899 {
1900 const Iterator iter = *this;
1901 accessor.advance();
1902 return iter;
1903 }
1904
1905
1906 template <typename number, bool Constness>
1907 inline const Accessor<number, Constness> &
1908 Iterator<number, Constness>::operator*() const
1909 {
1910 return accessor;
1911 }
1912
1913
1914 template <typename number, bool Constness>
1915 inline const Accessor<number, Constness> *
1916 Iterator<number, Constness>::operator->() const
1917 {
1918 return &accessor;
1919 }
1920
1921
1922 template <typename number, bool Constness>
1923 inline bool
1924 Iterator<number, Constness>::operator==(const Iterator &other) const
1925 {
1926 return (accessor == other.accessor);
1927 }
1928
1929
1930 template <typename number, bool Constness>
1931 inline bool
1932 Iterator<number, Constness>::operator!=(const Iterator &other) const
1933 {
1934 return !(*this == other);
1935 }
1936
1937
1938 template <typename number, bool Constness>
1939 inline bool
1940 Iterator<number, Constness>::operator<(const Iterator &other) const
1941 {
1942 Assert(&accessor.get_matrix() == &other.accessor.get_matrix(),
1943 ExcInternalError());
1944
1945 return (accessor < other.accessor);
1946 }
1947
1948
1949 template <typename number, bool Constness>
1950 inline bool
1951 Iterator<number, Constness>::operator>(const Iterator &other) const
1952 {
1953 return (other < *this);
1954 }
1955
1956
1957 template <typename number, bool Constness>
1958 inline int
1959 Iterator<number, Constness>::operator-(const Iterator &other) const
1960 {
1961 Assert(&accessor.get_matrix() == &other.accessor.get_matrix(),
1962 ExcInternalError());
1963
1964 // TODO: can be optimized
1965 int difference = 0;
1966 if (*this < other)
1967 {
1968 Iterator copy = *this;
1969 while (copy != other)
1970 {
1971 ++copy;
1972 --difference;
1973 }
1974 }
1975 else
1976 {
1977 Iterator copy = other;
1978 while (copy != *this)
1979 {
1980 ++copy;
1981 ++difference;
1982 }
1983 }
1984 return difference;
1985 }
1986
1987
1988
1989 template <typename number, bool Constness>
1990 inline Iterator<number, Constness>
1991 Iterator<number, Constness>::operator+(const unsigned int n) const
1992 {
1993 Iterator x = *this;
1994 for (unsigned int i = 0; i < n; ++i)
1995 ++x;
1996
1997 return x;
1998 }
1999
2000 } // namespace ChunkSparseMatrixIterators
2001
2002
2003
2004 template <typename number>
2005 inline typename ChunkSparseMatrix<number>::const_iterator
2006 ChunkSparseMatrix<number>::begin() const
2007 {
2008 return const_iterator(this, 0);
2009 }
2010
2011
2012 template <typename number>
2013 inline typename ChunkSparseMatrix<number>::const_iterator
2014 ChunkSparseMatrix<number>::end() const
2015 {
2016 return const_iterator(this);
2017 }
2018
2019
2020 template <typename number>
2021 inline typename ChunkSparseMatrix<number>::iterator
2022 ChunkSparseMatrix<number>::begin()
2023 {
2024 return iterator(this, 0);
2025 }
2026
2027
2028 template <typename number>
2029 inline typename ChunkSparseMatrix<number>::iterator
2030 ChunkSparseMatrix<number>::end()
2031 {
2032 return iterator(this);
2033 }
2034
2035
2036 template <typename number>
2037 inline typename ChunkSparseMatrix<number>::const_iterator
2038 ChunkSparseMatrix<number>::begin(const unsigned int r) const
2039 {
2040 AssertIndexRange(r, m());
2041 return const_iterator(this, r);
2042 }
2043
2044
2045
2046 template <typename number>
2047 inline typename ChunkSparseMatrix<number>::const_iterator
2048 ChunkSparseMatrix<number>::end(const unsigned int r) const
2049 {
2050 AssertIndexRange(r, m());
2051 return const_iterator(this, r + 1);
2052 }
2053
2054
2055
2056 template <typename number>
2057 inline typename ChunkSparseMatrix<number>::iterator
2058 ChunkSparseMatrix<number>::begin(const unsigned int r)
2059 {
2060 AssertIndexRange(r, m());
2061 return iterator(this, r);
2062 }
2063
2064
2065
2066 template <typename number>
2067 inline typename ChunkSparseMatrix<number>::iterator
2068 ChunkSparseMatrix<number>::end(const unsigned int r)
2069 {
2070 AssertIndexRange(r, m());
2071 return iterator(this, r + 1);
2072 }
2073
2074
2075
2076 #endif // DOXYGEN
2077
2078 DEAL_II_NAMESPACE_CLOSE
2079
2080 #endif