Debian Codegraph @

include/deal.II/lac/chunk_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_chunk_sparsity_pattern_h
16 #define dealii_chunk_sparsity_pattern_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/enable_observer_pointer.h>
22 #include <deal.II/base/exceptions.h>
23
24 #include <deal.II/lac/sparsity_pattern.h>
25
26 #include <iostream>
27 #include <vector>
28
29 DEAL_II_NAMESPACE_OPEN
30
31
32 // Forward declaration
33 #ifndef DOXYGEN
34 template <typename>
35 class ChunkSparseMatrix;
36 #endif
37
38 /**
39 * @addtogroup Sparsity
40 * @{
41 */
42
43
44
45 /**
46 * Iterators on sparsity patterns
47 */
48 namespace ChunkSparsityPatternIterators
49 {
50 // forward declaration
51 class Iterator;
52
53 /**
54 * Accessor class for iterators into sparsity patterns. This class is also
55 * the base class for both const and non-const accessor classes into sparse
56 * matrices.
57 *
58 * Note that this class only allows read access to elements, providing their
59 * row and column number. It does not allow modifying the sparsity pattern
60 * itself.
61 */
62 class Accessor
63 {
64 public:
65 /**
66 * Declare the type for container size.
67 */
68 using size_type = types::global_dof_index;
69
70 /**
71 * Constructor.
72 */
73 Accessor(const ChunkSparsityPattern *matrix, const size_type row);
74
75 /**
76 * Constructor. Construct the end accessor for the given sparsity pattern.
77 */
78 Accessor(const ChunkSparsityPattern *matrix);
79
80 /**
81 * Row number of the element represented by this object. This function can
82 * only be called for entries for which is_valid_entry() is true.
83 */
84 size_type
85 row() const;
86
87 /**
88 * Return the global index from the reduced sparsity pattern.
89 */
90 std::size_t
91 reduced_index() const;
92
93 /**
94 * Column number of the element represented by this object. This function
95 * can only be called for entries for which is_valid_entry() is true.
96 */
97 size_type
98 column() const;
99
100 /**
101 * Return whether the sparsity pattern entry pointed to by this iterator
102 * is valid or not. Note that after compressing the sparsity pattern, all
103 * entries are valid. However, before compression, the sparsity pattern
104 * allocated some memory to be used while still adding new nonzero
105 * entries; if you create iterators in this phase of the sparsity
106 * pattern's lifetime, you will iterate over elements that are not valid.
107 * If this is so, then this function will return false.
108 */
109 bool
110 is_valid_entry() const;
111
112
113 /**
114 * Comparison. True, if both iterators point to the same matrix position.
115 */
116 bool
117 operator==(const Accessor &) const;
118
119
120 /**
121 * Comparison operator. Result is true if either the first row number is
122 * smaller or if the row numbers are equal and the first index is smaller.
123 *
124 * This function is only valid if both iterators point into the same
125 * sparsity pattern.
126 */
127 bool
128 operator<(const Accessor &) const;
129
130 protected:
131 /**
132 * The sparsity pattern we operate on accessed.
133 */
134 const ChunkSparsityPattern *sparsity_pattern;
135
136 /**
137 * The accessor of the (reduced) sparsity pattern.
138 */
139 SparsityPatternIterators::Accessor reduced_accessor;
140
141 /**
142 * Current chunk row number.
143 */
144 size_type chunk_row;
145
146 /**
147 * Current chunk col number.
148 */
149 size_type chunk_col;
150
151 /**
152 * Move the accessor to the next nonzero entry in the matrix.
153 */
154 void
155 advance();
156
157 // Grant access to iterator class.
158 friend class Iterator;
159 };
160
161
162
163 /**
164 * Iterator that walks over the elements of a sparsity pattern.
165 */
166 class Iterator
167 {
168 public:
169 /**
170 * Declare the type for container size.
171 */
172 using size_type = types::global_dof_index;
173
174 /**
175 * Constructor. Create an iterator into the sparsity pattern @p sp for the
176 * given row and the index within it.
177 */
178 Iterator(const ChunkSparsityPattern *sp, const size_type row);
179
180 /**
181 * Prefix increment.
182 */
183 Iterator &
184 operator++();
185
186 /**
187 * Postfix increment.
188 */
189 Iterator
190 operator++(int);
191
192 /**
193 * Dereferencing operator.
194 */
195 const Accessor &
196 operator*() const;
197
198 /**
199 * Dereferencing operator.
200 */
201 const Accessor *
202 operator->() const;
203
204 /**
205 * Comparison. True, if both iterators point to the same matrix position.
206 */
207 bool
208 operator==(const Iterator &) const;
209
210 /**
211 * Inverse of <tt>==</tt>.
212 */
213 bool
214 operator!=(const Iterator &) const;
215
216 /**
217 * Comparison operator. Result is true if either the first row number is
218 * smaller or if the row numbers are equal and the first index is smaller.
219 *
220 * This function is only valid if both iterators point into the same
221 * matrix.
222 */
223 bool
224 operator<(const Iterator &) const;
225
226 private:
227 /**
228 * Store an object of the accessor class.
229 */
230 Accessor accessor;
231 };
232 } // namespace ChunkSparsityPatternIterators
233
234
235
236 /**
237 * Structure representing the sparsity pattern of a sparse matrix. This class
238 * is an example of the "static" type of
239 * @ref Sparsity.
240 * It uses the compressed row storage (CSR) format to store data.
241 *
242 * The use of this class is demonstrated in step-51.
243 */
244 class ChunkSparsityPattern : public EnableObserverPointer
245 {
246 public:
247 /**
248 * Declare the type for container size.
249 */
250 using size_type = types::global_dof_index;
251 /**
252 * Typedef an iterator class that allows to walk over all nonzero elements
253 * of a sparsity pattern.
254 */
255 using const_iterator = ChunkSparsityPatternIterators::Iterator;
256
257 /**
258 * Typedef an iterator class that allows to walk over all nonzero elements
259 * of a sparsity pattern.
260 *
261 * Since the iterator does not allow to modify the sparsity pattern, this
262 * type is the same as that for @p const_iterator.
263 */
264 using iterator = ChunkSparsityPatternIterators::Iterator;
265
266 /**
267 * Define a value which is used to indicate that a certain value in the
268 * colnums array is unused, i.e. does not represent a certain column number
269 * index.
270 *
271 * Indices with this invalid value are used to insert new entries to the
272 * sparsity pattern using the add() member function, and are removed when
273 * calling compress().
274 *
275 * You should not assume that the variable declared here has a certain
276 * value. The initialization is given here only to enable the compiler to
277 * perform some optimizations, but the actual value of the variable may
278 * change over time.
279 */
280 static const size_type invalid_entry = SparsityPattern::invalid_entry;
281
282 /**
283 * Initialize the matrix empty, that is with no memory allocated. This is
284 * useful if you want such objects as member variables in other classes. You
285 * can make the structure usable by calling the reinit() function.
286 */
287 ChunkSparsityPattern();
288
289 /**
290 * Copy constructor. This constructor is only allowed to be called if the
291 * matrix structure to be copied is empty. This is so in order to prevent
292 * involuntary copies of objects for temporaries, which can use large
293 * amounts of computing time. However, copy constructors are needed if one
294 * wants to place a ChunkSparsityPattern in a container, e.g., to write such
295 * statements like <tt>v.push_back (ChunkSparsityPattern());</tt>, with
296 * <tt>v</tt> a vector of ChunkSparsityPattern objects.
297 *
298 * Usually, it is sufficient to use the explicit keyword to disallow
299 * unwanted temporaries, but this does not work for <tt>std::vector</tt>.
300 * Since copying a structure like this is not useful anyway because multiple
301 * matrices can use the same sparsity structure, copies are only allowed for
302 * empty objects, as described above.
303 */
304 ChunkSparsityPattern(const ChunkSparsityPattern &);
305
306 /**
307 * Initialize a rectangular matrix.
308 *
309 * @arg m number of rows @arg n number of columns @arg max_per_row maximum
310 * number of nonzero entries per row
311 */
312 ChunkSparsityPattern(const size_type m,
313 const size_type n,
314 const size_type max_chunks_per_row,
315 const size_type chunk_size);
316
317 /**
318 * Initialize a rectangular matrix.
319 *
320 * @arg m number of rows @arg n number of columns @arg row_lengths possible
321 * number of nonzero entries for each row. This vector must have one entry
322 * for each row.
323 */
324 ChunkSparsityPattern(const size_type m,
325 const size_type n,
326 const std::vector<size_type> &row_lengths,
327 const size_type chunk_size);
328
329 /**
330 * Initialize a quadratic matrix of dimension <tt>n</tt> with at most
331 * <tt>max_per_row</tt> nonzero entries per row.
332 *
333 * This constructor automatically enables optimized storage of diagonal
334 * elements. To avoid this, use the constructor taking row and column
335 * numbers separately.
336 */
337 ChunkSparsityPattern(const size_type n,
338 const size_type max_per_row,
339 const size_type chunk_size);
340
341 /**
342 * Initialize a quadratic matrix.
343 *
344 * @arg m number of rows and columns @arg row_lengths possible number of
345 * nonzero entries for each row. This vector must have one entry for each
346 * row.
347 */
348 ChunkSparsityPattern(const size_type m,
349 const std::vector<size_type> &row_lengths,
350 const size_type chunk_size);
351
352 /**
353 * Destructor.
354 */
355 ~ChunkSparsityPattern() override = default;
356
357 /**
358 * Copy operator. For this the same holds as for the copy constructor: it is
359 * declared, defined and fine to be called, but the latter only for empty
360 * objects.
361 */
362 ChunkSparsityPattern &
363 operator=(const ChunkSparsityPattern &);
364
365 /**
366 * Reallocate memory and set up data structures for a new matrix with <tt>m
367 * </tt>rows and <tt>n</tt> columns, with at most <tt>max_per_row</tt>
368 * nonzero entries per row.
369 *
370 * This function simply maps its operations to the other <tt>reinit</tt>
371 * function.
372 */
373 void
374 reinit(const size_type m,
375 const size_type n,
376 const size_type max_per_row,
377 const size_type chunk_size);
378
379 /**
380 * Reallocate memory for a matrix of size <tt>m x n</tt>. The number of
381 * entries for each row is taken from the array <tt>row_lengths</tt> which
382 * has to give this number of each row <tt>i=1...m</tt>.
383 *
384 * If <tt>m*n==0</tt> all memory is freed, resulting in a total
385 * reinitialization of the object. If it is nonzero, new memory is only
386 * allocated if the new size extends the old one. This is done to save time
387 * and to avoid fragmentation of the heap.
388 *
389 * If the number of rows equals the number of columns then diagonal elements
390 * are stored first in each row to allow optimized access in relaxation
391 * methods of SparseMatrix.
392 */
393 void
394 reinit(const size_type m,
395 const size_type n,
396 const std::vector<size_type> &row_lengths,
397 const size_type chunk_size);
398
399 /**
400 * Same as above, but with an ArrayView argument instead.
401 */
402 void
403 reinit(const size_type m,
404 const size_type n,
405 const ArrayView<const size_type> &row_lengths,
406 const size_type chunk_size);
407
408 /**
409 * This function compresses the sparsity structure that this object
410 * represents. It does so by eliminating unused entries and sorting the
411 * remaining ones to allow faster access by usage of binary search
412 * algorithms. A special sorting scheme is used for the diagonal entry of
413 * quadratic matrices, which is always the first entry of each row.
414 *
415 * The memory which is no more needed is released.
416 *
417 * SparseMatrix objects require the ChunkSparsityPattern objects they are
418 * initialized with to be compressed, to reduce memory requirements.
419 */
420 void
421 compress();
422
423 /**
424 * This function can be used as a replacement for reinit(), subsequent calls
425 * to add() and a final call to close() if you know exactly in advance the
426 * entries that will form the matrix sparsity pattern.
427 *
428 * The first two parameters determine the size of the matrix. For the two
429 * last ones, note that a sparse matrix can be described by a sequence of
430 * rows, each of which is represented by a sequence of pairs of column
431 * indices and values. In the present context, the begin() and end()
432 * parameters designate iterators (of forward iterator type) into a
433 * container, one representing one row. The distance between begin() and
434 * end() should therefore be equal to n_rows(). These iterators may be
435 * iterators of <tt>std::vector</tt>, <tt>std::list</tt>, pointers into a
436 * C-style array, or any other iterator satisfying the requirements of a
437 * forward iterator. The objects pointed to by these iterators (i.e. what we
438 * get after applying <tt>operator*</tt> or <tt>operator-></tt> to one of
439 * these iterators) must be a container itself that provides functions
440 * <tt>begin</tt> and <tt>end</tt> designating a range of iterators that
441 * describe the contents of one line. Dereferencing these inner iterators
442 * must either yield a pair of an integer as column index and a
443 * value of arbitrary type (such a type would be used if we wanted to
444 * describe a sparse matrix with one such object), or simply an integer (if we
445 * only wanted to describe a sparsity pattern). The function is able to
446 * determine itself whether an integer or a pair is what we get after
447 * dereferencing the inner iterators, through some template magic.
448 *
449 * While the order of the outer iterators denotes the different rows of the
450 * matrix, the order of the inner iterator denoting the columns does not
451 * matter, as they are sorted internal to this function anyway.
452 *
453 * Since that all sounds very complicated, consider the following example
454 * code, which may be used to fill a sparsity pattern:
455 * @code
456 * std::vector<std::vector<size_type> > column_indices (n_rows);
457 * for (size_type row=0; row<n_rows; ++row)
458 * // generate necessary columns in this row
459 * fill_row (column_indices[row]);
460 *
461 * sparsity.copy_from (n_rows, n_cols,
462 * column_indices.begin(),
463 * column_indices.end());
464 * @endcode
465 *
466 * Note that this example works since the iterators dereferenced yield
467 * containers with functions <tt>begin</tt> and <tt>end</tt> (namely
468 * <tt>std::vector</tt>s), and the inner iterators dereferenced yield
469 * integers as column indices. Note that we could have replaced
470 * each of the two <tt>std::vector</tt> occurrences by <tt>std::list</tt>,
471 * and the inner one by <tt>std::set</tt> as well.
472 *
473 * Another example would be as follows, where we initialize a whole matrix,
474 * not only a sparsity pattern:
475 * @code
476 * std::vector<std::map<size_type,double> > entries (n_rows);
477 * for (size_type row=0; row<n_rows; ++row)
478 * // generate necessary pairs of columns
479 * // and corresponding values in this row
480 * fill_row (entries[row]);
481 *
482 * sparsity.copy_from (n_rows, n_cols,
483 * column_indices.begin(),
484 * column_indices.end());
485 * matrix.reinit (sparsity);
486 * matrix.copy_from (column_indices.begin(),
487 * column_indices.end());
488 * @endcode
489 *
490 * This example works because dereferencing iterators of the inner type
491 * yields a pair of integers and a value, the first of which we
492 * take as column index. As previously, the outer <tt>std::vector</tt> could
493 * be replaced by <tt>std::list</tt>, and the inner
494 * <tt>std::map<size_type,double></tt> could be replaced by
495 * <tt>std::vector<std::pair<size_type,double> ></tt>, or a list or set of
496 * such pairs, as they all return iterators that point to such pairs.
497 */
498 template <typename ForwardIterator>
499 void
500 copy_from(const size_type n_rows,
501 const size_type n_cols,
502 const ForwardIterator begin,
503 const ForwardIterator end,
504 const size_type chunk_size);
505
506 /**
507 * Copy data from an object of type DynamicSparsityPattern. Previous content
508 * of this object is lost, and the sparsity pattern is in compressed mode
509 * afterwards.
510 */
511 template <typename SparsityPatternType>
512 void
513 copy_from(const SparsityPatternType &dsp, const size_type chunk_size);
514
515 /**
516 * Take a full matrix and use its nonzero entries to generate a sparse
517 * matrix entry pattern for this object.
518 *
519 * Previous content of this object is lost, and the sparsity pattern is in
520 * compressed mode afterwards.
521 */
522 template <typename number>
523 void
524 copy_from(const FullMatrix<number> &matrix, const size_type chunk_size);
525
526 /**
527 * Set the sparsity pattern of the chunk sparsity pattern to be given by
528 * <tt>chunk_size*chunksize</tt> blocks of the sparsity pattern for chunks
529 * specified. Note that the final number of rows <tt>m</tt> of the sparsity
530 * pattern will be approximately <tt>sparsity_pattern_for_chunks.n_rows() *
531 * chunk_size</tt> (modulo padding elements in the last chunk) and similarly
532 * for the number of columns <tt>n</tt>.
533 *
534 * This is a special initialization option in case you can tell the position
535 * of the chunk already from the beginning without generating the sparsity
536 * pattern using <tt>make_sparsity_pattern</tt> calls. This bypasses the
537 * search for chunks but of course needs to be handled with care in order to
538 * give a correct sparsity pattern.
539 *
540 * Previous content of this object is lost, and the sparsity pattern is in
541 * compressed mode afterwards.
542 */
543 template <typename Sparsity>
544 void
545 create_from(const size_type m,
546 const size_type n,
547 const Sparsity &sparsity_pattern_for_chunks,
548 const size_type chunk_size,
549 const bool optimize_diagonal = true);
550
551 /**
552 * Return whether the object is empty. It is empty if no memory is
553 * allocated, which is the same as that both dimensions are zero.
554 */
555 bool
556 empty() const;
557
558 /**
559 * Return the chunk size given as argument when constructing this object.
560 */
561 size_type
562 get_chunk_size() const;
563
564 /**
565 * Return the maximum number of entries per row. Before compression, this
566 * equals the number given to the constructor, while after compression, it
567 * equals the maximum number of entries actually allocated by the user.
568 */
569 size_type
570 max_entries_per_row() const;
571
572 /**
573 * Add a nonzero entry to the matrix. This function may only be called for
574 * non-compressed sparsity patterns.
575 *
576 * If the entry already exists, nothing bad happens.
577 */
578 void
579 add(const size_type i, const size_type j);
580
581 /**
582 * Make the sparsity pattern symmetric by adding the sparsity pattern of the
583 * transpose object.
584 *
585 * This function throws an exception if the sparsity pattern does not
586 * represent a quadratic matrix.
587 */
588 void
589 symmetrize();
590
591 /**
592 * Return number of rows of this matrix, which equals the dimension of the
593 * image space.
594 */
595 inline size_type
596 n_rows() const;
597
598 /**
599 * Return number of columns of this matrix, which equals the dimension of
600 * the range space.
601 */
602 inline size_type
603 n_cols() const;
604
605 /**
606 * Check if a value at a certain position may be non-zero.
607 */
608 bool
609 exists(const size_type i, const size_type j) const;
610
611 /**
612 * Number of entries in a specific row.
613 */
614 size_type
615 row_length(const size_type row) const;
616
617 /**
618 * Compute the bandwidth of the matrix represented by this structure. The
619 * bandwidth is the maximum of $|i-j|$ for which the index pair $(i,j)$
620 * represents a nonzero entry of the matrix. Consequently, the maximum
621 * bandwidth a $n\times m$ matrix can have is $\max\{n-1,m-1\}$.
622 */
623 size_type
624 bandwidth() const;
625
626 /**
627 * Return the number of nonzero elements of this matrix. Actually, it
628 * returns the number of entries in the sparsity pattern; if any of the
629 * entries should happen to be zero, it is counted anyway.
630 *
631 * This function may only be called if the matrix struct is compressed. It
632 * does not make too much sense otherwise anyway.
633 */
634 size_type
635 n_nonzero_elements() const;
636
637 /**
638 * Return whether the structure is compressed or not.
639 */
640 bool
641 is_compressed() const;
642
643 /**
644 * Return whether this object stores only those entries that have been added
645 * explicitly, or if the sparsity pattern contains elements that have been
646 * added through other means (implicitly) while building it. For the current
647 * class, the result is true if and only if it is square because it then
648 * unconditionally stores the diagonal entries whether they have been added
649 * explicitly or not.
650 *
651 * This function mainly serves the purpose of describing the current class
652 * in cases where several kinds of sparsity patterns can be passed as
653 * template arguments.
654 */
655 bool
656 stores_only_added_elements() const;
657
658 /**
659 * Iterator starting at the first entry of the matrix. The resulting
660 * iterator can be used to walk over all nonzero entries of the sparsity
661 * pattern.
662 */
663 iterator
664 begin() const;
665
666 /**
667 * Final iterator.
668 */
669 iterator
670 end() const;
671
672 /**
673 * Iterator starting at the first entry of row <tt>r</tt>.
674 *
675 * Note that if the given row is empty, i.e. does not contain any nonzero
676 * entries, then the iterator returned by this function equals
677 * <tt>end(r)</tt>. Note also that the iterator may not be dereferenceable in
678 * that case.
679 */
680 iterator
681 begin(const size_type r) const;
682
683 /**
684 * Final iterator of row <tt>r</tt>. It points to the first element past the
685 * end of line @p r, or past the end of the entire sparsity pattern.
686 *
687 * Note that the end iterator is not necessarily dereferenceable. This is in
688 * particular the case if it is the end iterator for the last row of a
689 * matrix.
690 */
691 iterator
692 end(const size_type r) const;
693
694 /**
695 * Write the data of this object en bloc to a file. This is done in a binary
696 * mode, so the output is neither readable by humans nor (probably) by other
697 * computers using a different operating system of number format.
698 *
699 * The purpose of this function is that you can swap out matrices and
700 * sparsity pattern if you are short of memory, want to communicate between
701 * different programs, or allow objects to be persistent across different
702 * runs of the program.
703 */
704 void
705 block_write(std::ostream &out) const;
706
707 /**
708 * Read data that has previously been written by block_write() from a file.
709 * This is done using the inverse operations to the above function, so it is
710 * reasonably fast because the bitstream is not interpreted except for a few
711 * numbers up front.
712 *
713 * The object is resized on this operation, and all previous contents are
714 * lost.
715 *
716 * A primitive form of error checking is performed which will recognize the
717 * bluntest attempts to interpret some data as a vector stored bitwise to a
718 * file, but not more.
719 */
720 void
721 block_read(std::istream &in);
722
723 /**
724 * Print the sparsity of the matrix. The output consists of one line per row
725 * of the format <tt>[i,j1,j2,j3,...]</tt>. <i>i</i> is the row number and
726 * <i>jn</i> are the allocated columns in this row.
727 */
728 void
729 print(std::ostream &out) const;
730
731 /**
732 * Print the sparsity of the matrix in a format that <tt>gnuplot</tt>
733 * understands and which can be used to plot the sparsity pattern in a
734 * graphical way. The format consists of pairs <tt>i j</tt> of nonzero
735 * elements, each representing one entry of this matrix, one per line of the
736 * output file. Indices are counted from zero on, as usual. Since sparsity
737 * patterns are printed in the same way as matrices are displayed, we print
738 * the negative of the column index, which means that the <tt>(0,0)</tt>
739 * element is in the top left rather than in the bottom left corner.
740 *
741 * Print the sparsity pattern in gnuplot by setting the data style to dots
742 * or points and use the <tt>plot</tt> command.
743 */
744 void
745 print_gnuplot(std::ostream &out) const;
746
747 /**
748 * Determine an estimate for the memory consumption (in bytes) of this
749 * object. See MemoryConsumption.
750 */
751 std::size_t
752 memory_consumption() const;
753
754 /**
755 * @addtogroup Exceptions
756 * @{
757 */
758 /**
759 * Exception
760 */
761 DeclException1(ExcInvalidNumber,
762 size_type,
763 << "The provided number is invalid here: " << arg1);
764 /**
765 * Exception
766 */
767 DeclException2(ExcInvalidIndex,
768 size_type,
769 size_type,
770 << "The given index " << arg1 << " should be less than "
771 << arg2 << '.');
772 /**
773 * Exception
774 */
775 DeclException2(ExcNotEnoughSpace,
776 size_type,
777 size_type,
778 << "Upon entering a new entry to row " << arg1
779 << ": there was no free entry any more. " << std::endl
780 << "(Maximum number of entries for this row: " << arg2
781 << "; maybe the matrix is already compressed?)");
782 /**
783 * The operation is only allowed after the SparsityPattern has been set up
784 * and compress() was called.
785 */
786 DeclExceptionMsg(
787 ExcNotCompressed,
788 "The operation you attempted is only allowed after the SparsityPattern "
789 "has been set up and compress() was called.");
790 /**
791 * This operation changes the structure of the SparsityPattern and is not
792 * possible after compress() has been called.
793 */
794 DeclExceptionMsg(
795 ExcMatrixIsCompressed,
796 "The operation you attempted changes the structure of the SparsityPattern "
797 "and is not possible after compress() has been called.");
798 /**
799 * Exception
800 */
801 DeclException0(ExcEmptyObject);
802 /**
803 * Exception
804 */
805 DeclException2(ExcIteratorRange,
806 size_type,
807 size_type,
808 << "The iterators denote a range of " << arg1
809 << " elements, but the given number of rows was " << arg2);
810 /**
811 * Exception
812 */
813 DeclException0(ExcMETISNotInstalled);
814 /**
815 * Exception
816 */
817 DeclException1(ExcInvalidNumberOfPartitions,
818 size_type,
819 << "The number of partitions you gave is " << arg1
820 << ", but must be greater than zero.");
821 /**
822 * Exception
823 */
824 DeclException2(ExcInvalidArraySize,
825 size_type,
826 size_type,
827 << "The array has size " << arg1 << " but should have size "
828 << arg2);
829 /** @} */
830 private:
831 /**
832 * Number of rows that this sparsity structure shall represent.
833 */
834 size_type rows;
835
836 /**
837 * Number of columns that this sparsity structure shall represent.
838 */
839 size_type cols;
840
841 /**
842 * The size of chunks.
843 */
844 size_type chunk_size;
845
846 /**
847 * The reduced sparsity pattern. We store only which chunks exist, with each
848 * chunk a block in the matrix of size chunk_size by chunk_size.
849 */
850 SparsityPattern sparsity_pattern;
851
852 // Make all the chunk sparse matrix kinds friends.
853 template <typename>
854 friend class ChunkSparseMatrix;
855
856 // Make the accessor class a friend.
857 friend class ChunkSparsityPatternIterators::Accessor;
858 };
859
860
861 /** @} */
862 /*---------------------- Inline functions -----------------------------------*/
863
864 #ifndef DOXYGEN
865
866 namespace ChunkSparsityPatternIterators
867 {
868 inline Accessor::Accessor(const ChunkSparsityPattern *sparsity_pattern,
869 const size_type row)
870 : sparsity_pattern(sparsity_pattern)
871 , reduced_accessor(row == sparsity_pattern->n_rows() ?
872 *sparsity_pattern->sparsity_pattern.end() :
873 *sparsity_pattern->sparsity_pattern.begin(
874 row / sparsity_pattern->get_chunk_size()))
875 , chunk_row(row == sparsity_pattern->n_rows() ?
876 0 :
877 row % sparsity_pattern->get_chunk_size())
878 , chunk_col(0)
879 {}
880
881
882
883 inline Accessor::Accessor(const ChunkSparsityPattern *sparsity_pattern)
884 : sparsity_pattern(sparsity_pattern)
885 , reduced_accessor(*sparsity_pattern->sparsity_pattern.end())
886 , chunk_row(0)
887 , chunk_col(0)
888 {}
889
890
891
892 inline bool
893 Accessor::is_valid_entry() const
894 {
895 return reduced_accessor.is_valid_entry() &&
896 sparsity_pattern->get_chunk_size() * reduced_accessor.row() +
897 chunk_row <
898 sparsity_pattern->n_rows() &&
899 sparsity_pattern->get_chunk_size() * reduced_accessor.column() +
900 chunk_col <
901 sparsity_pattern->n_cols();
902 }
903
904
905
906 inline Accessor::size_type
907 Accessor::row() const
908 {
909 Assert(is_valid_entry() == true, ExcInvalidIterator());
910
911 return sparsity_pattern->get_chunk_size() * reduced_accessor.row() +
912 chunk_row;
913 }
914
915
916
917 inline Accessor::size_type
918 Accessor::column() const
919 {
920 Assert(is_valid_entry() == true, ExcInvalidIterator());
921
922 return sparsity_pattern->get_chunk_size() * reduced_accessor.column() +
923 chunk_col;
924 }
925
926
927
928 inline std::size_t
929 Accessor::reduced_index() const
930 {
931 Assert(is_valid_entry() == true, ExcInvalidIterator());
932
933 return reduced_accessor.linear_index;
934 }
935
936
937
938 inline bool
939 Accessor::operator==(const Accessor &other) const
940 {
941 // no need to check for equality of sparsity patterns as this is done in
942 // the reduced case already and every ChunkSparsityPattern has its own
943 // reduced sparsity pattern
944 return (reduced_accessor == other.reduced_accessor &&
945 chunk_row == other.chunk_row && chunk_col == other.chunk_col);
946 }
947
948
949
950 inline bool
951 Accessor::operator<(const Accessor &other) const
952 {
953 Assert(sparsity_pattern == other.sparsity_pattern, ExcInternalError());
954
955 if (chunk_row != other.chunk_row)
956 {
957 if (reduced_accessor.linear_index ==
958 reduced_accessor.container->n_nonzero_elements())
959 return false;
960 if (other.reduced_accessor.linear_index ==
961 reduced_accessor.container->n_nonzero_elements())
962 return true;
963
964 const auto global_row = sparsity_pattern->get_chunk_size() *
965 reduced_accessor.row() +
966 chunk_row,
967 other_global_row = sparsity_pattern->get_chunk_size() *
968 other.reduced_accessor.row() +
969 other.chunk_row;
970 if (global_row < other_global_row)
971 return true;
972 else if (global_row > other_global_row)
973 return false;
974 }
975
976 return (
977 reduced_accessor.linear_index < other.reduced_accessor.linear_index ||
978 (reduced_accessor.linear_index == other.reduced_accessor.linear_index &&
979 chunk_col < other.chunk_col));
980 }
981
982
983 inline void
984 Accessor::advance()
985 {
986 const auto chunk_size = sparsity_pattern->get_chunk_size();
987 Assert(chunk_row < chunk_size && chunk_col < chunk_size,
988 ExcIteratorPastEnd());
989 Assert(reduced_accessor.row() * chunk_size + chunk_row <
990 sparsity_pattern->n_rows() &&
991 reduced_accessor.column() * chunk_size + chunk_col <
992 sparsity_pattern->n_cols(),
993 ExcIteratorPastEnd());
994 if (chunk_size == 1)
995 {
996 reduced_accessor.advance();
997 return;
998 }
999
1000 ++chunk_col;
1001
1002 // end of chunk
1003 if (chunk_col == chunk_size ||
1004 reduced_accessor.column() * chunk_size + chunk_col ==
1005 sparsity_pattern->n_cols())
1006 {
1007 const auto reduced_row = reduced_accessor.row();
1008 // end of row
1009 if (reduced_accessor.linear_index + 1 ==
1010 reduced_accessor.container->rowstart[reduced_row + 1])
1011 {
1012 ++chunk_row;
1013
1014 chunk_col = 0;
1015
1016 // end of chunk rows or end of matrix
1017 if (chunk_row == chunk_size ||
1018 (reduced_row * chunk_size + chunk_row ==
1019 sparsity_pattern->n_rows()))
1020 {
1021 chunk_row = 0;
1022 reduced_accessor.advance();
1023 }
1024 // go back to the beginning of the same reduced row but with
1025 // chunk_row increased by one
1026 else
1027 reduced_accessor.linear_index =
1028 reduced_accessor.container->rowstart[reduced_row];
1029 }
1030 // advance within chunk
1031 else
1032 {
1033 reduced_accessor.advance();
1034 chunk_col = 0;
1035 }
1036 }
1037 }
1038
1039
1040
1041 inline Iterator::Iterator(const ChunkSparsityPattern *sparsity_pattern,
1042 const size_type row)
1043 : accessor(sparsity_pattern, row)
1044 {}
1045
1046
1047
1048 inline Iterator &
1049 Iterator::operator++()
1050 {
1051 accessor.advance();
1052 return *this;
1053 }
1054
1055
1056
1057 inline Iterator
1058 Iterator::operator++(int)
1059 {
1060 const Iterator iter = *this;
1061 accessor.advance();
1062 return iter;
1063 }
1064
1065
1066
1067 inline const Accessor &
1068 Iterator::operator*() const
1069 {
1070 return accessor;
1071 }
1072
1073
1074
1075 inline const Accessor *
1076 Iterator::operator->() const
1077 {
1078 return &accessor;
1079 }
1080
1081
1082 inline bool
1083 Iterator::operator==(const Iterator &other) const
1084 {
1085 return (accessor == other.accessor);
1086 }
1087
1088
1089
1090 inline bool
1091 Iterator::operator!=(const Iterator &other) const
1092 {
1093 return !(accessor == other.accessor);
1094 }
1095
1096
1097 inline bool
1098 Iterator::operator<(const Iterator &other) const
1099 {
1100 return accessor < other.accessor;
1101 }
1102
1103 } // namespace ChunkSparsityPatternIterators
1104
1105
1106
1107 inline ChunkSparsityPattern::iterator
1108 ChunkSparsityPattern::begin() const
1109 {
1110 return {this, 0};
1111 }
1112
1113
1114 inline ChunkSparsityPattern::iterator
1115 ChunkSparsityPattern::end() const
1116 {
1117 return {this, n_rows()};
1118 }
1119
1120
1121
1122 inline ChunkSparsityPattern::iterator
1123 ChunkSparsityPattern::begin(const size_type r) const
1124 {
1125 AssertIndexRange(r, n_rows());
1126 return {this, r};
1127 }
1128
1129
1130
1131 inline ChunkSparsityPattern::iterator
1132 ChunkSparsityPattern::end(const size_type r) const
1133 {
1134 AssertIndexRange(r, n_rows());
1135 return {this, r + 1};
1136 }
1137
1138
1139
1140 inline ChunkSparsityPattern::size_type
1141 ChunkSparsityPattern::n_rows() const
1142 {
1143 return rows;
1144 }
1145
1146
1147 inline ChunkSparsityPattern::size_type
1148 ChunkSparsityPattern::n_cols() const
1149 {
1150 return cols;
1151 }
1152
1153
1154
1155 inline ChunkSparsityPattern::size_type
1156 ChunkSparsityPattern::get_chunk_size() const
1157 {
1158 return chunk_size;
1159 }
1160
1161
1162
1163 inline bool
1164 ChunkSparsityPattern::is_compressed() const
1165 {
1166 return sparsity_pattern.compressed;
1167 }
1168
1169
1170
1171 template <typename ForwardIterator>
1172 void
1173 ChunkSparsityPattern::copy_from(const size_type n_rows,
1174 const size_type n_cols,
1175 const ForwardIterator begin,
1176 const ForwardIterator end,
1177 const size_type chunk_size)
1178 {
1179 Assert(static_cast<size_type>(std::distance(begin, end)) == n_rows,
1180 ExcIteratorRange(std::distance(begin, end), n_rows));
1181
1182 // first determine row lengths for each row. if the matrix is quadratic,
1183 // then we might have to add an additional entry for the diagonal, if that
1184 // is not yet present. as we have to call compress anyway later on, don't
1185 // bother to check whether that diagonal entry is in a certain row or not
1186 const bool is_square = (n_rows == n_cols);
1187 std::vector<size_type> row_lengths;
1188 row_lengths.reserve(n_rows);
1189 for (ForwardIterator i = begin; i != end; ++i)
1190 row_lengths.push_back(std::distance(i->begin(), i->end()) +
1191 (is_square ? 1 : 0));
1192 reinit(n_rows, n_cols, row_lengths, chunk_size);
1193
1194 // now enter all the elements into the matrix
1195 size_type row = 0;
1196 using inner_iterator =
1197 typename std::iterator_traits<ForwardIterator>::value_type::const_iterator;
1198 for (ForwardIterator i = begin; i != end; ++i, ++row)
1199 {
1200 const inner_iterator end_of_row = i->end();
1201 for (inner_iterator j = i->begin(); j != end_of_row; ++j)
1202 {
1203 const size_type col =
1204 internal::SparsityPatternTools::get_column_index_from_iterator(*j);
1205 Assert(col < n_cols, ExcInvalidIndex(col, n_cols));
1206
1207 add(row, col);
1208 }
1209 }
1210
1211 // finally compress everything. this also sorts the entries within each row
1212 compress();
1213 }
1214
1215
1216 #endif // DOXYGEN
1217
1218 DEAL_II_NAMESPACE_CLOSE
1219
1220 #endif