Debian Codegraph @

include/deal.II/lac/sparse_matrix.templates.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 1999 - 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
16 #ifndef dealii_sparse_matrix_templates_h
17 #define dealii_sparse_matrix_templates_h
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/parallel.h>
22 #include <deal.II/base/template_constraints.h>
23 #include <deal.II/base/utilities.h>
24
25 #include <deal.II/lac/dynamic_sparsity_pattern.h>
26 #include <deal.II/lac/full_matrix.h>
27 #include <deal.II/lac/sparse_matrix.h>
28 #include <deal.II/lac/trilinos_sparse_matrix.h>
29 #include <deal.II/lac/vector.h>
30 #include <deal.II/lac/vector_memory.h>
31
32 #include <boost/io/ios_state.hpp>
33
34 #include <algorithm>
35 #include <cmath>
36 #include <functional>
37 #include <iomanip>
38 #include <numeric>
39 #include <ostream>
40 #include <vector>
41
42
43
44 DEAL_II_NAMESPACE_OPEN
45
46
47 template <typename number>
48 SparseMatrix<number>::SparseMatrix()
49 : cols(nullptr, "SparseMatrix")
50 , val(nullptr)
51 , max_len(0)
52 {}
53
54
55
56 template <typename number>
57 SparseMatrix<number>::SparseMatrix(const SparseMatrix &m)
58 : EnableObserverPointer(m)
59 , cols(nullptr, "SparseMatrix")
60 , val(nullptr)
61 , max_len(0)
62 {
63 Assert(m.cols == nullptr && m.val == nullptr && m.max_len == 0,
64 ExcMessage(
65 "This constructor can only be called if the provided argument "
66 "is an empty matrix. This constructor can not be used to "
67 "copy-construct a non-empty matrix. Use the "
68 "SparseMatrix::copy_from() function for that purpose."));
69 }
70
71
72
73 template <typename number>
74 SparseMatrix<number>::SparseMatrix(SparseMatrix<number> &&m) noexcept
75 : EnableObserverPointer(std::move(m))
76 , cols(std::move(m.cols))
77 , val(std::move(m.val))
78 , max_len(m.max_len)
79 {
80 m.cols = nullptr;
81 m.val = nullptr;
82 m.max_len = 0;
83 }
84
85
86
87 template <typename number>
88 SparseMatrix<number> &
89 SparseMatrix<number>::operator=(const SparseMatrix<number> &m)
90 {
91 Assert(m.cols == nullptr && m.val == nullptr && m.max_len == 0,
92 ExcMessage("This operator can only be called if the provided right "
93 "hand side is an empty matrix. This operator can not be "
94 "used to copy a non-empty matrix. Use the "
95 "SparseMatrix::copy_from() function for that purpose."));
96
97 return *this;
98 }
99
100
101
102 template <typename number>
103 SparseMatrix<number> &
104 SparseMatrix<number>::operator=(SparseMatrix<number> &&m) noexcept
105 {
106 cols = m.cols;
107 val = std::move(m.val);
108 max_len = m.max_len;
109
110 m.cols = nullptr;
111 m.val = nullptr;
112 m.max_len = 0;
113
114 return *this;
115 }
116
117
118
119 template <typename number>
120 SparseMatrix<number>::SparseMatrix(const SparsityPattern &c)
121 : cols(nullptr, "SparseMatrix")
122 , val(nullptr)
123 , max_len(0)
124 {
125 // virtual functions called in constructors and destructors never use the
126 // override in a derived class
127 // for clarity be explicit on which function is called
128 SparseMatrix<number>::reinit(c);
129 }
130
131
132
133 template <typename number>
134 SparseMatrix<number>::SparseMatrix(const SparsityPattern &c,
135 const IdentityMatrix &id)
136 : cols(nullptr, "SparseMatrix")
137 , val(nullptr)
138 , max_len(0)
139 {
140 Assert(c.n_rows() == id.m(), ExcDimensionMismatch(c.n_rows(), id.m()));
141 Assert(c.n_cols() == id.n(), ExcDimensionMismatch(c.n_cols(), id.n()));
142
143 // virtual functions called in constructors and destructors never use the
144 // override in a derived class
145 // for clarity be explicit on which function is called
146 SparseMatrix<number>::reinit(c);
147 for (size_type i = 0; i < n(); ++i)
148 this->set(i, i, 1.);
149 }
150
151
152
153 template <typename number>
154 SparseMatrix<number>::~SparseMatrix()
155 {
156 cols = nullptr;
157 }
158
159
160
161 template <typename number>
162 SparseMatrix<number> &
163 SparseMatrix<number>::operator=(const double d)
164 {
165 Assert(d == 0, ExcScalarAssignmentOnlyForZeroValue());
166
167 Assert(cols != nullptr, ExcNeedsSparsityPattern());
168 Assert(cols->compressed || cols->empty(),
169 SparsityPattern::ExcNotCompressed());
170
171 // do initial zeroing of elements in parallel. Try to achieve a similar
172 // layout as when doing matrix-vector products, as on some NUMA systems, a
173 // memory block is assigned to memory banks where the first access is
174 // generated. For sparse matrices, the first operations is usually the
175 // operator=. The grain size is chosen to reflect the number of rows in
176 // minimum_parallel_grain_size, weighted by the number of nonzero entries
177 // per row on average.
178 const std::size_t matrix_size = cols->n_nonzero_elements();
179 const size_type grain_size =
180 internal::SparseMatrixImplementation::minimum_parallel_grain_size *
181 (cols->n_nonzero_elements() + m()) / m();
182 if (matrix_size > grain_size)
183 parallel::apply_to_subranges(
184 0U,
185 matrix_size,
186 [values = this->val.get()](const size_type begin, const size_type end) {
187 std::fill(values + begin, values + end, number(0.));
188 },
189 grain_size);
190 else if (matrix_size > 0)
191 {
192 std::fill(val.get(), val.get() + matrix_size, 0);
193 }
194
195 return *this;
196 }
197
198
199
200 template <typename number>
201 SparseMatrix<number> &
202 SparseMatrix<number>::operator=(const IdentityMatrix &id)
203 {
204 Assert(cols->n_rows() == id.m(),
205 ExcDimensionMismatch(cols->n_rows(), id.m()));
206 Assert(cols->n_cols() == id.n(),
207 ExcDimensionMismatch(cols->n_cols(), id.n()));
208
209 *this = 0;
210 for (size_type i = 0; i < n(); ++i)
211 this->set(i, i, 1.);
212
213 return *this;
214 }
215
216
217
218 template <typename number>
219 void
220 SparseMatrix<number>::reinit(const SparsityPattern &sparsity)
221 {
222 cols = &sparsity;
223
224 if (cols->empty())
225 {
226 val.reset();
227 max_len = 0;
228 return;
229 }
230
231 const std::size_t N = cols->n_nonzero_elements();
232 if (N > max_len || max_len == 0)
233 {
234 val = std::make_unique<number[]>(N);
235 max_len = N;
236 }
237
238 *this = 0.;
239 }
240
241
242
243 template <typename number>
244 void
245 SparseMatrix<number>::clear()
246 {
247 cols = nullptr;
248 val.reset();
249 max_len = 0;
250 }
251
252
253
254 template <typename number>
255 bool
256 SparseMatrix<number>::empty() const
257 {
258 if (cols == nullptr)
259 return true;
260 else
261 return cols->empty();
262 }
263
264
265
266 template <typename number>
267 typename SparseMatrix<number>::size_type
268 SparseMatrix<number>::get_row_length(const size_type row) const
269 {
270 Assert(cols != nullptr, ExcNeedsSparsityPattern());
271 return cols->row_length(row);
272 }
273
274
275
276 template <typename number>
277 std::size_t
278 SparseMatrix<number>::n_nonzero_elements() const
279 {
280 Assert(cols != nullptr, ExcNeedsSparsityPattern());
281 return cols->n_nonzero_elements();
282 }
283
284
285
286 template <typename number>
287 std::size_t
288 SparseMatrix<number>::n_actually_nonzero_elements(const double threshold) const
289 {
290 Assert(cols != nullptr, ExcNeedsSparsityPattern());
291 Assert(threshold >= 0, ExcMessage("Negative threshold!"));
292 size_type nnz = 0;
293 const std::size_t nnz_alloc = n_nonzero_elements();
294 for (size_type i = 0; i < nnz_alloc; ++i)
295 if (std::abs(val[i]) > threshold)
296 ++nnz;
297 return nnz;
298 }
299
300
301
302 template <typename number>
303 void
304 SparseMatrix<number>::symmetrize()
305 {
306 Assert(cols != nullptr, ExcNeedsSparsityPattern());
307 Assert(cols->rows == cols->cols, ExcNotQuadratic());
308
309 const size_type n_rows = m();
310 for (size_type row = 0; row < n_rows; ++row)
311 {
312 // first skip diagonal entry
313 number *val_ptr = &val[cols->rowstart[row]];
314 if (m() == n())
315 ++val_ptr;
316 const size_type *colnum_ptr = &cols->colnums[cols->rowstart[row] + 1];
317 const number *const val_end_of_row = &val[cols->rowstart[row + 1]];
318
319 // treat lower left triangle
320 while ((val_ptr != val_end_of_row) && (*colnum_ptr < row))
321 {
322 // compute the mean of this
323 // and the transpose value
324 const number mean_value =
325 (*val_ptr + val[(*cols)(*colnum_ptr, row)]) / number(2.0);
326 // set this value and the
327 // transpose one to the
328 // mean
329 *val_ptr = mean_value;
330 set(*colnum_ptr, row, mean_value);
331
332 // advance pointers
333 ++val_ptr;
334 ++colnum_ptr;
335 };
336 };
337 }
338
339
340
341 template <typename number>
342 template <typename somenumber>
343 SparseMatrix<number> &
344 SparseMatrix<number>::copy_from(const SparseMatrix<somenumber> &matrix)
345 {
346 Assert(cols != nullptr, ExcNeedsSparsityPattern());
347 Assert(val != nullptr, ExcNotInitialized());
348 Assert(cols == matrix.cols, ExcDifferentSparsityPatterns());
349
350 std::copy(matrix.val.get(),
351 matrix.val.get() + cols->n_nonzero_elements(),
352 val.get());
353
354 return *this;
355 }
356
357
358
359 template <typename number>
360 template <typename somenumber>
361 void
362 SparseMatrix<number>::copy_from(const FullMatrix<somenumber> &matrix)
363 {
364 // first delete previous content
365 *this = 0;
366
367 // then copy old matrix
368 for (size_type row = 0; row < matrix.m(); ++row)
369 for (size_type col = 0; col < matrix.n(); ++col)
370 if (matrix(row, col) != somenumber())
371 set(row, col, number(matrix(row, col)));
372 }
373
374
375
376 #ifdef DEAL_II_WITH_TRILINOS
377
378 template <typename number>
379 SparseMatrix<number> &
380 SparseMatrix<number>::copy_from(const TrilinosWrappers::SparseMatrix &matrix)
381 {
382 Assert(m() == matrix.m(), ExcDimensionMismatch(m(), matrix.m()));
383 Assert(n() == matrix.n(), ExcDimensionMismatch(n(), matrix.n()));
384
385 // first delete previous content
386 *this = 0;
387
388 std::vector<TrilinosScalar> value_cache;
389 std::vector<size_type> colnum_cache;
390
391 for (size_type row = 0; row < matrix.m(); ++row)
392 {
393 value_cache.resize(matrix.n());
394 colnum_cache.resize(matrix.n());
395
396 // copy column indices and values and at the same time enquire about the
397 // length of the row
398 int ncols;
399 int ierr = matrix.trilinos_matrix().ExtractGlobalRowCopy(
400 row,
401 matrix.row_length(row),
402 ncols,
403 value_cache.data(),
404 reinterpret_cast<TrilinosWrappers::types::int_type *>(
405 colnum_cache.data()));
406 Assert(ierr == 0, ExcTrilinosError(ierr));
407
408 // resize arrays to the size actually used
409 value_cache.resize(ncols);
410 colnum_cache.resize(ncols);
411
412 // then copy everything in one swoop
413 this->set(row, colnum_cache, value_cache);
414 }
415
416 return *this;
417 }
418
419 #endif
420
421
422 template <typename number>
423 template <typename somenumber>
424 void
425 SparseMatrix<number>::add(const number factor,
426 const SparseMatrix<somenumber> &matrix)
427 {
428 Assert(cols != nullptr, ExcNeedsSparsityPattern());
429 Assert(val != nullptr, ExcNotInitialized());
430 Assert(cols == matrix.cols, ExcDifferentSparsityPatterns());
431
432 number *val_ptr = val.get();
433 const somenumber *matrix_ptr = matrix.val.get();
434 const number *const end_ptr = val.get() + cols->n_nonzero_elements();
435
436 while (val_ptr != end_ptr)
437 *val_ptr++ += factor * number(*matrix_ptr++);
438 }
439
440
441
442 namespace internal
443 {
444 namespace SparseMatrixImplementation
445 {
446 using size_type = types::global_dof_index;
447
448 /**
449 * Perform a vmult using the SparseMatrix data structures, but only using
450 * a subinterval for the row indices.
451 *
452 * In the sequential case, this function is called on all rows, in the
453 * parallel case it may be called on a subrange, at the discretion of the
454 * task scheduler.
455 */
456 template <typename number, typename InVector, typename OutVector>
457 void
458 vmult_on_subrange(const size_type begin_row,
459 const size_type end_row,
460 const number *values,
461 const std::size_t *rowstart,
462 const size_type *colnums,
463 const InVector &src,
464 OutVector &dst,
465 const bool add)
466 {
467 const number *val_ptr = &values[rowstart[begin_row]];
468 const size_type *colnum_ptr = &colnums[rowstart[begin_row]];
469 typename OutVector::iterator dst_ptr = dst.begin() + begin_row;
470
471 if (add == false)
472 for (size_type row = begin_row; row < end_row; ++row)
473 {
474 typename OutVector::value_type s = 0.;
475 const number *const val_end_of_row = &values[rowstart[row + 1]];
476 while (val_ptr != val_end_of_row)
477 s += typename OutVector::value_type(*val_ptr++) *
478 typename OutVector::value_type(src(*colnum_ptr++));
479 *dst_ptr++ = s;
480 }
481 else
482 for (size_type row = begin_row; row < end_row; ++row)
483 {
484 typename OutVector::value_type s = *dst_ptr;
485 const number *const val_end_of_row = &values[rowstart[row + 1]];
486 while (val_ptr != val_end_of_row)
487 s += typename OutVector::value_type(*val_ptr++) *
488 typename OutVector::value_type(src(*colnum_ptr++));
489 *dst_ptr++ = s;
490 }
491 }
492 } // namespace SparseMatrixImplementation
493 } // namespace internal
494
495
496 template <typename number>
497 template <typename number2>
498 void
499 SparseMatrix<number>::add(const size_type row,
500 const size_type n_cols,
501 const size_type *col_indices,
502 const number2 *values,
503 const bool elide_zero_values,
504 const bool col_indices_are_sorted)
505 {
506 Assert(cols != nullptr, ExcNeedsSparsityPattern());
507 AssertIndexRange(row, m());
508
509 // if we have sufficiently many columns
510 // and sorted indices it is faster to
511 // just go through the column indices and
512 // look whether we found one, rather than
513 // doing many binary searches
514 if (elide_zero_values == false && col_indices_are_sorted == true &&
515 n_cols > 3)
516 {
517 // check whether the given indices are
518 // really sorted
519 if constexpr (running_in_debug_mode())
520 {
521 for (size_type i = 1; i < n_cols; ++i)
522 Assert(col_indices[i] > col_indices[i - 1],
523 ExcMessage(
524 "List of indices is unsorted or contains duplicates."));
525 }
526
527 const size_type *this_cols = &cols->colnums[cols->rowstart[row]];
528 const size_type row_length_1 = cols->row_length(row) - 1;
529 number *val_ptr = &val[cols->rowstart[row]];
530
531 if (m() == n())
532 {
533 // find diagonal and add it if found
534 Assert(this_cols[0] == row, ExcInternalError());
535 const size_type *diag_pos =
536 Utilities::lower_bound(col_indices, col_indices + n_cols, row);
537 const size_type diag = diag_pos - col_indices;
538 size_type post_diag = diag;
539 if (diag != n_cols && *diag_pos == row)
540 {
541 val_ptr[0] += *(values + (diag_pos - col_indices));
542 ++post_diag;
543 }
544
545 // Add indices before diagonal. Because the input array
546 // is sorted, and because the entries in this matrix row
547 // are sorted, we can just linearly walk the colnums array
548 // and the input array in parallel, stopping whenever the
549 // former matches the column index of the next index in
550 // the input array:
551 size_type counter = 1;
552 for (size_type i = 0; i < diag; ++i)
553 {
554 while (this_cols[counter] < col_indices[i] &&
555 counter < row_length_1)
556 ++counter;
557
558 Assert((this_cols[counter] == col_indices[i]) ||
559 (values[i] == number2()),
560 ExcInvalidIndex(row, col_indices[i]));
561
562 val_ptr[counter] += values[i];
563 }
564
565 // Then do the same to add indices after the diagonal:
566 for (size_type i = post_diag; i < n_cols; ++i)
567 {
568 while (this_cols[counter] < col_indices[i] &&
569 counter < row_length_1)
570 ++counter;
571
572 Assert((this_cols[counter] == col_indices[i]) ||
573 (values[i] == number2()),
574 ExcInvalidIndex(row, col_indices[i]));
575
576 val_ptr[counter] += values[i];
577 }
578
579 Assert(counter < cols->row_length(row),
580 ExcMessage(
581 "Specified invalid column indices in add function."));
582 }
583 else
584 {
585 // Use the same algorithm as above, but because the matrix is
586 // not square, we can now do without the split for diagonal/
587 // entries before the diagonal/entries are the diagonal.
588 size_type counter = 0;
589 for (size_type i = 0; i < n_cols; ++i)
590 {
591 while (this_cols[counter] < col_indices[i] &&
592 counter < row_length_1)
593 ++counter;
594
595 Assert((this_cols[counter] == col_indices[i]) ||
596 (values[i] == number2()),
597 ExcInvalidIndex(row, col_indices[i]));
598
599 val_ptr[counter] += values[i];
600 }
601 Assert(counter < cols->row_length(row),
602 ExcMessage(
603 "Specified invalid column indices in add function."));
604 }
605 return;
606 }
607
608 // unsorted case: first, search all the
609 // indices to find out which values we
610 // actually need to add.
611 const size_type *const my_cols = cols->colnums.get();
612 size_type index = cols->rowstart[row];
613 const size_type next_row_index = cols->rowstart[row + 1];
614
615 for (size_type j = 0; j < n_cols; ++j)
616 {
617 const number value = number(values[j]);
618 AssertIsFinite(value);
619
620 if constexpr (running_in_debug_mode())
621 {
622 if (elide_zero_values == true && value == number())
623 continue;
624 }
625 else
626 {
627 if (value == number())
628 continue;
629 }
630
631 // check whether the next index to add is
632 // the next present index in the sparsity
633 // pattern (otherwise, do a binary
634 // search)
635 if (index < next_row_index && my_cols[index] == col_indices[j])
636 goto add_value;
637
638 index = cols->operator()(row, col_indices[j]);
639
640 // it is allowed to add elements to
641 // the matrix that are not part of
642 // the sparsity pattern, if the
643 // value we add is zero
644 if (index == SparsityPattern::invalid_entry)
645 {
646 Assert(value == number(), ExcInvalidIndex(row, col_indices[j]));
647 continue;
648 }
649
650 add_value:
651 val[index] += value;
652 ++index;
653 }
654 }
655
656
657
658 template <typename number>
659 template <typename number2>
660 void
661 SparseMatrix<number>::set(const size_type row,
662 const size_type n_cols,
663 const size_type *col_indices,
664 const number2 *values,
665 const bool elide_zero_values)
666 {
667 Assert(cols != nullptr, ExcNeedsSparsityPattern());
668 AssertIndexRange(row, m());
669
670 // First, search all the indices to find
671 // out which values we actually need to
672 // set.
673 const size_type *my_cols = cols->colnums.get();
674 std::size_t index = cols->rowstart[row], next_index = index;
675 const std::size_t next_row_index = cols->rowstart[row + 1];
676
677 if (elide_zero_values == true)
678 {
679 for (size_type j = 0; j < n_cols; ++j)
680 {
681 const number value = number(values[j]);
682 AssertIsFinite(value);
683
684 if (value == number())
685 continue;
686
687 // check whether the next index to set is
688 // the next present index in the sparsity
689 // pattern (otherwise, do a binary
690 // search)
691 if (index != next_row_index && my_cols[index] == col_indices[j])
692 goto set_value;
693
694 next_index = cols->operator()(row, col_indices[j]);
695
696 // it is allowed to set elements in
697 // the matrix that are not part of
698 // the sparsity pattern, if the
699 // value to which we set it is zero
700 if (next_index == SparsityPattern::invalid_entry)
701 {
702 Assert(false, ExcInvalidIndex(row, col_indices[j]));
703 continue;
704 }
705 index = next_index;
706
707 set_value:
708 val[index] = value;
709 ++index;
710 }
711 }
712 else
713 {
714 // same code as above, but now check for zeros
715 for (size_type j = 0; j < n_cols; ++j)
716 {
717 const number value = number(values[j]);
718 AssertIsFinite(value);
719
720 if (index != next_row_index && my_cols[index] == col_indices[j])
721 goto set_value_checked;
722
723 next_index = cols->operator()(row, col_indices[j]);
724
725 if (next_index == SparsityPattern::invalid_entry)
726 {
727 Assert(value == number(), ExcInvalidIndex(row, col_indices[j]));
728 continue;
729 }
730 index = next_index;
731
732 set_value_checked:
733 val[index] = value;
734 ++index;
735 }
736 }
737 }
738
739
740
741 template <typename number>
742 template <class OutVector, class InVector>
743 void
744 SparseMatrix<number>::vmult(OutVector &dst, const InVector &src) const
745 {
746 Assert(cols != nullptr, ExcNeedsSparsityPattern());
747 Assert(val != nullptr, ExcNotInitialized());
748 Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size()));
749 Assert(n() == src.size(), ExcDimensionMismatch(n(), src.size()));
750
751 Assert(!PointerComparison::equal(&src, &dst), ExcSourceEqualsDestination());
752
753 parallel::apply_to_subranges(
754 0U,
755 m(),
756 [this, &src, &dst](const size_type begin_row, const size_type end_row) {
757 internal::SparseMatrixImplementation::vmult_on_subrange(
758 begin_row,
759 end_row,
760 val.get(),
761 cols->rowstart.get(),
762 cols->colnums.get(),
763 src,
764 dst,
765 false);
766 },
767 internal::SparseMatrixImplementation::minimum_parallel_grain_size);
768 }
769
770
771
772 template <typename number>
773 template <class OutVector, class InVector>
774 void
775 SparseMatrix<number>::Tvmult(OutVector &dst, const InVector &src) const
776 {
777 Assert(val != nullptr, ExcNotInitialized());
778 Assert(cols != nullptr, ExcNeedsSparsityPattern());
779 Assert(n() == dst.size(), ExcDimensionMismatch(n(), dst.size()));
780 Assert(m() == src.size(), ExcDimensionMismatch(m(), src.size()));
781
782 Assert(!PointerComparison::equal(&src, &dst), ExcSourceEqualsDestination());
783
784 dst = 0;
785
786 for (size_type i = 0; i < m(); ++i)
787 {
788 for (size_type j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j)
789 {
790 const size_type p = cols->colnums[j];
791 dst(p) += typename OutVector::value_type(val[j]) *
792 typename OutVector::value_type(src(i));
793 }
794 }
795 }
796
797
798
799 template <typename number>
800 template <class OutVector, class InVector>
801 void
802 SparseMatrix<number>::vmult_add(OutVector &dst, const InVector &src) const
803 {
804 Assert(cols != nullptr, ExcNeedsSparsityPattern());
805 Assert(val != nullptr, ExcNotInitialized());
806 Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size()));
807 Assert(n() == src.size(), ExcDimensionMismatch(n(), src.size()));
808
809 Assert(!PointerComparison::equal(&src, &dst), ExcSourceEqualsDestination());
810
811 parallel::apply_to_subranges(
812 0U,
813 m(),
814 [this, &src, &dst](const size_type begin_row, const size_type end_row) {
815 internal::SparseMatrixImplementation::vmult_on_subrange(
816 begin_row,
817 end_row,
818 val.get(),
819 cols->rowstart.get(),
820 cols->colnums.get(),
821 src,
822 dst,
823 true);
824 },
825 internal::SparseMatrixImplementation::minimum_parallel_grain_size);
826 }
827
828
829
830 template <typename number>
831 template <class OutVector, class InVector>
832 void
833 SparseMatrix<number>::Tvmult_add(OutVector &dst, const InVector &src) const
834 {
835 Assert(val != nullptr, ExcNotInitialized());
836 Assert(cols != nullptr, ExcNeedsSparsityPattern());
837 Assert(n() == dst.size(), ExcDimensionMismatch(n(), dst.size()));
838 Assert(m() == src.size(), ExcDimensionMismatch(m(), src.size()));
839
840 Assert(!PointerComparison::equal(&src, &dst), ExcSourceEqualsDestination());
841
842 for (size_type i = 0; i < m(); ++i)
843 for (size_type j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j)
844 {
845 const size_type p = cols->colnums[j];
846 dst(p) += typename OutVector::value_type(val[j]) *
847 typename OutVector::value_type(src(i));
848 }
849 }
850
851
852 namespace internal
853 {
854 namespace SparseMatrixImplementation
855 {
856 /**
857 * Perform a vmult using the SparseMatrix data structures, but only using
858 * a subinterval for the row indices.
859 *
860 * In the sequential case, this function is called on all rows, in the
861 * parallel case it may be called on a subrange, at the discretion of the
862 * task scheduler.
863 */
864 template <typename number, typename InVector>
865 typename InVector::value_type
866 matrix_norm_sqr_on_subrange(const size_type begin_row,
867 const size_type end_row,
868 const number *values,
869 const std::size_t *rowstart,
870 const size_type *colnums,
871 const InVector &v)
872 {
873 typename InVector::value_type norm_sqr = 0.;
874
875 for (size_type i = begin_row; i < end_row; ++i)
876 {
877 typename InVector::value_type s = 0;
878 for (size_type j = rowstart[i]; j < rowstart[i + 1]; ++j)
879 s += typename InVector::value_type(values[j]) * v(colnums[j]);
880 norm_sqr +=
881 v(i) *
882 numbers::NumberTraits<typename InVector::value_type>::conjugate(s);
883 }
884 return norm_sqr;
885 }
886 } // namespace SparseMatrixImplementation
887 } // namespace internal
888
889
890
891 template <typename number>
892 template <typename somenumber>
893 somenumber
894 SparseMatrix<number>::matrix_norm_square(const Vector<somenumber> &v) const
895 {
896 Assert(cols != nullptr, ExcNeedsSparsityPattern());
897 Assert(val != nullptr, ExcNotInitialized());
898 Assert(m() == v.size(), ExcDimensionMismatch(m(), v.size()));
899 Assert(n() == v.size(), ExcDimensionMismatch(n(), v.size()));
900
901 return parallel::accumulate_from_subranges<somenumber>(
902 [this, &v](const size_type begin_row, const size_type end_row) {
903 return internal::SparseMatrixImplementation::matrix_norm_sqr_on_subrange(
904 begin_row,
905 end_row,
906 val.get(),
907 cols->rowstart.get(),
908 cols->colnums.get(),
909 v);
910 },
911 0,
912 m(),
913 internal::SparseMatrixImplementation::minimum_parallel_grain_size);
914 }
915
916
917
918 namespace internal
919 {
920 namespace SparseMatrixImplementation
921 {
922 /**
923 * Perform a vmult using the SparseMatrix data structures, but only using
924 * a subinterval for the row indices.
925 *
926 * In the sequential case, this function is called on all rows, in the
927 * parallel case it may be called on a subrange, at the discretion of the
928 * task scheduler.
929 */
930 template <typename number, typename InVector>
931 typename InVector::value_type
932 matrix_scalar_product_on_subrange(const size_type begin_row,
933 const size_type end_row,
934 const number *values,
935 const std::size_t *rowstart,
936 const size_type *colnums,
937 const InVector &u,
938 const InVector &v)
939 {
940 typename InVector::value_type norm_sqr = 0.;
941
942 for (size_type i = begin_row; i < end_row; ++i)
943 {
944 typename InVector::value_type s = 0;
945 for (size_type j = rowstart[i]; j < rowstart[i + 1]; ++j)
946 s += typename InVector::value_type(values[j]) * v(colnums[j]);
947 norm_sqr +=
948 u(i) *
949 numbers::NumberTraits<typename InVector::value_type>::conjugate(s);
950 }
951 return norm_sqr;
952 }
953 } // namespace SparseMatrixImplementation
954 } // namespace internal
955
956
957
958 template <typename number>
959 template <typename somenumber>
960 somenumber
961 SparseMatrix<number>::matrix_scalar_product(const Vector<somenumber> &u,
962 const Vector<somenumber> &v) const
963 {
964 Assert(cols != nullptr, ExcNeedsSparsityPattern());
965 Assert(val != nullptr, ExcNotInitialized());
966 Assert(m() == u.size(), ExcDimensionMismatch(m(), u.size()));
967 Assert(n() == v.size(), ExcDimensionMismatch(n(), v.size()));
968
969 return parallel::accumulate_from_subranges<somenumber>(
970 [this, &u, &v](const size_type begin_row, const size_type end_row) {
971 return internal::SparseMatrixImplementation::
972 matrix_scalar_product_on_subrange(begin_row,
973 end_row,
974 val.get(),
975 cols->rowstart.get(),
976 cols->colnums.get(),
977 u,
978 v);
979 },
980 0,
981 m(),
982 internal::SparseMatrixImplementation::minimum_parallel_grain_size);
983 }
984
985
986
987 template <typename number>
988 template <typename numberB, typename numberC>
989 void
990 SparseMatrix<number>::mmult(SparseMatrix<numberC> &C,
991 const SparseMatrix<numberB> &B,
992 const Vector<number> &V,
993 const bool rebuild_sparsity_C) const
994 {
995 const bool use_vector = V.size() == n() ? true : false;
996 Assert(n() == B.m(), ExcDimensionMismatch(n(), B.m()));
997 Assert(cols != nullptr, ExcNeedsSparsityPattern());
998 Assert(B.cols != nullptr, ExcNeedsSparsityPattern());
999 Assert(C.cols != nullptr, ExcNeedsSparsityPattern());
1000
1001 const SparsityPattern &sp_A = *cols;
1002 const SparsityPattern &sp_B = *B.cols;
1003
1004 // clear previous content of C
1005 if (rebuild_sparsity_C == true)
1006 {
1007 // we are about to change the sparsity pattern of C. this can not work
1008 // if either A or B use the same sparsity pattern
1009 Assert(&C.get_sparsity_pattern() != &this->get_sparsity_pattern(),
1010 ExcMessage("Can't use the same sparsity pattern for "
1011 "different matrices if it is to be rebuilt."));
1012 Assert(&C.get_sparsity_pattern() != &B.get_sparsity_pattern(),
1013 ExcMessage("Can't use the same sparsity pattern for "
1014 "different matrices if it is to be rebuilt."));
1015
1016 // need to change the sparsity pattern of C, so cast away const-ness.
1017 SparsityPattern &sp_C =
1018 *(const_cast<SparsityPattern *>(&C.get_sparsity_pattern()));
1019 C.clear();
1020 sp_C.reinit(0, 0, 0);
1021
1022 // create a sparsity pattern for the matrix C.
1023 {
1024 DynamicSparsityPattern dsp;
1025 dsp.compute_mmult_pattern(sp_A, sp_B);
1026 sp_C.copy_from(dsp);
1027 }
1028
1029 // reinit matrix C from that information
1030 C.reinit(sp_C);
1031 }
1032
1033 Assert(C.m() == m(), ExcDimensionMismatch(C.m(), m()));
1034 Assert(C.n() == B.n(), ExcDimensionMismatch(C.n(), B.n()));
1035
1036 // create an array that caches some
1037 // elements that are going to be written
1038 // into the new matrix.
1039 unsigned int max_n_cols_B = 0;
1040 for (size_type i = 0; i < B.m(); ++i)
1041 max_n_cols_B = std::max(max_n_cols_B, sp_B.row_length(i));
1042 std::vector<numberC> new_entries(max_n_cols_B);
1043
1044 // now compute the actual entries: a matrix-matrix product involves three
1045 // nested loops. One over the rows of A, for each row we then loop over all
1046 // the columns, and then we need to multiply each element with all the
1047 // elements in that row in B.
1048 for (size_type i = 0; i < C.m(); ++i)
1049 {
1050 const size_type *rows = &sp_A.colnums[sp_A.rowstart[i]];
1051 const size_type *const end_rows = &sp_A.colnums[sp_A.rowstart[i + 1]];
1052 for (; rows != end_rows; ++rows)
1053 {
1054 const number A_val = val[rows - &sp_A.colnums[sp_A.rowstart[0]]];
1055 const size_type col = *rows;
1056 const size_type *new_cols = (&sp_B.colnums[sp_B.rowstart[col]]);
1057
1058 // special treatment for diagonal
1059 if (sp_B.n_rows() == sp_B.n_cols())
1060 {
1061 C.add(i,
1062 *new_cols,
1063 numberC(A_val) *
1064 numberC(
1065 B.val[new_cols - &sp_B.colnums[sp_B.rowstart[0]]]) *
1066 numberC(use_vector ? V(col) : 1));
1067 ++new_cols;
1068 }
1069
1070 // now the innermost loop that goes over all the elements in row
1071 // 'col' of matrix B. Cache the elements, and then write them into C
1072 // at once
1073 numberC *new_ptr = new_entries.data();
1074 const numberB *B_val_ptr =
1075 &B.val[new_cols - &sp_B.colnums[sp_B.rowstart[0]]];
1076 const numberB *const end_cols = &B.val[sp_B.rowstart[col + 1]];
1077 for (; B_val_ptr != end_cols; ++B_val_ptr)
1078 *new_ptr++ = numberC(A_val) * numberC(*B_val_ptr) *
1079 numberC(use_vector ? V(col) : 1);
1080
1081 C.add(i,
1082 new_ptr - new_entries.data(),
1083 new_cols,
1084 new_entries.data(),
1085 false,
1086 true);
1087 }
1088 }
1089 }
1090
1091
1092
1093 template <typename number>
1094 template <typename numberB, typename numberC>
1095 void
1096 SparseMatrix<number>::Tmmult(SparseMatrix<numberC> &C,
1097 const SparseMatrix<numberB> &B,
1098 const Vector<number> &V,
1099 const bool rebuild_sparsity_C) const
1100 {
1101 const bool use_vector = V.size() == m() ? true : false;
1102 Assert(m() == B.m(), ExcDimensionMismatch(m(), B.m()));
1103 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1104 Assert(B.cols != nullptr, ExcNeedsSparsityPattern());
1105 Assert(C.cols != nullptr, ExcNeedsSparsityPattern());
1106
1107 const SparsityPattern &sp_A = *cols;
1108 const SparsityPattern &sp_B = *B.cols;
1109
1110 // clear previous content of C
1111 if (rebuild_sparsity_C == true)
1112 {
1113 // we are about to change the sparsity pattern of C. this can not work
1114 // if either A or B use the same sparsity pattern
1115 Assert(&C.get_sparsity_pattern() != &this->get_sparsity_pattern(),
1116 ExcMessage("Can't use the same sparsity pattern for "
1117 "different matrices if it is to be rebuilt."));
1118 Assert(&C.get_sparsity_pattern() != &B.get_sparsity_pattern(),
1119 ExcMessage("Can't use the same sparsity pattern for "
1120 "different matrices if it is to be rebuilt."));
1121
1122 // need to change the sparsity pattern of C, so cast away const-ness.
1123 SparsityPattern &sp_C =
1124 *(const_cast<SparsityPattern *>(&C.get_sparsity_pattern()));
1125 C.clear();
1126 sp_C.reinit(0, 0, 0);
1127
1128 // create a sparsity pattern for the matrix.
1129 {
1130 DynamicSparsityPattern dsp;
1131 dsp.compute_Tmmult_pattern(sp_A, sp_B);
1132 sp_C.copy_from(dsp);
1133 }
1134
1135 // reinit matrix C from that information
1136 C.reinit(sp_C);
1137 }
1138
1139 Assert(C.m() == n(), ExcDimensionMismatch(C.m(), n()));
1140 Assert(C.n() == B.n(), ExcDimensionMismatch(C.n(), B.n()));
1141
1142 // create an array that caches some
1143 // elements that are going to be written
1144 // into the new matrix.
1145 unsigned int max_n_cols_B = 0;
1146 for (size_type i = 0; i < B.m(); ++i)
1147 max_n_cols_B = std::max(max_n_cols_B, sp_B.row_length(i));
1148 std::vector<numberC> new_entries(max_n_cols_B);
1149
1150 // now compute the actual entries: a matrix-matrix product involves three
1151 // nested loops. One over the rows of A, for each row we then loop over all
1152 // the columns, and then we need to multiply each element with all the
1153 // elements in that row in B.
1154 for (size_type i = 0; i < m(); ++i)
1155 {
1156 const size_type *rows = &sp_A.colnums[sp_A.rowstart[i]];
1157 const size_type *const end_rows = &sp_A.colnums[sp_A.rowstart[i + 1]];
1158 const size_type *new_cols = &sp_B.colnums[sp_B.rowstart[i]];
1159 if (sp_B.n_rows() == sp_B.n_cols())
1160 ++new_cols;
1161
1162 const numberB *const end_cols = &B.val[sp_B.rowstart[i + 1]];
1163
1164 for (; rows != end_rows; ++rows)
1165 {
1166 const size_type row = *rows;
1167 const number A_val = val[rows - &sp_A.colnums[sp_A.rowstart[0]]];
1168
1169 // special treatment for diagonal
1170 if (sp_B.n_rows() == sp_B.n_cols())
1171 C.add(row,
1172 i,
1173 numberC(A_val) *
1174 numberC(
1175 B.val[new_cols - 1 - &sp_B.colnums[sp_B.rowstart[0]]]) *
1176 numberC(use_vector ? V(i) : 1));
1177
1178 // now the innermost loop that goes over all the elements in row
1179 // 'col' of matrix B. Cache the elements, and then write them into C
1180 // at once
1181 numberC *new_ptr = new_entries.data();
1182 const numberB *B_val_ptr =
1183 &B.val[new_cols - &sp_B.colnums[sp_B.rowstart[0]]];
1184 for (; B_val_ptr != end_cols; ++B_val_ptr)
1185 *new_ptr++ = numberC(A_val) * numberC(*B_val_ptr) *
1186 numberC(use_vector ? V(i) : 1);
1187
1188 C.add(row,
1189 new_ptr - new_entries.data(),
1190 new_cols,
1191 new_entries.data(),
1192 false,
1193 true);
1194 }
1195 }
1196 }
1197
1198
1199
1200 template <typename number>
1201 typename SparseMatrix<number>::real_type
1202 SparseMatrix<number>::l1_norm() const
1203 {
1204 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1205 Assert(val != nullptr, ExcNotInitialized());
1206
1207 Vector<real_type> column_sums(n());
1208 const size_type n_rows = m();
1209 for (size_type row = 0; row < n_rows; ++row)
1210 for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j)
1211 column_sums(cols->colnums[j]) +=
1212 numbers::NumberTraits<number>::abs(val[j]);
1213
1214 return column_sums.linfty_norm();
1215 }
1216
1217
1218
1219 template <typename number>
1220 typename SparseMatrix<number>::real_type
1221 SparseMatrix<number>::linfty_norm() const
1222 {
1223 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1224 Assert(val != nullptr, ExcNotInitialized());
1225
1226 const number *val_ptr = &val[cols->rowstart[0]];
1227
1228 real_type max = 0;
1229 const size_type n_rows = m();
1230 for (size_type row = 0; row < n_rows; ++row)
1231 {
1232 real_type sum = 0;
1233 const number *const val_end_of_row = &val[cols->rowstart[row + 1]];
1234 while (val_ptr != val_end_of_row)
1235 sum += numbers::NumberTraits<number>::abs(*val_ptr++);
1236 if (sum > max)
1237 max = sum;
1238 }
1239 return max;
1240 }
1241
1242
1243
1244 template <typename number>
1245 typename SparseMatrix<number>::real_type
1246 SparseMatrix<number>::frobenius_norm() const
1247 {
1248 // simply add up all entries in the
1249 // sparsity pattern, without taking any
1250 // reference to rows or columns
1251 real_type norm_sqr = 0;
1252 const size_type n_rows = m();
1253 for (const number *ptr = val.get(); ptr != val.get() + cols->rowstart[n_rows];
1254 ++ptr)
1255 norm_sqr += numbers::NumberTraits<number>::abs_square(*ptr);
1256
1257 return std::sqrt(norm_sqr);
1258 }
1259
1260
1261
1262 namespace internal
1263 {
1264 namespace SparseMatrixImplementation
1265 {
1266 /**
1267 * Perform a vmult using the SparseMatrix data structures, but only using
1268 * a subinterval for the row indices.
1269 *
1270 * In the sequential case, this function is called on all rows, in the
1271 * parallel case it may be called on a subrange, at the discretion of the
1272 * task scheduler.
1273 */
1274 template <typename number, typename InVector, typename OutVector>
1275 typename OutVector::value_type
1276 residual_sqr_on_subrange(const size_type begin_row,
1277 const size_type end_row,
1278 const number *values,
1279 const std::size_t *rowstart,
1280 const size_type *colnums,
1281 const InVector &u,
1282 const InVector &b,
1283 OutVector &dst)
1284 {
1285 typename OutVector::value_type norm_sqr = 0.;
1286
1287 for (size_type i = begin_row; i < end_row; ++i)
1288 {
1289 typename OutVector::value_type s = b(i);
1290 for (size_type j = rowstart[i]; j < rowstart[i + 1]; ++j)
1291 s -= typename OutVector::value_type(values[j]) * u(colnums[j]);
1292 dst(i) = s;
1293 norm_sqr +=
1294 s *
1295 numbers::NumberTraits<typename OutVector::value_type>::conjugate(s);
1296 }
1297 return norm_sqr;
1298 }
1299 } // namespace SparseMatrixImplementation
1300 } // namespace internal
1301
1302
1303 template <typename number>
1304 template <typename somenumber>
1305 somenumber
1306 SparseMatrix<number>::residual(Vector<somenumber> &dst,
1307 const Vector<somenumber> &u,
1308 const Vector<somenumber> &b) const
1309 {
1310 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1311 Assert(val != nullptr, ExcNotInitialized());
1312 Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size()));
1313 Assert(m() == b.size(), ExcDimensionMismatch(m(), b.size()));
1314 Assert(n() == u.size(), ExcDimensionMismatch(n(), u.size()));
1315
1316 Assert(&u != &dst, ExcSourceEqualsDestination());
1317
1318 return std::sqrt(parallel::accumulate_from_subranges<somenumber>(
1319 [this, &u, &b, &dst](const size_type begin_row, const size_type end_row) {
1320 return internal::SparseMatrixImplementation::residual_sqr_on_subrange(
1321 begin_row,
1322 end_row,
1323 val.get(),
1324 cols->rowstart.get(),
1325 cols->colnums.get(),
1326 u,
1327 b,
1328 dst);
1329 },
1330 0,
1331 m(),
1332 internal::SparseMatrixImplementation::minimum_parallel_grain_size));
1333 }
1334
1335
1336 namespace internal
1337 {
1338 namespace SparseMatrixImplementation
1339 {
1340 // assert that the matrix has no zeros on the diagonal. this is important
1341 // for preconditioners such as Jacobi or SSOR
1342 template <typename number>
1343 void
1344 AssertNoZerosOnDiagonal(const SparseMatrix<number> &matrix)
1345 {
1346 if constexpr (running_in_debug_mode())
1347 {
1348 for (typename SparseMatrix<number>::size_type row = 0;
1349 row < matrix.m();
1350 ++row)
1351 Assert(matrix.diag_element(row) != number(),
1352 ExcMessage(
1353 "There is a zero on the diagonal of this matrix "
1354 "in row " +
1355 std::to_string(row) +
1356 ". The preconditioner you selected cannot work if that "
1357 "is the case because one of its steps requires "
1358 "division by the diagonal elements of the matrix."
1359 "\n\n"
1360 "You should check whether you have correctly "
1361 "assembled the matrix that you use for this "
1362 "preconditioner. If it is correct that there are "
1363 "zeros on the diagonal, then you will have to chose "
1364 "a different preconditioner."));
1365 }
1366 else
1367 {
1368 (void)matrix;
1369 }
1370 }
1371 } // namespace SparseMatrixImplementation
1372 } // namespace internal
1373
1374
1375 template <typename number>
1376 template <typename somenumber>
1377 void
1378 SparseMatrix<number>::precondition_Jacobi(Vector<somenumber> &dst,
1379 const Vector<somenumber> &src,
1380 const number omega) const
1381 {
1382 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1383 Assert(val != nullptr, ExcNotInitialized());
1384 AssertDimension(m(), n());
1385 AssertDimension(dst.size(), n());
1386 AssertDimension(src.size(), n());
1387
1388 internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this);
1389
1390 const size_type n = src.size();
1391 somenumber *dst_ptr = dst.begin();
1392 const somenumber *src_ptr = src.begin();
1393 const std::size_t *rowstart_ptr = cols->rowstart.get();
1394
1395 // optimize the following loop for
1396 // the case that the relaxation
1397 // factor is one. In that case, we
1398 // can save one FP multiplication
1399 // per row
1400 //
1401 // note that for square matrices,
1402 // the diagonal entry is the first
1403 // in each row, i.e. at index
1404 // rowstart[i]. and we do have a
1405 // square matrix by above assertion
1406 if (omega != number(1.))
1407 for (size_type i = 0; i < n; ++i, ++dst_ptr, ++src_ptr, ++rowstart_ptr)
1408 *dst_ptr = somenumber(omega) * *src_ptr / somenumber(val[*rowstart_ptr]);
1409 else
1410 for (size_type i = 0; i < n; ++i, ++dst_ptr, ++src_ptr, ++rowstart_ptr)
1411 *dst_ptr = *src_ptr / somenumber(val[*rowstart_ptr]);
1412 }
1413
1414
1415
1416 template <typename number>
1417 template <typename somenumber>
1418 void
1419 SparseMatrix<number>::precondition_SSOR(
1420 Vector<somenumber> &dst,
1421 const Vector<somenumber> &src,
1422 const number omega,
1423 const std::vector<std::size_t> &pos_right_of_diagonal) const
1424 {
1425 // to understand how this function works
1426 // you may want to take a look at the CVS
1427 // archives to see the original version
1428 // which is much clearer...
1429 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1430 Assert(val != nullptr, ExcNotInitialized());
1431 AssertDimension(m(), n());
1432 AssertDimension(dst.size(), n());
1433 AssertDimension(src.size(), n());
1434
1435 internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this);
1436
1437 const size_type n = src.size();
1438 const std::size_t *rowstart_ptr = cols->rowstart.get();
1439 somenumber *dst_ptr = &dst(0);
1440
1441 // case when we have stored the position
1442 // just right of the diagonal (then we
1443 // don't have to search for it).
1444 if (pos_right_of_diagonal.size() != 0)
1445 {
1446 Assert(pos_right_of_diagonal.size() == dst.size(),
1447 ExcDimensionMismatch(pos_right_of_diagonal.size(), dst.size()));
1448
1449 // forward sweep
1450 for (size_type row = 0; row < n; ++row, ++dst_ptr, ++rowstart_ptr)
1451 {
1452 *dst_ptr = src(row);
1453 const std::size_t first_right_of_diagonal_index =
1454 pos_right_of_diagonal[row];
1455 Assert(first_right_of_diagonal_index <= *(rowstart_ptr + 1),
1456 ExcInternalError());
1457 number s = 0;
1458 for (size_type j = (*rowstart_ptr) + 1;
1459 j < first_right_of_diagonal_index;
1460 ++j)
1461 s += val[j] * number(dst(cols->colnums[j]));
1462
1463 // divide by diagonal element
1464 *dst_ptr -= s * omega;
1465 *dst_ptr /= val[*rowstart_ptr];
1466 }
1467
1468 rowstart_ptr = cols->rowstart.get();
1469 dst_ptr = &dst(0);
1470 for (; rowstart_ptr != &cols->rowstart[n]; ++rowstart_ptr, ++dst_ptr)
1471 *dst_ptr *= somenumber(omega * (number(2.) - omega)) *
1472 somenumber(val[*rowstart_ptr]);
1473
1474 // backward sweep
1475 rowstart_ptr = &cols->rowstart[n - 1];
1476 dst_ptr = &dst(n - 1);
1477 for (int row = n - 1; row >= 0; --row, --rowstart_ptr, --dst_ptr)
1478 {
1479 const size_type end_row = *(rowstart_ptr + 1);
1480 const size_type first_right_of_diagonal_index =
1481 pos_right_of_diagonal[row];
1482 number s = 0;
1483 // go through the column from the end towards the diagonal in order
1484 // to delay the use of the newly computed "dst" values on
1485 // out-of-order-execution hardware
1486 for (size_type j = end_row - 1; j >= first_right_of_diagonal_index;
1487 --j)
1488 s += val[j] * number(dst(cols->colnums[j]));
1489
1490 *dst_ptr -= s * omega;
1491 *dst_ptr /= val[*rowstart_ptr];
1492 };
1493 return;
1494 }
1495
1496 // case when we need to get the position
1497 // of the first element right of the
1498 // diagonal manually for each sweep.
1499 // forward sweep
1500 for (size_type row = 0; row < n; ++row, ++dst_ptr, ++rowstart_ptr)
1501 {
1502 *dst_ptr = src(row);
1503 // find the first element in this line
1504 // which is on the right of the diagonal.
1505 // we need to precondition with the
1506 // elements on the left only.
1507 // note: the first entry in each
1508 // line denotes the diagonal element,
1509 // which we need not check.
1510 const size_type first_right_of_diagonal_index =
1511 (Utilities::lower_bound(cols->colnums.get() + *rowstart_ptr + 1,
1512 cols->colnums.get() + *(rowstart_ptr + 1),
1513 row) -
1514 cols->colnums.get());
1515
1516 number s = 0;
1517 for (size_type j = (*rowstart_ptr) + 1; j < first_right_of_diagonal_index;
1518 ++j)
1519 s += val[j] * number(dst(cols->colnums[j]));
1520
1521 // divide by diagonal element
1522 *dst_ptr -= s * omega;
1523 Assert(val[*rowstart_ptr] != number(), ExcDivideByZero());
1524 *dst_ptr /= val[*rowstart_ptr];
1525 };
1526
1527 rowstart_ptr = cols->rowstart.get();
1528 dst_ptr = &dst(0);
1529 for (size_type row = 0; row < n; ++row, ++rowstart_ptr, ++dst_ptr)
1530 *dst_ptr *=
1531 somenumber((number(2.) - omega)) * somenumber(val[*rowstart_ptr]);
1532
1533 // backward sweep
1534 rowstart_ptr = &cols->rowstart[n - 1];
1535 dst_ptr = &dst(n - 1);
1536 for (int row = n - 1; row >= 0; --row, --rowstart_ptr, --dst_ptr)
1537 {
1538 const size_type end_row = *(rowstart_ptr + 1);
1539 const size_type first_right_of_diagonal_index =
1540 (Utilities::lower_bound(&cols->colnums[*rowstart_ptr + 1],
1541 &cols->colnums[end_row],
1542 static_cast<size_type>(row)) -
1543 cols->colnums.get());
1544 number s = 0;
1545 for (size_type j = first_right_of_diagonal_index; j < end_row; ++j)
1546 s += val[j] * number(dst(cols->colnums[j]));
1547 *dst_ptr -= s * omega;
1548 Assert(val[*rowstart_ptr] != number(), ExcDivideByZero());
1549 *dst_ptr /= val[*rowstart_ptr];
1550 };
1551 }
1552
1553
1554 template <typename number>
1555 template <typename somenumber>
1556 void
1557 SparseMatrix<number>::precondition_SOR(Vector<somenumber> &dst,
1558 const Vector<somenumber> &src,
1559 const number omega) const
1560 {
1561 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1562 Assert(val != nullptr, ExcNotInitialized());
1563
1564 dst = src;
1565 SOR(dst, omega);
1566 }
1567
1568
1569 template <typename number>
1570 template <typename somenumber>
1571 void
1572 SparseMatrix<number>::precondition_TSOR(Vector<somenumber> &dst,
1573 const Vector<somenumber> &src,
1574 const number omega) const
1575 {
1576 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1577 Assert(val != nullptr, ExcNotInitialized());
1578
1579 dst = src;
1580 TSOR(dst, omega);
1581 }
1582
1583
1584 template <typename number>
1585 template <typename somenumber>
1586 void
1587 SparseMatrix<number>::SOR(Vector<somenumber> &dst, const number omega) const
1588 {
1589 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1590 Assert(val != nullptr, ExcNotInitialized());
1591 AssertDimension(m(), n());
1592 AssertDimension(dst.size(), n());
1593
1594 internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this);
1595
1596 for (size_type row = 0; row < m(); ++row)
1597 {
1598 somenumber s = dst(row);
1599 for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j)
1600 {
1601 const size_type col = cols->colnums[j];
1602 if (col < row)
1603 s -= somenumber(val[j]) * dst(col);
1604 }
1605
1606 dst(row) = s * somenumber(omega) / somenumber(val[cols->rowstart[row]]);
1607 }
1608 }
1609
1610
1611 template <typename number>
1612 template <typename somenumber>
1613 void
1614 SparseMatrix<number>::TSOR(Vector<somenumber> &dst, const number omega) const
1615 {
1616 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1617 Assert(val != nullptr, ExcNotInitialized());
1618 AssertDimension(m(), n());
1619 AssertDimension(dst.size(), n());
1620
1621 internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this);
1622
1623 size_type row = m() - 1;
1624 while (true)
1625 {
1626 somenumber s = dst(row);
1627 for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j)
1628 if (cols->colnums[j] > row)
1629 s -= somenumber(val[j]) * dst(cols->colnums[j]);
1630
1631 dst(row) = s * somenumber(omega) / somenumber(val[cols->rowstart[row]]);
1632
1633 if (row == 0)
1634 break;
1635
1636 --row;
1637 }
1638 }
1639
1640
1641 template <typename number>
1642 template <typename somenumber>
1643 void
1644 SparseMatrix<number>::PSOR(Vector<somenumber> &dst,
1645 const std::vector<size_type> &permutation,
1646 const std::vector<size_type> &inverse_permutation,
1647 const number omega) const
1648 {
1649 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1650 Assert(val != nullptr, ExcNotInitialized());
1651 AssertDimension(m(), n());
1652
1653 Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size()));
1654 Assert(m() == permutation.size(),
1655 ExcDimensionMismatch(m(), permutation.size()));
1656 Assert(m() == inverse_permutation.size(),
1657 ExcDimensionMismatch(m(), inverse_permutation.size()));
1658
1659 internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this);
1660
1661 for (size_type urow = 0; urow < m(); ++urow)
1662 {
1663 const size_type row = permutation[urow];
1664 somenumber s = dst(row);
1665
1666 for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j)
1667 {
1668 const size_type col = cols->colnums[j];
1669 if (inverse_permutation[col] < urow)
1670 {
1671 s -= somenumber(val[j]) * dst(col);
1672 }
1673 }
1674
1675 dst(row) = s * somenumber(omega) / somenumber(val[cols->rowstart[row]]);
1676 }
1677 }
1678
1679
1680 template <typename number>
1681 template <typename somenumber>
1682 void
1683 SparseMatrix<number>::TPSOR(Vector<somenumber> &dst,
1684 const std::vector<size_type> &permutation,
1685 const std::vector<size_type> &inverse_permutation,
1686 const number omega) const
1687 {
1688 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1689 Assert(val != nullptr, ExcNotInitialized());
1690 AssertDimension(m(), n());
1691
1692 Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size()));
1693 Assert(m() == permutation.size(),
1694 ExcDimensionMismatch(m(), permutation.size()));
1695 Assert(m() == inverse_permutation.size(),
1696 ExcDimensionMismatch(m(), inverse_permutation.size()));
1697
1698 internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this);
1699
1700 for (size_type urow = m(); urow != 0;)
1701 {
1702 --urow;
1703 const size_type row = permutation[urow];
1704 somenumber s = dst(row);
1705 for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j)
1706 {
1707 const size_type col = cols->colnums[j];
1708 if (inverse_permutation[col] > urow)
1709 s -= somenumber(val[j]) * dst(col);
1710 }
1711
1712 dst(row) = s * somenumber(omega) / somenumber(val[cols->rowstart[row]]);
1713 }
1714 }
1715
1716
1717
1718 template <typename number>
1719 template <typename somenumber>
1720 void
1721 SparseMatrix<number>::Jacobi_step(Vector<somenumber> &v,
1722 const Vector<somenumber> &b,
1723 const number omega) const
1724 {
1725 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1726 Assert(val != nullptr, ExcNotInitialized());
1727 AssertDimension(m(), n());
1728
1729 Assert(m() == v.size(), ExcDimensionMismatch(m(), v.size()));
1730 Assert(m() == b.size(), ExcDimensionMismatch(m(), b.size()));
1731
1732 GrowingVectorMemory<Vector<somenumber>> mem;
1733 typename VectorMemory<Vector<somenumber>>::Pointer w(mem);
1734 w->reinit(v);
1735
1736 if (!v.all_zero())
1737 {
1738 vmult(*w, v);
1739 *w -= b;
1740 }
1741 else
1742 w->equ(-1., b);
1743 precondition_Jacobi(*w, *w, omega);
1744 v -= *w;
1745 }
1746
1747
1748
1749 template <typename number>
1750 template <typename somenumber>
1751 void
1752 SparseMatrix<number>::SOR_step(Vector<somenumber> &v,
1753 const Vector<somenumber> &b,
1754 const number omega) const
1755 {
1756 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1757 Assert(val != nullptr, ExcNotInitialized());
1758 AssertDimension(m(), n());
1759 Assert(m() == v.size(), ExcDimensionMismatch(m(), v.size()));
1760 Assert(m() == b.size(), ExcDimensionMismatch(m(), b.size()));
1761
1762 internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this);
1763
1764 for (size_type row = 0; row < m(); ++row)
1765 {
1766 somenumber s = b(row);
1767 for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j)
1768 {
1769 s -= somenumber(val[j]) * v(cols->colnums[j]);
1770 }
1771 v(row) += s * somenumber(omega) / somenumber(val[cols->rowstart[row]]);
1772 }
1773 }
1774
1775
1776
1777 template <typename number>
1778 template <typename somenumber>
1779 void
1780 SparseMatrix<number>::TSOR_step(Vector<somenumber> &v,
1781 const Vector<somenumber> &b,
1782 const number omega) const
1783 {
1784 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1785 Assert(val != nullptr, ExcNotInitialized());
1786 AssertDimension(m(), n());
1787 Assert(m() == v.size(), ExcDimensionMismatch(m(), v.size()));
1788 Assert(m() == b.size(), ExcDimensionMismatch(m(), b.size()));
1789
1790 internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this);
1791
1792 for (int row = m() - 1; row >= 0; --row)
1793 {
1794 somenumber s = b(row);
1795 for (size_type j = cols->rowstart[row]; j < cols->rowstart[row + 1]; ++j)
1796 {
1797 s -= somenumber(val[j]) * v(cols->colnums[j]);
1798 }
1799 v(row) += s * somenumber(omega) / somenumber(val[cols->rowstart[row]]);
1800 }
1801 }
1802
1803
1804
1805 template <typename number>
1806 template <typename somenumber>
1807 void
1808 SparseMatrix<number>::SSOR_step(Vector<somenumber> &v,
1809 const Vector<somenumber> &b,
1810 const number omega) const
1811 {
1812 SOR_step(v, b, omega);
1813 TSOR_step(v, b, omega);
1814 }
1815
1816
1817
1818 template <typename number>
1819 template <typename somenumber>
1820 void
1821 SparseMatrix<number>::SSOR(Vector<somenumber> &dst, const number omega) const
1822 {
1823 // TODO: Is this called anywhere? If so, multiplication with omega(2-omega)D
1824 // is missing
1825 DEAL_II_NOT_IMPLEMENTED();
1826
1827 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1828 Assert(val != nullptr, ExcNotInitialized());
1829 AssertDimension(m(), n());
1830 Assert(m() == dst.size(), ExcDimensionMismatch(m(), dst.size()));
1831
1832 internal::SparseMatrixImplementation::AssertNoZerosOnDiagonal(*this);
1833
1834 const size_type n = dst.size();
1835 size_type j;
1836 somenumber s;
1837
1838 for (size_type i = 0; i < n; ++i)
1839 {
1840 s = 0.;
1841 for (j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j)
1842 {
1843 const size_type p = cols->colnums[j];
1844 if (p != SparsityPattern::invalid_entry)
1845 {
1846 if (i > j)
1847 s += somenumber(val[j]) * dst(p);
1848 }
1849 }
1850 dst(i) -= s * somenumber(omega);
1851 dst(i) /= somenumber(val[cols->rowstart[i]]);
1852 }
1853
1854 for (int i = n - 1; i >= 0;
1855 i--) // this time, i is signed, but always positive!
1856 {
1857 s = 0.;
1858 for (j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j)
1859 {
1860 const size_type p = cols->colnums[j];
1861 if (p != SparsityPattern::invalid_entry)
1862 {
1863 if (static_cast<size_type>(i) < j)
1864 s += somenumber(val[j]) * dst(p);
1865 }
1866 }
1867 dst(i) -= s * somenumber(omega) / somenumber(val[cols->rowstart[i]]);
1868 }
1869 }
1870
1871
1872
1873 template <typename number>
1874 void
1875 SparseMatrix<number>::print_formatted(std::ostream &out,
1876 const unsigned int precision,
1877 const bool scientific,
1878 const unsigned int width_,
1879 const char *zero_string,
1880 const double denominator,
1881 const char *separator) const
1882 {
1883 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1884 Assert(val != nullptr, ExcNotInitialized());
1885
1886 unsigned int width = width_;
1887
1888 std::ios::fmtflags old_flags = out.flags();
1889 unsigned int old_precision = out.precision(precision);
1890
1891 if (scientific)
1892 {
1893 out.setf(std::ios::scientific, std::ios::floatfield);
1894 if (width == 0u)
1895 width = precision + 7;
1896 }
1897 else
1898 {
1899 out.setf(std::ios::fixed, std::ios::floatfield);
1900 if (width == 0u)
1901 width = precision + 2;
1902 }
1903
1904 for (size_type i = 0; i < m(); ++i)
1905 {
1906 for (size_type j = 0; j < n(); ++j)
1907 if ((*cols)(i, j) != SparsityPattern::invalid_entry)
1908 out << std::setw(width)
1909 << val[cols->operator()(i, j)] * number(denominator) << separator;
1910 else
1911 out << std::setw(width) << zero_string << separator;
1912 out << std::endl;
1913 };
1914 AssertThrow(out.fail() == false, ExcIO());
1915
1916 // reset output format
1917 out.precision(old_precision);
1918 out.flags(old_flags);
1919 }
1920
1921
1922
1923 template <typename number>
1924 void
1925 SparseMatrix<number>::print_pattern(std::ostream &out,
1926 const double threshold) const
1927 {
1928 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1929 Assert(val != nullptr, ExcNotInitialized());
1930
1931 for (size_type i = 0; i < m(); ++i)
1932 {
1933 for (size_type j = 0; j < n(); ++j)
1934 if ((*cols)(i, j) == SparsityPattern::invalid_entry)
1935 out << '.';
1936 else if (std::abs(val[cols->operator()(i, j)]) > threshold)
1937 out << '*';
1938 else
1939 out << ':';
1940 out << std::endl;
1941 };
1942 AssertThrow(out.fail() == false, ExcIO());
1943 }
1944
1945
1946
1947 template <typename number>
1948 void
1949 SparseMatrix<number>::print_as_numpy_arrays(std::ostream &out,
1950 const unsigned int precision) const
1951 {
1952 AssertThrow(out.fail() == false, ExcIO());
1953 boost::io::ios_flags_saver restore_flags(out);
1954
1955 out.precision(precision);
1956
1957 Assert(cols != nullptr, ExcNeedsSparsityPattern());
1958 Assert(val != nullptr, ExcNotInitialized());
1959
1960 std::vector<number> rows;
1961 std::vector<number> columns;
1962 std::vector<number> values;
1963 rows.reserve(n_nonzero_elements());
1964 columns.reserve(n_nonzero_elements());
1965 values.reserve(n_nonzero_elements());
1966
1967 for (size_type i = 0; i < cols->rows; ++i)
1968 {
1969 for (size_type j = cols->rowstart[i]; j < cols->rowstart[i + 1]; ++j)
1970 {
1971 rows.push_back(i);
1972 columns.push_back(cols->colnums[j]);
1973 values.push_back(val[j]);
1974 }
1975 }
1976
1977 for (auto d : values)
1978 out << d << ' ';
1979 out << '\n';
1980
1981 for (auto r : rows)
1982 out << r << ' ';
1983 out << '\n';
1984
1985 for (auto c : columns)
1986 out << c << ' ';
1987 out << '\n';
1988 out << std::flush;
1989
1990 AssertThrow(out.fail() == false, ExcIO());
1991 }
1992
1993
1994
1995 template <typename number>
1996 void
1997 SparseMatrix<number>::block_write(std::ostream &out) const
1998 {
1999 AssertThrow(out.fail() == false, ExcIO());
2000
2001 // first the simple objects,
2002 // bracketed in [...]
2003 out << '[' << max_len << "][";
2004 // then write out real data
2005 out.write(reinterpret_cast<const char *>(val.get()),
2006 reinterpret_cast<const char *>(val.get() + max_len) -
2007 reinterpret_cast<const char *>(val.get()));
2008 out << ']';
2009
2010 AssertThrow(out.fail() == false, ExcIO());
2011 }
2012
2013
2014
2015 template <typename number>
2016 void
2017 SparseMatrix<number>::block_read(std::istream &in)
2018 {
2019 AssertThrow(in.fail() == false, ExcIO());
2020
2021 char c;
2022
2023 // first read in simple data
2024 in >> c;
2025 AssertThrow(c == '[', ExcIO());
2026 in >> max_len;
2027
2028 in >> c;
2029 AssertThrow(c == ']', ExcIO());
2030 in >> c;
2031 AssertThrow(c == '[', ExcIO());
2032
2033 // reallocate space
2034 val = std::make_unique<number[]>(max_len);
2035
2036 // then read data
2037 in.read(reinterpret_cast<char *>(val.get()),
2038 reinterpret_cast<char *>(val.get() + max_len) -
2039 reinterpret_cast<char *>(val.get()));
2040 in >> c;
2041 AssertThrow(c == ']', ExcIO());
2042 }
2043
2044
2045 template <typename number>
2046 void
2047 SparseMatrix<number>::compress(VectorOperation::values)
2048 {}
2049
2050
2051 template <typename number>
2052 std::size_t
2053 SparseMatrix<number>::memory_consumption() const
2054 {
2055 return max_len * static_cast<std::size_t>(sizeof(number)) + sizeof(*this);
2056 }
2057
2058
2059 DEAL_II_NAMESPACE_CLOSE
2060
2061 #endif