Debian Codegraph @

include/deal.II/lac/trilinos_tpetra_sparsity_pattern.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2024 - 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_trilinos_tpetra_sparsity_pattern_h
16 #define dealii_trilinos_tpetra_sparsity_pattern_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/types.h>
21
22 #include <deal.II/lac/trilinos_tpetra_types.h>
23
24 #ifdef DEAL_II_TRILINOS_WITH_TPETRA
25
26 # include <deal.II/base/enable_observer_pointer.h>
27 # include <deal.II/base/index_set.h>
28 # include <deal.II/base/mpi_stub.h>
29
30 # include <deal.II/lac/exceptions.h>
31 # include <deal.II/lac/sparsity_pattern_base.h>
32
33 # include <Tpetra_CrsGraph.hpp>
34
35 # include <cmath>
36 # include <memory>
37 # include <vector>
38
39
40 DEAL_II_NAMESPACE_OPEN
41
42 // forward declarations
43 # ifndef DOXYGEN
44 class DynamicSparsityPattern;
45
46 namespace LinearAlgebra
47 {
48 namespace TpetraWrappers
49 {
50 template <typename MemorySpace>
51 class SparsityPattern;
52
53 template <typename Number, typename MemorySpace>
54 class SparseMatrix;
55
56 namespace SparsityPatternIterators
57 {
58 template <typename MemorySpace>
59 class Iterator;
60 }
61 } // namespace TpetraWrappers
62 } // namespace LinearAlgebra
63 # endif
64
65 namespace LinearAlgebra
66 {
67 namespace TpetraWrappers
68 {
69 namespace SparsityPatternIterators
70 {
71 /**
72 * Accessor class for iterators into sparsity patterns. This class is also
73 * the base class for both const and non-const accessor classes into
74 * sparse matrices.
75 *
76 * Note that this class only allows read access to elements, providing
77 * their row and column number. It does not allow modifying the sparsity
78 * pattern itself.
79 *
80 * @ingroup TrilinosWrappers
81 */
82 template <typename MemorySpace = dealii::MemorySpace::Host>
83 class Accessor
84 {
85 public:
86 /**
87 * Declare type for container size.
88 */
89 using size_type = dealii::types::global_dof_index;
90
91 /**
92 * Constructor.
93 */
94 Accessor(const SparsityPattern<MemorySpace> *sparsity_pattern,
95 const size_type row,
96 const size_type index);
97
98 /**
99 * Row number of the element represented by this object.
100 */
101 size_type
102 row() const;
103
104 /**
105 * Index in row of the element represented by this object.
106 */
107 size_type
108 index() const;
109
110 /**
111 * Column number of the element represented by this object.
112 */
113 size_type
114 column() const;
115
116 /**
117 * Exception
118 */
119 DeclException0(ExcBeyondEndOfSparsityPattern);
120
121 /**
122 * Exception
123 */
124 DeclException3(ExcAccessToNonlocalRow,
125 size_type,
126 size_type,
127 size_type,
128 << "You tried to access row " << arg1
129 << " of a distributed sparsity pattern, "
130 << " but only rows " << arg2 << " through " << arg3
131 << " are stored locally and can be accessed.");
132
133 private:
134 /**
135 * The matrix accessed.
136 */
137 SparsityPattern<MemorySpace> *sparsity_pattern;
138
139 /**
140 * Current row number.
141 */
142 size_type a_row;
143
144 /**
145 * Current index in row.
146 */
147 size_type a_index;
148
149 /**
150 * Cache where we store the column indices of the present row. This is
151 * necessary, since Trilinos makes access to the elements of its
152 * matrices rather hard, and it is much more efficient to copy all
153 * column entries of a row once when we enter it than repeatedly asking
154 * Trilinos for individual ones. This also makes some sense since it is
155 * likely that we will access them sequentially anyway.
156 *
157 * In order to make copying of iterators/accessor of acceptable
158 * performance, we keep a shared pointer to these entries so that more
159 * than one accessor can access this data if necessary.
160 */
161 std::shared_ptr<std::vector<dealii::types::signed_global_dof_index>>
162 colnum_cache;
163
164 /**
165 * Discard the old row caches (they may still be used by other
166 * accessors) and generate new ones for the row pointed to presently by
167 * this accessor.
168 */
169 void
170 visit_present_row();
171
172 // Make enclosing class a friend.
173 friend class Iterator<MemorySpace>;
174 };
175
176 /**
177 * Iterator class for sparsity patterns of type
178 * TrilinosWrappers::SparsityPattern. Access to individual elements of the
179 * sparsity pattern is handled by the Accessor class in this namespace.
180 */
181 template <typename MemorySpace = dealii::MemorySpace::Host>
182 class Iterator
183 {
184 public:
185 /**
186 * Declare type for container size.
187 */
188 using size_type = types::global_dof_index;
189
190 /**
191 * Constructor. Create an iterator into the matrix @p matrix for the
192 * given row and the index within it.
193 */
194 Iterator(const SparsityPattern<MemorySpace> *sparsity_pattern,
195 const size_type row,
196 const size_type index);
197
198 /**
199 * Copy constructor.
200 */
201 Iterator(const Iterator<MemorySpace> &i);
202
203 /**
204 * Prefix increment.
205 */
206 Iterator<MemorySpace> &
207 operator++();
208
209 /**
210 * Postfix increment.
211 */
212 Iterator
213 operator++(int);
214
215 /**
216 * Dereferencing operator.
217 */
218 const Accessor<MemorySpace> &
219 operator*() const;
220
221 /**
222 * Dereferencing operator.
223 */
224 const Accessor<MemorySpace> *
225 operator->() const;
226
227 /**
228 * Comparison. True, if both iterators point to the same matrix
229 * position.
230 */
231 bool
232 operator==(const Iterator<MemorySpace> &) const;
233
234 /**
235 * Inverse of <tt>==</tt>.
236 */
237 bool
238 operator!=(const Iterator<MemorySpace> &) const;
239
240 /**
241 * Comparison operator. Result is true if either the first row number is
242 * smaller or if the row numbers are equal and the first index is
243 * smaller.
244 */
245 bool
246 operator<(const Iterator<MemorySpace> &) const;
247
248 /**
249 * Exception
250 */
251 DeclException2(ExcInvalidIndexWithinRow,
252 size_type,
253 size_type,
254 << "Attempt to access element " << arg2 << " of row "
255 << arg1 << " which doesn't have that many elements.");
256
257 private:
258 /**
259 * Store an object of the accessor class.
260 */
261 Accessor<MemorySpace> accessor;
262
263 friend class TpetraWrappers::SparsityPattern<MemorySpace>;
264 };
265
266 } // namespace SparsityPatternIterators
267
268
269 /**
270 * This class implements a wrapper class to use the Trilinos distributed
271 * sparsity pattern class Tpetra::CrsGraph. This class is designed to be
272 * used for construction of %parallel Trilinos matrices. The functionality
273 * of this class is modeled after the existing sparsity pattern classes,
274 * with the difference that this class can work fully in %parallel according
275 * to a partitioning of the sparsity pattern rows.
276 *
277 * This class has many similarities to the DynamicSparsityPattern, since it
278 * can dynamically add elements to the pattern without any memory being
279 * previously reserved for it. However, it also has a method
280 * SparsityPattern<MemorySpace>::compress(), that finalizes the pattern and
281 * enables its use with Trilinos sparse matrices.
282 *
283 * @ingroup TrilinosWrappers
284 * @ingroup Sparsity
285 */
286 template <typename MemorySpace = dealii::MemorySpace::Host>
287 class SparsityPattern : public SparsityPatternBase
288 {
289 public:
290 /**
291 * Declare type for container size.
292 */
293 using size_type = dealii::types::global_dof_index;
294 /**
295 * Declare an alias for the iterator class.
296 */
297 using const_iterator = SparsityPatternIterators::Iterator<MemorySpace>;
298
299 /**
300 * @name Basic constructors and initialization
301 */
302 /** @{ */
303 /**
304 * Default constructor. Generates an empty (zero-size) sparsity pattern.
305 */
306 SparsityPattern();
307
308 /**
309 * Generate a sparsity pattern that is completely stored locally, having
310 * $m$ rows and $n$ columns. The resulting matrix will be completely
311 * stored locally, too.
312 *
313 * It is possible to specify the number of columns entries per row using
314 * the optional @p n_entries_per_row argument. However, this value does
315 * not need to be accurate or even given at all, since one does usually
316 * not have this kind of information before building the sparsity pattern
317 * (the usual case when the function DoFTools::make_sparsity_pattern() is
318 * called). The entries are allocated dynamically in a similar manner as
319 * for the deal.II DynamicSparsityPattern classes. However, a good
320 * estimate will reduce the setup time of the sparsity pattern.
321 */
322 SparsityPattern(const size_type m,
323 const size_type n,
324 const size_type n_entries_per_row = 0);
325
326 /**
327 * Generate a sparsity pattern that is completely stored locally, having
328 * $m$ rows and $n$ columns. The resulting matrix will be completely
329 * stored locally, too.
330 *
331 * The vector <tt>n_entries_per_row</tt> specifies the number of entries
332 * in each row (an information usually not available, though).
333 */
334 SparsityPattern(const size_type m,
335 const size_type n,
336 const std::vector<size_type> &n_entries_per_row);
337
338 /**
339 * Move constructor. Create a new sparse matrix by stealing the internal
340 * data.
341 */
342 SparsityPattern(SparsityPattern<MemorySpace> &&other) noexcept;
343
344 /**
345 * Copy constructor. Sets the calling sparsity pattern to be the same as
346 * the input sparsity pattern.
347 */
348 SparsityPattern(
349 const SparsityPattern<MemorySpace> &input_sparsity_pattern);
350
351 /**
352 * Destructor. Made virtual so that one can use pointers to this class.
353 */
354 virtual ~SparsityPattern() override = default;
355
356 /**
357 * Initialize a sparsity pattern that is completely stored locally, having
358 * $m$ rows and $n$ columns. The resulting matrix will be completely
359 * stored locally.
360 *
361 * The number of columns entries per row is specified as the maximum
362 * number of entries argument. This does not need to be an accurate
363 * number since the entries are allocated dynamically in a similar manner
364 * as for the deal.II DynamicSparsityPattern classes, but a good estimate
365 * will reduce the setup time of the sparsity pattern.
366 */
367 void
368 reinit(const size_type m,
369 const size_type n,
370 const size_type n_entries_per_row = 0);
371
372 /**
373 * Initialize a sparsity pattern that is completely stored locally, having
374 * $m$ rows and $n$ columns. The resulting matrix will be completely
375 * stored locally.
376 *
377 * The vector <tt>n_entries_per_row</tt> specifies the number of entries
378 * in each row.
379 */
380 void
381 reinit(const size_type m,
382 const size_type n,
383 const std::vector<size_type> &n_entries_per_row);
384
385 /**
386 * Copy function. Sets the calling sparsity pattern to be the same as the
387 * input sparsity pattern.
388 */
389 void
390 copy_from(const SparsityPattern<MemorySpace> &input_sparsity_pattern);
391
392 /**
393 * Copy function from one of the deal.II sparsity patterns. If used in
394 * parallel, this function uses an ad-hoc partitioning of the rows and
395 * columns.
396 */
397 template <typename SparsityPatternType>
398 void
399 copy_from(const SparsityPatternType &nontrilinos_sparsity_pattern);
400
401 /**
402 * Copy operator. This operation is only allowed for empty objects, to
403 * avoid potentially very costly operations automatically synthesized by
404 * the compiler. Use copy_from() instead if you know that you really want
405 * to copy a sparsity pattern with non-trivial content.
406 */
407 SparsityPattern<MemorySpace> &
408 operator=(const SparsityPattern<MemorySpace> &input_sparsity_pattern);
409
410 /**
411 * Release all memory and return to a state just like after having called
412 * the default constructor.
413 *
414 * This is a collective operation that needs to be called on all
415 * processors in order to avoid a dead lock.
416 */
417 void
418 clear();
419
420 /**
421 * In analogy to our own SparsityPattern class, this function compresses
422 * the sparsity pattern and allows the resulting pattern to be used for
423 * actually generating a (Trilinos-based) matrix. This function also
424 * exchanges non-local data that might have accumulated during the
425 * addition of new elements. This function must therefore be called once
426 * the structure is fixed. This is a collective operation, i.e., it needs
427 * to be run on all processors when used in parallel.
428 */
429 void
430 compress();
431 /** @} */
432
433 /**
434 * @name Constructors and initialization using an IndexSet description
435 */
436 /** @{ */
437
438 /**
439 * Constructor for a square sparsity pattern using an IndexSet and an MPI
440 * communicator for the description of the %parallel partitioning.
441 * Moreover, the number of nonzero entries in the rows of the sparsity
442 * pattern can be specified. Note that this number does not need to be
443 * exact, and it is even allowed that the actual sparsity structure has
444 * more nonzero entries than specified in the constructor. However it is
445 * still advantageous to provide good estimates here since a good value
446 * will avoid repeated allocation of memory, which considerably increases
447 * the performance when creating the sparsity pattern.
448 */
449 SparsityPattern(const IndexSet &parallel_partitioning,
450 const MPI_Comm communicator = MPI_COMM_WORLD,
451 const size_type n_entries_per_row = 0);
452
453 /**
454 * Same as before, but now use the exact number of nonzero entries in
455 * each m row. Since we know the number of elements in the sparsity
456 * pattern exactly in this case, we can already allocate the right amount
457 * of memory, which makes the creation process by the respective
458 * SparsityPattern<MemorySpace>::reinit call considerably faster. However,
459 * this is a rather unusual situation, since knowing the number of entries
460 * in each row is usually connected to knowing the indices of nonzero
461 * entries, which the sparsity pattern is designed to describe.
462 */
463 SparsityPattern(const IndexSet &parallel_partitioning,
464 const MPI_Comm communicator,
465 const std::vector<size_type> &n_entries_per_row);
466
467 /**
468 * This constructor is similar to the one above, but it now takes two
469 * different index sets to describe the %parallel partitioning of rows and
470 * columns. This interface is meant to be used for generating rectangular
471 * sparsity pattern. Note that there is no real parallelism along the
472 * columns &ndash; the processor that owns a certain row always owns all
473 * the column elements, no matter how far they might be spread out. The
474 * second Tpetra::Map is only used to specify the number of columns and
475 * for internal arrangements when doing matrix-vector products with
476 * vectors based on that column map.
477 *
478 * The number of columns entries per row is specified as the maximum
479 * number of entries argument.
480 */
481 SparsityPattern(const IndexSet &row_parallel_partitioning,
482 const IndexSet &col_parallel_partitioning,
483 const MPI_Comm communicator = MPI_COMM_WORLD,
484 const size_type n_entries_per_row = 0);
485
486 /**
487 * This constructor is similar to the one above, but it now takes two
488 * different index sets for rows and columns. This interface is meant to
489 * be used for generating rectangular matrices, where one map specifies
490 * the %parallel distribution of rows and the second one specifies the
491 * distribution of degrees of freedom associated with matrix columns. This
492 * second map is however not used for the distribution of the columns
493 * themselves &ndash; rather, all column elements of a row are stored on
494 * the same processor. The vector <tt>n_entries_per_row</tt> specifies the
495 * number of entries in each row of the newly generated matrix.
496 */
497 SparsityPattern(const IndexSet &row_parallel_partitioning,
498 const IndexSet &col_parallel_partitioning,
499 const MPI_Comm communicator,
500 const std::vector<size_type> &n_entries_per_row);
501
502 /**
503 * This constructor constructs general sparsity patterns, possible non-
504 * square ones. Constructing a sparsity pattern this way allows the user
505 * to explicitly specify the rows into which we are going to add elements.
506 * This set is required to be a superset of the first index set @p
507 * row_parallel_partitioning that includes also rows that are owned by
508 * another processor (ghost rows). Note that elements can only be added to
509 * rows specified by @p writable_rows.
510 *
511 * This method is beneficial when the rows to which a processor is going
512 * to write can be determined before actually inserting elements into the
513 * matrix. For the typical parallel::distributed::Triangulation class used
514 * in deal.II, we know that a processor only will add row elements for
515 * what we call the locally relevant dofs (see
516 * DoFTools::extract_locally_relevant_dofs). The other constructors
517 * methods use general Trilinos facilities that allow to add elements to
518 * arbitrary rows (as done by all the other reinit functions). However,
519 * this flexibility come at a cost, the most prominent being that adding
520 * elements into the same matrix from multiple threads in shared memory is
521 * not safe whenever MPI is used. For these settings, the current method
522 * is the one to choose: It will store the off-processor data as an
523 * additional sparsity pattern (that is then passed to the Trilinos matrix
524 * via the reinit method) which can be organized in such a way that
525 * thread-safety can be ensured (as long as the user makes sure to never
526 * write into the same matrix row simultaneously, of course).
527 */
528 SparsityPattern(const IndexSet &row_parallel_partitioning,
529 const IndexSet &col_parallel_partitioning,
530 const IndexSet &writable_rows,
531 const MPI_Comm communicator = MPI_COMM_WORLD,
532 const size_type n_entries_per_row = 0);
533
534 /**
535 * Reinitialization function for generating a square sparsity pattern
536 * using an IndexSet and an MPI communicator for the description of the
537 * %parallel partitioning and the number of nonzero entries in the rows of
538 * the sparsity pattern. Note that this number does not need to be exact,
539 * and it is even allowed that the actual sparsity structure has more
540 * nonzero entries than specified in the constructor. However it is still
541 * advantageous to provide good estimates here since this will
542 * considerably increase the performance when creating the sparsity
543 * pattern.
544 *
545 * This function does not create any entries by itself, but provides the
546 * correct data structures that can be used by the respective add()
547 * function.
548 */
549 void
550 reinit(const IndexSet &parallel_partitioning,
551 const MPI_Comm communicator = MPI_COMM_WORLD,
552 const size_type n_entries_per_row = 0);
553
554 /**
555 * Same as before, but now use the exact number of nonzero entries in
556 * each row. Since we know the number of elements in the sparsity pattern
557 * exactly in this case, we can already allocate the right amount of
558 * memory, which makes process of adding entries to the sparsity pattern
559 * considerably faster. However, this is a rather unusual situation, since
560 * knowing the number of entries in each row is usually connected to
561 * knowing the indices of nonzero entries, which the sparsity pattern is
562 * designed to describe.
563 */
564 void
565 reinit(const IndexSet &parallel_partitioning,
566 const MPI_Comm communicator,
567 const std::vector<size_type> &n_entries_per_row);
568
569 /**
570 * This reinit function is similar to the one above, but it now takes two
571 * different index sets for rows and columns. This interface is meant to
572 * be used for generating rectangular sparsity pattern, where one index
573 * set describes the %parallel partitioning of the dofs associated with
574 * the sparsity pattern rows and the other one of the sparsity pattern
575 * columns. Note that there is no real parallelism along the columns
576 * &ndash; the processor that owns a certain row always owns all the
577 * column elements, no matter how far they might be spread out. The second
578 * IndexSet is only used to specify the number of columns and for internal
579 * arrangements when doing matrix-vector products with vectors based on an
580 * Tpetra::Map based on that IndexSet.
581 *
582 * The number of columns entries per row is specified by the argument
583 * <tt>n_entries_per_row</tt>.
584 */
585 void
586 reinit(const IndexSet &row_parallel_partitioning,
587 const IndexSet &col_parallel_partitioning,
588 const MPI_Comm communicator = MPI_COMM_WORLD,
589 const size_type n_entries_per_row = 0);
590
591 /**
592 * This reinit function is used to specify general matrices, possibly non-
593 * square ones. In addition to the arguments of the other reinit method
594 * above, it allows the user to explicitly specify the rows into which we
595 * are going to add elements. This set is a superset of the first index
596 * set @p row_parallel_partitioning that includes also rows that are owned
597 * by another processor (ghost rows).
598 *
599 * This method is beneficial when the rows to which a processor is going
600 * to write can be determined before actually inserting elements into the
601 * matrix. For the typical parallel::distributed::Triangulation class used
602 * in deal.II, we know that a processor only will add row elements for
603 * what we call the locally relevant dofs (see
604 * DoFTools::extract_locally_relevant_dofs). Trilinos matrices allow to
605 * add elements to arbitrary rows (as done by all the other reinit
606 * functions) and this is what all the other reinit methods do, too.
607 * However, this flexibility come at a cost, the most prominent being that
608 * adding elements into the same matrix from multiple threads in shared
609 * memory is not safe whenever MPI is used. For these settings, the
610 * current method is the one to choose: It will store the off-processor
611 * data as an additional sparsity pattern (that is then passed to the
612 * Trilinos matrix via the reinit method) which can be organized in such a
613 * way that thread-safety can be ensured (as long as the user makes sure
614 * to never write into the same matrix row simultaneously, of course).
615 */
616 void
617 reinit(const IndexSet &row_parallel_partitioning,
618 const IndexSet &col_parallel_partitioning,
619 const IndexSet &writeable_rows,
620 const MPI_Comm communicator = MPI_COMM_WORLD,
621 const size_type n_entries_per_row = 0);
622
623 /**
624 * Same as before, but now using a vector <tt>n_entries_per_row</tt> for
625 * specifying the number of entries in each row of the sparsity pattern.
626 */
627 void
628 reinit(const IndexSet &row_parallel_partitioning,
629 const IndexSet &col_parallel_partitioning,
630 const MPI_Comm communicator,
631 const std::vector<size_type> &n_entries_per_row);
632
633 /**
634 * Reinit function. Takes one of the deal.II sparsity patterns and the
635 * %parallel partitioning of the rows and columns specified by two index
636 * sets and a %parallel communicator for initializing the current Trilinos
637 * sparsity pattern. The optional argument @p exchange_data can be used
638 * for reinitialization with a sparsity pattern that is not fully
639 * constructed. This feature is only implemented for input sparsity
640 * patterns of type DynamicSparsityPattern.
641 */
642 template <typename SparsityPatternType>
643 void
644 reinit(const IndexSet &row_parallel_partitioning,
645 const IndexSet &col_parallel_partitioning,
646 const SparsityPatternType &nontrilinos_sparsity_pattern,
647 const MPI_Comm communicator = MPI_COMM_WORLD,
648 const bool exchange_data = false);
649
650 /**
651 * Reinit function. Takes one of the deal.II sparsity patterns and a
652 * %parallel partitioning of the rows and columns for initializing the
653 * current Trilinos sparsity pattern. The optional argument @p
654 * exchange_data can be used for reinitialization with a sparsity pattern
655 * that is not fully constructed. This feature is only implemented for
656 * input sparsity patterns of type DynamicSparsityPattern.
657 */
658 template <typename SparsityPatternType>
659 void
660 reinit(const IndexSet &parallel_partitioning,
661 const SparsityPatternType &nontrilinos_sparsity_pattern,
662 const MPI_Comm communicator = MPI_COMM_WORLD,
663 const bool exchange_data = false);
664 /** @} */
665 /**
666 * @name Information on the sparsity pattern
667 */
668 /** @{ */
669
670 /**
671 * Return the state of the sparsity pattern, i.e., whether compress()
672 * needs to be called after an operation requiring data exchange.
673 */
674 bool
675 is_compressed() const;
676
677 /**
678 * Return the maximum number of entries per row on the current processor.
679 */
680 unsigned int
681 max_entries_per_row() const;
682
683 /**
684 * Return the local dimension of the sparsity pattern, i.e. the number of
685 * rows stored on the present MPI process. In the sequential case, this
686 * number is the same as n_rows(), but for parallel matrices it may be
687 * smaller.
688 *
689 * To figure out which elements exactly are stored locally, use
690 * local_range().
691 */
692 unsigned int
693 local_size() const;
694
695 /**
696 * Return a pair of indices indicating which rows of this sparsity pattern
697 * are stored locally. The first number is the index of the first row
698 * stored, the second the index of the one past the last one that is
699 * stored locally. If this is a sequential matrix, then the result will be
700 * the pair (0,n_rows()), otherwise it will be a pair (i,i+n), where
701 * <tt>n=local_size()</tt>.
702 */
703 std::pair<size_type, size_type>
704 local_range() const;
705
706 /**
707 * Return whether @p index is in the local range or not, see also
708 * local_range().
709 */
710 bool
711 in_local_range(const size_type index) const;
712
713 /**
714 * Return the number of nonzero elements of this sparsity pattern.
715 */
716 std::uint64_t
717 n_nonzero_elements() const;
718
719 /**
720 * Return the number of entries in the given row.
721 *
722 * In a parallel context, the row in question may of course not be
723 * stored on the current processor, and in that case it is not
724 * possible to query the number of entries in it. In that case,
725 * the returned value is `static_cast<size_type>(-1)`.
726 */
727 size_type
728 row_length(const size_type row) const;
729
730 /**
731 * Compute the bandwidth of the matrix represented by this structure. The
732 * bandwidth is the maximum of $|i-j|$ for which the index pair $(i,j)$
733 * represents a nonzero entry of the matrix. Consequently, the maximum
734 * bandwidth a $n\times m$ matrix can have is $\max\{n-1,m-1\}$.
735 */
736 size_type
737 bandwidth() const;
738
739 /**
740 * Return whether the object is empty. It is empty if no memory is
741 * allocated, which is the same as when both dimensions are zero.
742 */
743 bool
744 empty() const;
745
746 /**
747 * Return whether the index (<i>i,j</i>) exists in the sparsity pattern
748 * (i.e., it may be nonzero) or not.
749 */
750 bool
751 exists(const size_type i, const size_type j) const;
752
753 /**
754 * Return whether a given @p row is stored in the current object
755 * on this process.
756 */
757 bool
758 row_is_stored_locally(const size_type i) const;
759
760 /**
761 * Determine an estimate for the memory consumption (in bytes) of this
762 * object. Currently not implemented for this class.
763 */
764 std::size_t
765 memory_consumption() const;
766
767 /** @} */
768 /**
769 * @name Adding entries
770 */
771 /** @{ */
772 /**
773 * Add the element (<i>i,j</i>) to the sparsity pattern.
774 */
775 void
776 add(const size_type i, const size_type j);
777
778
779 /**
780 * Add several elements in one row to the sparsity pattern.
781 */
782 template <typename ForwardIterator>
783 void
784 add_entries(const size_type row,
785 ForwardIterator begin,
786 ForwardIterator end,
787 const bool indices_are_sorted = false);
788
789 virtual void
790 add_row_entries(
791 const dealii::types::global_dof_index &row,
792 const ArrayView<const dealii::types::global_dof_index> &columns,
793 const bool indices_are_sorted = false) override;
794
795 using SparsityPatternBase::add_entries;
796
797 /** @} */
798 /**
799 * @name Access of underlying Trilinos data
800 */
801 /** @{ */
802
803 /**
804 * Return a Teuchos::RCP to the underlying Trilinos Tpetra::CrsGraph
805 * data that stores the sparsity pattern.
806 */
807 Teuchos::RCP<TpetraTypes::GraphType<MemorySpace>>
808 trilinos_sparsity_pattern() const;
809
810 /**
811 * Return a const Teuchos::RCP to the underlying Trilinos Tpetra::Map that
812 * sets the parallel partitioning of the domain space of this sparsity
813 * pattern, i.e., the partitioning of the vectors matrices based on this
814 * sparsity pattern are multiplied with.
815 */
816 Teuchos::RCP<const TpetraTypes::MapType<MemorySpace>>
817 domain_partitioner() const;
818
819 /**
820 * Return a const Teuchos::RCP to the underlying Trilinos Tpetra::Map that
821 * sets the partitioning of the range space of this sparsity pattern,
822 * i.e., the partitioning of the vectors that are result from matrix-
823 * vector products.
824 */
825 Teuchos::RCP<const TpetraTypes::MapType<MemorySpace>>
826 range_partitioner() const;
827
828 /**
829 * Return the underlying MPI communicator.
830 */
831 MPI_Comm
832 get_mpi_communicator() const;
833
834 /**
835 * Return the underlying Teuchos MPI communicator.
836 */
837 Teuchos::RCP<const Teuchos::Comm<int>>
838 get_teuchos_mpi_communicator() const;
839
840 /** @} */
841
842 /**
843 * @name Partitioners
844 */
845 /** @{ */
846
847 /**
848 * Return the partitioning of the domain space of this pattern, i.e., the
849 * partitioning of the vectors a matrix based on this sparsity pattern has
850 * to be multiplied with.
851 */
852 IndexSet
853 locally_owned_domain_indices() const;
854
855 /**
856 * Return the partitioning of the range space of this pattern, i.e., the
857 * partitioning of the vectors that are the result from matrix-vector
858 * products from a matrix based on this pattern.
859 */
860 IndexSet
861 locally_owned_range_indices() const;
862
863 /** @} */
864
865 /**
866 * @name Iterators
867 */
868 /** @{ */
869
870 /**
871 * Iterator starting at the first entry.
872 */
873 const_iterator
874 begin() const;
875
876 /**
877 * Final iterator.
878 */
879 const_iterator
880 end() const;
881
882 /**
883 * Iterator starting at the first entry of row @p r.
884 *
885 * Note that if the given row is empty, i.e. does not contain any nonzero
886 * entries, then the iterator returned by this function equals
887 * <tt>end(r)</tt>. Note also that the iterator may not be dereferenceable
888 * in that case.
889 */
890 const_iterator
891 begin(const size_type r) const;
892
893 /**
894 * Final iterator of row <tt>r</tt>. It points to the first element past
895 * the end of line @p r, or past the end of the entire sparsity pattern.
896 *
897 * Note that the end iterator is not necessarily dereferenceable. This is
898 * in particular the case if it is the end iterator for the last row of a
899 * matrix.
900 */
901 const_iterator
902 end(const size_type r) const;
903
904 /** @} */
905 /**
906 * @name Input/Output
907 */
908 /** @{ */
909
910 /**
911 * Print (the locally owned part of) the sparsity pattern to the given
912 * stream, using the format <tt>(line,col)</tt>. The optional flag outputs
913 * the sparsity pattern in Trilinos style, where even the according
914 * processor number is printed to the stream, as well as a summary before
915 * actually writing the entries.
916 */
917 void
918 print(std::ostream &out,
919 const bool write_extended_trilinos_info = false) const;
920
921 /**
922 * Print the sparsity of the matrix in a format that <tt>gnuplot</tt>
923 * understands and which can be used to plot the sparsity pattern in a
924 * graphical way. The format consists of pairs <tt>i j</tt> of nonzero
925 * elements, each representing one entry of this matrix, one per line of
926 * the output file. Indices are counted from zero on, as usual. Since
927 * sparsity patterns are printed in the same way as matrices are
928 * displayed, we print the negative of the column index, which means that
929 * the <tt>(0,0)</tt> element is in the top left rather than in the bottom
930 * left corner.
931 *
932 * Print the sparsity pattern in gnuplot by setting the data style to dots
933 * or points and use the <tt>plot</tt> command.
934 */
935 void
936 print_gnuplot(std::ostream &out) const;
937
938 /** @} */
939 /**
940 * @addtogroup Exceptions
941 * @{
942 */
943 /**
944 * Exception
945 */
946 DeclException1(ExcTrilinosError,
947 int,
948 << "An error with error number " << arg1
949 << " occurred while calling a Trilinos function");
950
951 /**
952 * Exception
953 */
954 DeclException2(ExcInvalidIndex,
955 size_type,
956 size_type,
957 << "The entry with index <" << arg1 << ',' << arg2
958 << "> does not exist.");
959
960 /**
961 * Exception
962 */
963 DeclException4(ExcAccessToNonLocalElement,
964 size_type,
965 size_type,
966 size_type,
967 size_type,
968 << "You tried to access element (" << arg1 << '/' << arg2
969 << ')'
970 << " of a distributed matrix, but only rows in range ["
971 << arg3 << ',' << arg4
972 << "] are stored locally and can be accessed.");
973
974 /**
975 * Exception
976 */
977 DeclException2(ExcAccessToNonPresentElement,
978 size_type,
979 size_type,
980 << "You tried to access element (" << arg1 << '/' << arg2
981 << ')' << " of a sparse matrix, but it appears to not"
982 << " exist in the Trilinos sparsity pattern.");
983 /** @} */
984 private:
985 /**
986 * Teuchos::RCP to the user-supplied Tpetra Trilinos mapping of the matrix
987 * columns that assigns parts of the matrix to the individual processes.
988 */
989 Teuchos::RCP<TpetraTypes::MapType<MemorySpace>> column_space_map;
990
991 /**
992 * A sparsity pattern object in Trilinos to be used for finite element
993 * based problems which allows for adding non-local elements to the
994 * pattern.
995 */
996 Teuchos::RCP<TpetraTypes::GraphType<MemorySpace>> graph;
997
998 /**
999 * A sparsity pattern object for the non-local part of the sparsity
1000 * pattern that is going to be sent to the owning processor. Only used
1001 * when the particular constructor or reinit method with writable_rows
1002 * argument is set
1003 */
1004 Teuchos::RCP<TpetraTypes::GraphType<MemorySpace>> nonlocal_graph;
1005
1006 // TODO: currently only for double
1007 friend class SparseMatrix<double, MemorySpace>;
1008 friend class SparsityPatternIterators::Accessor<MemorySpace>;
1009 friend class SparsityPatternIterators::Iterator<MemorySpace>;
1010 };
1011
1012
1013
1014 // ---------------- inline and template functions -----------------
1015
1016
1017 # ifndef DOXYGEN
1018
1019 namespace SparsityPatternIterators
1020 {
1021 template <typename MemorySpace>
1022 inline Accessor<MemorySpace>::Accessor(
1023 const SparsityPattern<MemorySpace> *sp,
1024 const size_type row,
1025 const size_type index)
1026 : sparsity_pattern(const_cast<SparsityPattern<MemorySpace> *>(sp))
1027 , a_row(row)
1028 , a_index(index)
1029 {
1030 visit_present_row();
1031 }
1032
1033
1034
1035 template <typename MemorySpace>
1036 inline typename Accessor<MemorySpace>::size_type
1037 Accessor<MemorySpace>::row() const
1038 {
1039 Assert(a_row < sparsity_pattern->n_rows(),
1040 ExcBeyondEndOfSparsityPattern());
1041 return a_row;
1042 }
1043
1044
1045
1046 template <typename MemorySpace>
1047 inline typename Accessor<MemorySpace>::size_type
1048 Accessor<MemorySpace>::column() const
1049 {
1050 Assert(a_row < sparsity_pattern->n_rows(),
1051 ExcBeyondEndOfSparsityPattern());
1052 return (*colnum_cache)[a_index];
1053 }
1054
1055
1056
1057 template <typename MemorySpace>
1058 inline typename Accessor<MemorySpace>::size_type
1059 Accessor<MemorySpace>::index() const
1060 {
1061 Assert(a_row < sparsity_pattern->n_rows(),
1062 ExcBeyondEndOfSparsityPattern());
1063 return a_index;
1064 }
1065
1066
1067
1068 template <typename MemorySpace>
1069 inline Iterator<MemorySpace>::Iterator(
1070 const SparsityPattern<MemorySpace> *sp,
1071 const size_type row,
1072 const size_type index)
1073 : accessor(sp, row, index)
1074 {}
1075
1076
1077
1078 template <typename MemorySpace>
1079 inline Iterator<MemorySpace>::Iterator(const Iterator<MemorySpace> &) =
1080 default;
1081
1082
1083
1084 template <typename MemorySpace>
1085 inline Iterator<MemorySpace> &
1086 Iterator<MemorySpace>::operator++()
1087 {
1088 Assert(accessor.a_row < accessor.sparsity_pattern->n_rows(),
1089 ExcIteratorPastEnd());
1090
1091 ++accessor.a_index;
1092
1093 // If at end of line: do one step, then cycle until we find a row with a
1094 // nonzero number of entries that is stored locally.
1095 if (accessor.a_index >=
1096 static_cast<dealii::types::signed_global_dof_index>(
1097 accessor.colnum_cache->size()))
1098 {
1099 accessor.a_index = 0;
1100 ++accessor.a_row;
1101
1102 while (accessor.a_row <
1103 static_cast<dealii::types::signed_global_dof_index>(
1104 accessor.sparsity_pattern->n_rows()))
1105 {
1106 const auto row_length =
1107 accessor.sparsity_pattern->row_length(accessor.a_row);
1108 if (row_length == 0 ||
1109 !accessor.sparsity_pattern->row_is_stored_locally(
1110 accessor.a_row))
1111 ++accessor.a_row;
1112 else
1113 break;
1114 }
1115
1116 accessor.visit_present_row();
1117 }
1118 return *this;
1119 }
1120
1121
1122
1123 template <typename MemorySpace>
1124 inline Iterator<MemorySpace>
1125 Iterator<MemorySpace>::operator++(int)
1126 {
1127 const Iterator<MemorySpace> old_state = *this;
1128 ++(*this);
1129 return old_state;
1130 }
1131
1132
1133
1134 template <typename MemorySpace>
1135 inline const Accessor<MemorySpace> &
1136 Iterator<MemorySpace>::operator*() const
1137 {
1138 return accessor;
1139 }
1140
1141
1142
1143 template <typename MemorySpace>
1144 inline const Accessor<MemorySpace> *
1145 Iterator<MemorySpace>::operator->() const
1146 {
1147 return &accessor;
1148 }
1149
1150
1151
1152 template <typename MemorySpace>
1153 inline bool
1154 Iterator<MemorySpace>::operator==(
1155 const Iterator<MemorySpace> &other) const
1156 {
1157 return (accessor.a_row == other.accessor.a_row &&
1158 accessor.a_index == other.accessor.a_index);
1159 }
1160
1161
1162
1163 template <typename MemorySpace>
1164 inline bool
1165 Iterator<MemorySpace>::operator!=(
1166 const Iterator<MemorySpace> &other) const
1167 {
1168 return !(*this == other);
1169 }
1170
1171
1172
1173 template <typename MemorySpace>
1174 inline bool
1175 Iterator<MemorySpace>::operator<(const Iterator<MemorySpace> &other) const
1176 {
1177 return (accessor.row() < other.accessor.row() ||
1178 (accessor.row() == other.accessor.row() &&
1179 accessor.index() < other.accessor.index()));
1180 }
1181
1182 } // namespace SparsityPatternIterators
1183
1184
1185
1186 template <typename MemorySpace>
1187 inline typename SparsityPattern<MemorySpace>::const_iterator
1188 SparsityPattern<MemorySpace>::begin() const
1189 {
1190 const size_type first_valid_row = this->local_range().first;
1191 return const_iterator(this, first_valid_row, 0);
1192 }
1193
1194
1195
1196 template <typename MemorySpace>
1197 inline typename SparsityPattern<MemorySpace>::const_iterator
1198 SparsityPattern<MemorySpace>::end() const
1199 {
1200 return const_iterator(this, n_rows(), 0);
1201 }
1202
1203
1204
1205 template <typename MemorySpace>
1206 inline typename SparsityPattern<MemorySpace>::const_iterator
1207 SparsityPattern<MemorySpace>::begin(const size_type r) const
1208 {
1209 AssertIndexRange(r, n_rows());
1210 if (row_length(r) > 0)
1211 return const_iterator(this, r, 0);
1212 else
1213 return end(r);
1214 }
1215
1216
1217
1218 template <typename MemorySpace>
1219 inline typename SparsityPattern<MemorySpace>::const_iterator
1220 SparsityPattern<MemorySpace>::end(const size_type r) const
1221 {
1222 AssertIndexRange(r, n_rows());
1223
1224 // place the iterator on the first entry
1225 // past this line, or at the end of the
1226 // matrix
1227 for (size_type i = r + 1; i < n_rows(); ++i)
1228 if (row_length(i) > 0)
1229 return const_iterator(this, i, 0);
1230
1231 // if there is no such line, then take the
1232 // end iterator of the matrix
1233 return end();
1234 }
1235
1236
1237
1238 template <typename MemorySpace>
1239 inline bool
1240 SparsityPattern<MemorySpace>::in_local_range(const size_type index) const
1241 {
1242 const TrilinosWrappers::types::int_type begin =
1243 graph->getRowMap()->getMinGlobalIndex();
1244 const TrilinosWrappers::types::int_type end =
1245 graph->getRowMap()->getMaxGlobalIndex() + 1;
1246
1247 return ((index >= static_cast<size_type>(begin)) &&
1248 (index < static_cast<size_type>(end)));
1249 }
1250
1251
1252
1253 template <typename MemorySpace>
1254 inline bool
1255 SparsityPattern<MemorySpace>::is_compressed() const
1256 {
1257 return graph->isFillComplete();
1258 }
1259
1260
1261
1262 template <typename MemorySpace>
1263 inline bool
1264 SparsityPattern<MemorySpace>::empty() const
1265 {
1266 return ((n_rows() == 0) && (n_cols() == 0));
1267 }
1268
1269
1270
1271 template <typename MemorySpace>
1272 inline void
1273 SparsityPattern<MemorySpace>::add(const size_type i, const size_type j)
1274 {
1275 add_entries(i, &j, &j + 1);
1276 }
1277
1278
1279
1280 template <typename MemorySpace>
1281 template <typename ForwardIterator>
1282 inline void
1283 SparsityPattern<MemorySpace>::add_entries(const size_type row,
1284 ForwardIterator begin,
1285 ForwardIterator end,
1286 const bool /*indices_are_sorted*/)
1287 {
1288 if (begin == end)
1289 return;
1290
1291 // verify that the size of the data type Trilinos expects matches that the
1292 // iterator points to. we allow for some slippage between signed and
1293 // unsigned and only compare that they are both either 32 or 64 bit. to
1294 // write this test properly, not that we cannot compare the size of
1295 // '*begin' because 'begin' may be an iterator and '*begin' may be an
1296 // accessor class. consequently, we need to somehow get an actual value
1297 // from it which we can by evaluating an expression such as when
1298 // multiplying the value produced by 2
1299 Assert(sizeof(TrilinosWrappers::types::int_type) == sizeof((*begin) * 2),
1300 ExcNotImplemented());
1301
1302 const TrilinosWrappers::types::int_type *col_index_ptr_begin =
1303 reinterpret_cast<TrilinosWrappers::types::int_type *>(
1304 const_cast<std::decay_t<decltype(*begin)> *>(&*begin));
1305
1306 const TrilinosWrappers::types::int_type *col_index_ptr_end =
1307 reinterpret_cast<TrilinosWrappers::types::int_type *>(
1308 const_cast<std::decay_t<decltype(*end)> *>(&*end));
1309
1310 // Check at least for the first index that the conversion actually works
1311 AssertDimension(*col_index_ptr_begin, *begin);
1312 AssertDimension(*col_index_ptr_end, *end);
1313 TrilinosWrappers::types::int_type trilinos_row_index = row;
1314
1315 // TODO: The following line creates an array by copying the entries.
1316 // Perhaps there is a way to only create a 'view' of these arrays
1317 // and pass that to Tpetra?
1318 Teuchos::Array<TrilinosWrappers::types::int_type> array(
1319 col_index_ptr_begin, col_index_ptr_end);
1320
1321 if (row_is_stored_locally(row))
1322 graph->insertGlobalIndices(trilinos_row_index, array());
1323 else if (nonlocal_graph.get() != nullptr)
1324 {
1325 // this is the case when we have explicitly set the off-processor rows
1326 // and want to create a separate matrix object for them (to retain
1327 // thread-safety)
1328 Assert(nonlocal_graph->getRowMap()->getLocalElement(row) !=
1329 Teuchos::OrdinalTraits<
1330 dealii::types::signed_global_dof_index>::invalid(),
1331 ExcMessage("Attempted to write into off-processor matrix row "
1332 "that has not be specified as being writable upon "
1333 "initialization"));
1334 nonlocal_graph->insertGlobalIndices(trilinos_row_index, array);
1335 }
1336 else
1337 graph->insertGlobalIndices(trilinos_row_index, array);
1338 }
1339
1340
1341
1342 template <typename MemorySpace>
1343 inline Teuchos::RCP<Tpetra::CrsGraph<int,
1344 dealii::types::signed_global_dof_index,
1345 TpetraTypes::NodeType<MemorySpace>>>
1346 SparsityPattern<MemorySpace>::trilinos_sparsity_pattern() const
1347 {
1348 return graph;
1349 }
1350
1351
1352
1353 template <typename MemorySpace>
1354 inline IndexSet
1355 SparsityPattern<MemorySpace>::locally_owned_domain_indices() const
1356 {
1357 return IndexSet(graph->getDomainMap().getConst());
1358 }
1359
1360
1361
1362 template <typename MemorySpace>
1363 inline IndexSet
1364 SparsityPattern<MemorySpace>::locally_owned_range_indices() const
1365 {
1366 return IndexSet(graph->getRangeMap().getConst());
1367 }
1368
1369 # endif // DOXYGEN
1370 } // namespace TpetraWrappers
1371
1372 } // namespace LinearAlgebra
1373
1374
1375 DEAL_II_NAMESPACE_CLOSE
1376
1377
1378 #else
1379
1380 // Make sure the scripts that create the C++20 module input files have
1381 // something to latch on if the preprocessor #ifdef above would
1382 // otherwise lead to an empty content of the file.
1383 DEAL_II_NAMESPACE_OPEN
1384 DEAL_II_NAMESPACE_CLOSE
1385
1386 #endif // DEAL_II_TRILINOS_WITH_TPETRA
1387
1388 #endif