Debian Codegraph @

include/deal.II/lac/trilinos_sparsity_pattern.h

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