From 02ed7aca6ea07e5ca7d0d42bab564ba3fee1e758 Mon Sep 17 00:00:00 2001 From: Martin Kronbichler Date: Wed, 31 Aug 2016 15:40:00 +0200 Subject: [PATCH] Fix bad complexity in copy of sparsity pattern. --- doc/news/changes.h | 16 +++++++++---- source/lac/sparsity_pattern.cc | 41 +++++++++++++++++++++++++++++++++- 2 files changed, 52 insertions(+), 5 deletions(-) diff --git a/doc/news/changes.h b/doc/news/changes.h index 690883db30..cfef367ed0 100644 --- a/doc/news/changes.h +++ b/doc/news/changes.h @@ -236,15 +236,15 @@ inconvenience this causes.
  • New: Added a new PolarManifold descriptor, that uses a polar coordinate - system to compute new points, and modified the existing SphericalManifold - descriptor to use geodesics on the surface of the sphere. + system to compute new points, and modified the existing SphericalManifold + descriptor to use geodesics on the surface of the sphere.
    (Luca Heltai, Mauro Bardelloni, 2016/08/04)
  • - New: Added Python bindings to generate and manipulate a Triangulation from - Python. The Triangulation generated in Python can be saved and later, loaded + New: Added Python bindings to generate and manipulate a Triangulation from + Python. The Triangulation generated in Python can be saved and later, loaded inside a C++ code.
    (Bruno Turcksin, 2016/08/03) @@ -495,6 +495,14 @@ inconvenience this causes.

    Specific improvements

      +
    1. Improved: SparsityPattern::copy_from() copying from a + DynamicSparsityPattern argument had quadratic complexity in the number of + rows for sparsity patterns where most of the rows are of length zero. The bad + algorithm has been replaced by a linear complexity one. +
      + (Dustin Kumor, Martin Kronbichler, 2016/08/31) +
    2. +
    3. New: Rank-4 symmetric tensors of type SymmetricTensor can now be converted to rank-4 tensors of type Tensor.
      diff --git a/source/lac/sparsity_pattern.cc b/source/lac/sparsity_pattern.cc index 501b4878ed..80fe41db7b 100644 --- a/source/lac/sparsity_pattern.cc +++ b/source/lac/sparsity_pattern.cc @@ -523,6 +523,46 @@ SparsityPattern::copy_from (const SparsityPatternType &dsp) +// Use a special implementation for DynamicSparsityPattern where we can use +// the column_number method to gain faster access to the +// entries. DynamicSparsityPattern::iterator can show quadratic complexity in +// case many rows are empty and the begin() method needs to jump to the next +// free row. Otherwise, the code is exactly the same as above. +template <> +void +SparsityPattern::copy_from (const DynamicSparsityPattern &dsp) +{ + const bool do_diag_optimize = (dsp.n_rows() == dsp.n_cols()); + std::vector row_lengths (dsp.n_rows()); + for (size_type i=0; i void SparsityPattern::copy_from (const FullMatrix &matrix) { @@ -998,7 +1038,6 @@ SparsityPattern::memory_consumption () const // explicit instantiations template void SparsityPattern::copy_from (const SparsityPattern &); -template void SparsityPattern::copy_from (const DynamicSparsityPattern &); template void SparsityPattern::copy_from (const FullMatrix &); template void SparsityPattern::copy_from (const FullMatrix &); -- 2.39.5