From 47c8a36dccb17699ca5887c65a8e455515ca228c Mon Sep 17 00:00:00 2001 From: kronbichler Date: Fri, 3 Apr 2009 13:04:41 +0000 Subject: [PATCH] Use a smarter algorithm for inserting a list of sorted elements into a CompressedSimpleSP. git-svn-id: https://svn.dealii.org/trunk@18547 0785d39b-7218-0410-832d-ea1e28bc413d --- deal.II/lac/include/lac/block_vector.h | 11 --- .../lac/include/lac/block_vector.templates.h | 12 ++++ .../lac/compressed_simple_sparsity_pattern.h | 72 +++++++++++++++++-- .../include/lac/constraint_matrix.templates.h | 6 +- .../lac/trilinos_block_sparse_matrix.h | 2 +- .../lac/include/lac/trilinos_precondition.h | 6 +- .../include/lac/trilinos_precondition_block.h | 5 +- .../lac/include/lac/trilinos_sparse_matrix.h | 3 +- .../source/trilinos_block_sparse_matrix.cc | 1 + deal.II/lac/source/trilinos_precondition.cc | 2 + .../lac/source/trilinos_precondition_block.cc | 3 + deal.II/lac/source/trilinos_sparse_matrix.cc | 1 + 12 files changed, 98 insertions(+), 26 deletions(-) diff --git a/deal.II/lac/include/lac/block_vector.h b/deal.II/lac/include/lac/block_vector.h index 77bd88e14d..29eb14f25f 100644 --- a/deal.II/lac/include/lac/block_vector.h +++ b/deal.II/lac/include/lac/block_vector.h @@ -19,7 +19,6 @@ #include #include #include -#include #include #include @@ -503,16 +502,6 @@ BlockVector::operator = (const BlockVector &v) } -#ifdef DEAL_II_USE_TRILINOS -template -inline -BlockVector & -BlockVector::operator = (const TrilinosWrappers::BlockVector &v) -{ - BaseClass::operator = (v); - return *this; -} -#endif template void BlockVector::scale (const value_type factor) diff --git a/deal.II/lac/include/lac/block_vector.templates.h b/deal.II/lac/include/lac/block_vector.templates.h index 0a6e1e8b78..c5c7ae89c6 100644 --- a/deal.II/lac/include/lac/block_vector.templates.h +++ b/deal.II/lac/include/lac/block_vector.templates.h @@ -16,6 +16,7 @@ #include #include +#include #include #include @@ -122,6 +123,17 @@ BlockVector::~BlockVector () {} +#ifdef DEAL_II_USE_TRILINOS +template +inline +BlockVector & +BlockVector::operator = (const TrilinosWrappers::BlockVector &v) +{ + BaseClass::operator = (v); + return *this; +} +#endif + template void BlockVector::swap (BlockVector &v) diff --git a/deal.II/lac/include/lac/compressed_simple_sparsity_pattern.h b/deal.II/lac/include/lac/compressed_simple_sparsity_pattern.h index fb8f716127..0d25f1dddc 100644 --- a/deal.II/lac/include/lac/compressed_simple_sparsity_pattern.h +++ b/deal.II/lac/include/lac/compressed_simple_sparsity_pattern.h @@ -20,6 +20,7 @@ #include #include +#include DEAL_II_NAMESPACE_OPEN @@ -366,7 +367,8 @@ class CompressedSimpleSparsityPattern : public Subscriptor */ template void add_entries (ForwardIterator begin, - ForwardIterator end); + ForwardIterator end, + const bool indices_are_sorted); }; @@ -417,18 +419,74 @@ template inline void CompressedSimpleSparsityPattern::Line::add_entries (ForwardIterator begin, - ForwardIterator end) + ForwardIterator end, + const bool indices_are_sorted) { - if (end - begin <= 0) + const int n_elements = end - begin; + if (n_elements <= 0) return; + const unsigned int n_cols = static_cast(n_elements); + const unsigned int stop_size = entries.size() + n_cols; + + if (indices_are_sorted == true && n_elements > 3) + { + if (entries.size() == 0 || entries.back() < *begin) + { + entries.insert(entries.end(), begin, end); + return; + } + + // resize vector by just inserting the + // list + const unsigned int col = *begin; + std::vector::iterator it = + std::lower_bound(entries.begin(), entries.end(), col); + const unsigned int pos1 = it - entries.begin(); + entries.insert (it, begin, end); + it = entries.begin() + pos1; + + // now merge the two lists. + ForwardIterator my_it = begin; + std::vector::iterator it2 = it + n_cols; + + // as long as there are indices both in + // the end of the entries list and in the + // input list + while (my_it != end && it2 != entries.end()) + { + if (*my_it < *it2) + *it++ = *my_it++; + else if (*my_it == *it2) + { + *it++ = *it2++; + ++my_it; + } + else + *it++ = *it2++; + } + // in case there are indices left in the + // input list + while (my_it != end) + *it++ = *my_it++; + + // in case there are indices left in the + // end of entries + while (it2 != entries.end()) + *it++ = *it2++; + + // resize + const unsigned int new_size = it - entries.begin(); + Assert (new_size <= stop_size, ExcInternalError()); + entries.resize (new_size); + return; + } + ForwardIterator my_it = begin; - const unsigned int n_cols = static_cast(end - begin); // If necessary, increase the size of the array. In order to avoid // allocating just a few entries every time, use five elements at a time // at least. - const unsigned int stop_size = entries.size() + (n_cols > 5 ? n_cols : 5); if (stop_size > entries.capacity()) entries.reserve (stop_size); @@ -521,11 +579,11 @@ void CompressedSimpleSparsityPattern::add_entries (const unsigned int row, ForwardIterator begin, ForwardIterator end, - const bool /*indices_are_sorted*/) + const bool indices_are_sorted) { Assert (row < rows, ExcIndexRange (row, 0, rows)); - lines[row].add_entries (begin, end); + lines[row].add_entries (begin, end, indices_are_sorted); } diff --git a/deal.II/lac/include/lac/constraint_matrix.templates.h b/deal.II/lac/include/lac/constraint_matrix.templates.h index 56de0b588b..307417bac8 100644 --- a/deal.II/lac/include/lac/constraint_matrix.templates.h +++ b/deal.II/lac/include/lac/constraint_matrix.templates.h @@ -2006,7 +2006,8 @@ add_entries_local_to_global (const std::vector &local_dof_indices, // into the vector Threads::ThreadMutex::ScopedLock lock(mutex); if (col_counter > 0) - sparsity_pattern.add_entries(row, cols.begin(), cols.begin()+col_counter); + sparsity_pattern.add_entries(row, cols.begin(), cols.begin()+col_counter, + true); } } @@ -2337,7 +2338,8 @@ add_entries_local_to_global (const std::vector &local_dof_indices, if (current_length > 0) sparsity_pattern.block(row_block.first, i).add_entries(row_block.second, cols.begin()+col_begins, - cols.begin()+col_begins+current_length); + cols.begin()+col_begins+current_length, + true); col_begins = actual_block_ends[i]; } } diff --git a/deal.II/lac/include/lac/trilinos_block_sparse_matrix.h b/deal.II/lac/include/lac/trilinos_block_sparse_matrix.h index 973a204fea..c03cf2ab77 100644 --- a/deal.II/lac/include/lac/trilinos_block_sparse_matrix.h +++ b/deal.II/lac/include/lac/trilinos_block_sparse_matrix.h @@ -17,7 +17,6 @@ #include #include #include -#include #include #include #include @@ -37,6 +36,7 @@ class BlockSparsityPattern; class BlockCompressedSparsityPattern; class BlockCompressedSetSparsityPattern; class BlockCompressedSimpleSparsityPattern; +template class BlockSparseMatrix; namespace TrilinosWrappers diff --git a/deal.II/lac/include/lac/trilinos_precondition.h b/deal.II/lac/include/lac/trilinos_precondition.h index a9f2cc93cb..791f59ce66 100755 --- a/deal.II/lac/include/lac/trilinos_precondition.h +++ b/deal.II/lac/include/lac/trilinos_precondition.h @@ -16,8 +16,6 @@ #include #include -#include -#include #include @@ -45,6 +43,10 @@ namespace ML_Epetra DEAL_II_NAMESPACE_OPEN +// forward declarations +template class SparseMatrix; +template class Vector; + /*! @addtogroup TrilinosWrappers *@{ */ diff --git a/deal.II/lac/include/lac/trilinos_precondition_block.h b/deal.II/lac/include/lac/trilinos_precondition_block.h index 7615f9c594..69d40311c1 100644 --- a/deal.II/lac/include/lac/trilinos_precondition_block.h +++ b/deal.II/lac/include/lac/trilinos_precondition_block.h @@ -16,9 +16,8 @@ #include #include -#include -#include #include +#include #ifdef DEAL_II_USE_TRILINOS @@ -39,6 +38,8 @@ DEAL_II_NAMESPACE_OPEN namespace TrilinosWrappers { + // forward declarations + class BlockSparseMatrix; /** * This implements an interface class of preconditioners for block diff --git a/deal.II/lac/include/lac/trilinos_sparse_matrix.h b/deal.II/lac/include/lac/trilinos_sparse_matrix.h index 452f6f6aed..3873c70b4d 100755 --- a/deal.II/lac/include/lac/trilinos_sparse_matrix.h +++ b/deal.II/lac/include/lac/trilinos_sparse_matrix.h @@ -16,7 +16,6 @@ #include #include -#include #include #include #include @@ -41,6 +40,8 @@ DEAL_II_NAMESPACE_OPEN +// forward declaration +template class SparseMatrix; namespace TrilinosWrappers { diff --git a/deal.II/lac/source/trilinos_block_sparse_matrix.cc b/deal.II/lac/source/trilinos_block_sparse_matrix.cc index 7778b00db5..46469bd6fe 100644 --- a/deal.II/lac/source/trilinos_block_sparse_matrix.cc +++ b/deal.II/lac/source/trilinos_block_sparse_matrix.cc @@ -13,6 +13,7 @@ #include +#include #include #ifdef DEAL_II_USE_TRILINOS diff --git a/deal.II/lac/source/trilinos_precondition.cc b/deal.II/lac/source/trilinos_precondition.cc index 5019b3fc8c..7db151a005 100755 --- a/deal.II/lac/source/trilinos_precondition.cc +++ b/deal.II/lac/source/trilinos_precondition.cc @@ -12,6 +12,8 @@ //--------------------------------------------------------------------------- +#include +#include #include #include #include diff --git a/deal.II/lac/source/trilinos_precondition_block.cc b/deal.II/lac/source/trilinos_precondition_block.cc index e313aa660d..c3700b545e 100755 --- a/deal.II/lac/source/trilinos_precondition_block.cc +++ b/deal.II/lac/source/trilinos_precondition_block.cc @@ -13,6 +13,9 @@ #include +#include +#include + #ifdef DEAL_II_USE_TRILINOS #include diff --git a/deal.II/lac/source/trilinos_sparse_matrix.cc b/deal.II/lac/source/trilinos_sparse_matrix.cc index 7cde3d2772..4aa9ea3dce 100755 --- a/deal.II/lac/source/trilinos_sparse_matrix.cc +++ b/deal.II/lac/source/trilinos_sparse_matrix.cc @@ -13,6 +13,7 @@ #include +#include #include #include #include -- 2.39.5