16 #ifndef dealii__sparsity_pattern_h 17 #define dealii__sparsity_pattern_h 20 #include <deal.II/base/config.h> 21 #include <deal.II/base/exceptions.h> 22 #include <deal.II/base/subscriptor.h> 26 #include <boost/version.hpp> 27 #if BOOST_VERSION >= 106400 28 # include <boost/serialization/array_wrapper.hpp> 30 # include <boost/serialization/array.hpp> 32 #include <boost/serialization/split_member.hpp> 38 DEAL_II_NAMESPACE_OPEN
45 template <
typename number>
class SparseILU;
60 namespace SparsityPatternTools
73 get_column_index_from_iterator (
const size_type i);
80 template <
typename value>
82 get_column_index_from_iterator (
const std::pair<size_type, value> &i);
89 template <
typename value>
91 get_column_index_from_iterator (
const std::pair<const size_type, value> &i);
130 const std::size_t index_within_sparsity);
141 size_type row ()
const;
148 size_type index ()
const;
154 size_type column ()
const;
165 bool is_valid_entry ()
const;
170 bool operator == (
const Accessor &)
const;
179 bool operator < (
const Accessor &)
const;
247 const std::size_t index_within_sparsity);
267 const Accessor *operator-> ()
const;
272 bool operator == (
const Iterator &)
const;
277 bool operator != (
const Iterator &)
const;
286 bool operator < (
const Iterator &)
const;
294 int operator - (
const Iterator &p)
const;
422 const unsigned int max_per_row);
435 const std::vector<unsigned int> &row_lengths);
446 const unsigned int max_per_row);
456 const std::vector<unsigned int> &row_lengths);
481 const unsigned int max_per_row,
482 const size_type extra_off_diagonals);
504 void reinit (
const size_type m,
506 const unsigned int max_per_row);
523 void reinit (
const size_type m,
525 const std::vector<unsigned int> &row_lengths);
531 void reinit (
const size_type m,
533 const VectorSlice<
const std::vector<unsigned int> > &row_lengths);
626 template <
typename ForwardIterator>
627 void copy_from (
const size_type n_rows,
628 const size_type n_cols,
629 const ForwardIterator begin,
630 const ForwardIterator end);
639 template <
typename SparsityPatternType>
640 void copy_from (
const SparsityPatternType &dsp);
650 template <
typename number>
668 void add (
const size_type i,
677 template <
typename ForwardIterator>
678 void add_entries (
const size_type row,
679 ForwardIterator begin,
681 const bool indices_are_sorted =
false);
719 iterator begin (
const size_type r)
const;
729 iterator end (
const size_type r)
const;
753 size_type max_entries_per_row ()
const;
764 size_type bandwidth ()
const;
774 std::size_t n_nonzero_elements ()
const;
779 bool is_compressed ()
const;
785 size_type n_rows ()
const;
791 size_type n_cols ()
const;
796 unsigned int row_length (
const size_type row)
const;
810 bool stores_only_added_elements ()
const;
816 std::size_t memory_consumption ()
const;
845 size_type operator() (
const size_type i,
846 const size_type j)
const;
859 std::pair<size_type, size_type>
860 matrix_position (
const std::size_t global_index)
const;
865 bool exists (
const size_type i,
866 const size_type j)
const;
875 size_type row_position(
const size_type i,
876 const size_type j)
const;
888 size_type column_number (
const size_type row,
889 const unsigned int index)
const;
907 void block_write (std::ostream &out)
const;
922 void block_read (std::istream &in);
929 void print (std::ostream &out)
const;
944 void print_gnuplot (std::ostream &out)
const;
953 void print_svg (std::ostream &out)
const;
960 template <
class Archive>
961 void save (Archive &ar,
const unsigned int version)
const;
967 template <
class Archive>
968 void load (Archive &ar,
const unsigned int version);
970 BOOST_SERIALIZATION_SPLIT_MEMBER()
983 << "Upon entering a new entry to row " << arg1
984 << ": there was no free entry any more. " <<
std::endl
985 << "(Maximum number of entries for this row: "
986 << arg2 << "; maybe the matrix is already compressed?)");
992 "The operation you attempted is only allowed after the
SparsityPattern "
993 "has been set up and compress() was called.");
999 "The operation you attempted changes the structure of the
SparsityPattern "
1000 "and is not possible after compress() has been called.");
1006 << "The iterators denote a range of " << arg1
1007 << " elements, but the given number of rows was " << arg2);
1013 << "The number of partitions you gave is " << arg1
1014 << ", but must be greater than zero.");
1050 unsigned int max_row_length;
1099 bool store_diagonal_first_in_row;
1106 template <typename number> friend class
SparseILU;
1131 const std::size_t i)
1133 sparsity_pattern(sparsity_pattern),
1134 index_within_sparsity(i)
1142 sparsity_pattern(sparsity_pattern),
1143 index_within_sparsity(sparsity_pattern->
rowstart[sparsity_pattern->
rows])
1151 return (index_within_sparsity < sparsity_pattern->rowstart[sparsity_pattern->
rows]
1153 sparsity_pattern->
colnums[index_within_sparsity]
1164 const std::size_t *insert_point =
1165 std::upper_bound(sparsity_pattern->
rowstart,
1166 sparsity_pattern->
rowstart + sparsity_pattern->
rows + 1,
1167 index_within_sparsity);
1168 return insert_point - sparsity_pattern->
rowstart - 1;
1178 return (sparsity_pattern->
colnums[index_within_sparsity]);
1184 Accessor::index()
const 1188 return index_within_sparsity - sparsity_pattern->
rowstart[row()];
1198 return (sparsity_pattern == other.sparsity_pattern &&
1199 index_within_sparsity == other.index_within_sparsity);
1208 Assert (sparsity_pattern == other.sparsity_pattern,
1211 return index_within_sparsity < other.index_within_sparsity;
1219 Assert (index_within_sparsity < sparsity_pattern->rowstart[sparsity_pattern->
rows],
1221 ++index_within_sparsity;
1228 const std::size_t i)
1230 accessor(sparsity_pattern, i)
1239 accessor.advance ();
1249 const Iterator iter = *
this;
1250 accessor.advance ();
1277 return (accessor == other.accessor);
1286 return ! (*
this == other);
1294 return accessor < other.accessor;
1300 Iterator::operator - (
const Iterator &other)
const 1302 Assert (accessor.sparsity_pattern == other.accessor.sparsity_pattern,
1305 return (*this)->index_within_sparsity - other->index_within_sparsity;
1315 return iterator(
this, rowstart[0]);
1323 return iterator(
this, rowstart[rows]);
1332 Assert (r<n_rows(), ExcIndexRangeType<size_type>(r,0,n_rows()));
1334 return iterator(
this, rowstart[r]);
1343 Assert (r<n_rows(), ExcIndexRangeType<size_type>(r,0,n_rows()));
1345 return iterator(
this, rowstart[r+1]);
1378 return (store_diagonal_first_in_row ==
false);
1387 Assert(row<rows, ExcIndexRangeType<size_type>(row,0,rows));
1388 return rowstart[row+1]-rowstart[row];
1396 const unsigned int index)
const 1398 Assert(row<rows, ExcIndexRangeType<size_type>(row,0,rows));
1401 return colnums[rowstart[row]+index];
1410 Assert (compressed, ExcNotCompressed());
1411 return rowstart[rows]-rowstart[0];
1416 template <
class Archive>
1424 ar &max_dim &rows &cols &max_vec_len &max_row_length &compressed &store_diagonal_first_in_row;
1426 ar &boost::serialization::make_array(rowstart, max_dim + 1);
1427 ar &boost::serialization::make_array(colnums, max_vec_len);
1432 template <
class Archive>
1440 ar &max_dim &rows &cols &max_vec_len &max_row_length &compressed &store_diagonal_first_in_row;
1444 rowstart =
new std::size_t[max_dim + 1];
1448 colnums =
new size_type[max_vec_len];
1450 ar &boost::serialization::make_array(rowstart, max_dim + 1);
1451 ar &boost::serialization::make_array(colnums, max_vec_len);
1464 if (rows != sp2.
rows ||
1470 for (size_type i = 0; i < rows+1; ++i)
1471 if (rowstart[i] != sp2.
rowstart[i])
1474 for (size_type i = 0; i < rowstart[rows]; ++i)
1475 if (colnums[i] != sp2.
colnums[i])
1485 namespace SparsityPatternTools
1494 get_column_index_from_iterator (
const size_type i)
1501 template <
typename value>
1504 get_column_index_from_iterator (
const std::pair<size_type, value> &i)
1511 template <
typename value>
1514 get_column_index_from_iterator (
const std::pair<const size_type, value> &i)
1523 template <
typename ForwardIterator>
1526 const size_type n_cols,
1527 const ForwardIterator begin,
1528 const ForwardIterator end)
1530 Assert (static_cast<size_type>(std::distance (begin, end)) == n_rows,
1531 ExcIteratorRange (std::distance (begin, end), n_rows));
1537 const bool is_square = (n_rows == n_cols);
1538 std::vector<unsigned int> row_lengths;
1539 row_lengths.reserve(n_rows);
1540 for (ForwardIterator i=begin; i!=end; ++i)
1541 row_lengths.push_back (std::distance (i->begin(), i->end())
1543 (is_square ? 1 : 0));
1544 reinit (n_rows, n_cols, row_lengths);
1552 typedef typename std::iterator_traits<ForwardIterator>::value_type::const_iterator inner_iterator;
1553 for (ForwardIterator i=begin; i!=end; ++i, ++row)
1555 size_type *cols = &colnums[rowstart[row]] + (is_square ? 1 : 0);
1556 const inner_iterator end_of_row = i->end();
1557 for (inner_iterator j=i->begin(); j!=end_of_row; ++j)
1560 = internal::SparsityPatternTools::get_column_index_from_iterator(*j);
1563 if ((col!=row) || !is_square)
1575 DEAL_II_NAMESPACE_CLOSE
types::global_dof_index size_type
const types::global_dof_index invalid_size_type
SparsityPatternIterators::Iterator iterator
std::size_t index_within_sparsity
#define DeclException2(Exception2, type1, type2, outsequence)
Iterator(const ChunkSparsityPattern *sp, const unsigned int row)
types::global_dof_index size_type
static const size_type invalid_entry
void save(Archive &ar, const unsigned int version) const
bool operator==(const Accessor &) const
const Accessor * operator->() const
static::ExceptionBase & ExcIndexRange(int arg1, int arg2, int arg3)
static::ExceptionBase & ExcInvalidIterator()
static::ExceptionBase & ExcInvalidNumberOfPartitions(int arg1)
#define DeclException1(Exception1, type1, outsequence)
unsigned int global_dof_index
#define Assert(cond, exc)
bool operator<(const Accessor &) const
#define DeclExceptionMsg(Exception, defaulttext)
unsigned int row_length(const size_type row) const
size_type column_number(const size_type row, const unsigned int index) const
bool stores_only_added_elements() const
void load(Archive &ar, const unsigned int version)
void copy_from(const size_type n_rows, const size_type n_cols, const ForwardIterator begin, const ForwardIterator end)
bool operator<(const Iterator &) const
SparsityPatternIterators::Iterator const_iterator
static::ExceptionBase & ExcIteratorPastEnd()
Accessor(const ChunkSparsityPattern *matrix, const unsigned int row)
types::global_dof_index size_type
bool operator==(const Iterator &) const
bool store_diagonal_first_in_row
const SparsityPattern * sparsity_pattern
static::ExceptionBase & ExcEmptyObject()
bool operator==(const SparsityPattern &) const
bool is_valid_entry() const
bool operator!=(const Iterator &) const
bool is_compressed() const
std::size_t n_nonzero_elements() const
const Accessor & operator*() const
unsigned int column() const
static::ExceptionBase & ExcInternalError()