From ceb95444570d0bb019d58b5ad73ed319699f257b Mon Sep 17 00:00:00 2001 From: Timo Heister Date: Sun, 8 Mar 2015 11:08:31 -0400 Subject: [PATCH] Rework Compressed*SparsityPattern - rename CompressedSimpleSparsityPattern to DynamicSparsityPattern - deprecate all Compressed*SparsityPattern classes - same for BlockCompressed*SparsityPattern - update examples - replace non-dynamic sparsity creation in step-7, 8, 9, 13, 14, 16, 23, 24, 25, 28, 29, 35 Motivation for removing the other compressed objects: Number of degrees of freedom: 274625 FE_Q<3>(4) CompressedSimple vmpeak: 749024 rss: 530804 make: 5.99s copy: 3.58s Compressed vmpeak: 744880 rss: 526852 make: 8.59s copy: 3.64s CompressedSet vmpeak: 3184880 rss: 2966776 make: 92s copy: 18s Or in Martin's words: I remember having looked into compute times for the DoFTools::make_sparsity_pattern in detail some five years ago and all benchmarks showed CompressedSimpleSparsityPattern as the fastest of the three. The internal data structure in CSimpleSP is std::vector, thus simpler than plain CSP where there is an additional array of length 8 with 'fresh' entries about to be submitted but otherwise very similar. std::set as used in CSetSP does way too many memory allocations and is most likely slower than inserting into a sorted vector for almost all imaginable loads with up to a few hundred entries. In particular for how we mostly use sparsity patterns where each row gets touched as many times as we have adjacent elements to that DoF. Last but not least, CSimpleSP is the only one with the appropriate infrastructure for parallel distributed computations where rows use an additional IndexSet argument. --- cmake/config/template-arguments.in | 8 +- .../compressed_block_sparsity_pattern.cc | 6 +- examples/step-11/step-11.cc | 12 +- examples/step-12/step-12.cc | 6 +- examples/step-13/step-13.cc | 17 +- examples/step-14/step-14.cc | 21 +- examples/step-15/step-15.cc | 4 +- examples/step-16/step-16.cc | 15 +- examples/step-18/step-18.cc | 10 +- examples/step-2/step-2.cc | 14 +- examples/step-20/step-20.cc | 6 +- examples/step-22/step-22.cc | 25 +- examples/step-23/step-23.cc | 9 +- examples/step-24/step-24.cc | 9 +- examples/step-25/step-25.cc | 9 +- examples/step-26/step-26.cc | 4 +- examples/step-27/step-27.cc | 8 +- examples/step-28/step-28.cc | 10 +- examples/step-29/step-29.cc | 10 +- examples/step-3/step-3.cc | 4 +- examples/step-31/step-31.cc | 17 +- examples/step-32/step-32.cc | 2 +- examples/step-33/step-33.cc | 6 +- examples/step-35/step-35.cc | 35 +- examples/step-36/step-36.cc | 2 +- examples/step-38/step-38.cc | 4 +- examples/step-39/step-39.cc | 10 +- examples/step-4/step-4.cc | 4 +- examples/step-40/step-40.cc | 6 +- examples/step-41/step-41.cc | 4 +- examples/step-43/step-43.cc | 17 +- examples/step-44/step-44.cc | 4 +- examples/step-45/step-45.cc | 6 +- examples/step-46/step-46.cc | 4 +- examples/step-47/step-47.cc | 4 +- examples/step-5/step-5.cc | 4 +- examples/step-50/step-50.cc | 7 +- examples/step-51/step-51.cc | 4 +- examples/step-52/step-52.cc | 2 +- examples/step-6/step-6.cc | 8 +- examples/step-7/step-7.cc | 11 +- examples/step-8/step-8.cc | 14 +- examples/step-9/step-9.cc | 16 +- include/deal.II/lac/block_sparsity_pattern.h | 232 +------ .../lac/compressed_set_sparsity_pattern.h | 426 +------------ .../lac/compressed_simple_sparsity_pattern.h | 497 +-------------- .../deal.II/lac/compressed_sparsity_pattern.h | 500 +--------------- include/deal.II/lac/constraint_matrix.h | 58 +- .../deal.II/lac/dynamic_sparsity_pattern.h | 528 ++++++++++++++++ include/deal.II/lac/generic_linear_algebra.h | 2 +- .../lac/petsc_parallel_block_sparse_matrix.h | 4 +- include/deal.II/lac/sparsity_pattern.h | 5 - .../lac/trilinos_block_sparse_matrix.h | 3 - .../deal.II/lac/trilinos_sparsity_pattern.h | 4 +- include/deal.II/matrix_free/dof_info.h | 3 +- .../deal.II/matrix_free/dof_info.templates.h | 22 +- source/lac/CMakeLists.txt | 4 +- source/lac/block_sparsity_pattern.cc | 207 +------ source/lac/chunk_sparsity_pattern.cc | 26 +- source/lac/compressed_set_sparsity_pattern.cc | 245 -------- source/lac/compressed_sparsity_pattern.cc | 565 ------------------ source/lac/constraint_matrix.cc | 409 +------------ ...pattern.cc => dynamic_sparsity_pattern.cc} | 88 +-- .../lac/petsc_parallel_block_sparse_matrix.cc | 4 +- source/lac/petsc_parallel_sparse_matrix.cc | 33 +- source/lac/petsc_sparse_matrix.cc | 18 +- source/lac/sparsity_pattern.cc | 8 +- source/lac/sparsity_tools.cc | 7 +- source/lac/trilinos_block_sparse_matrix.cc | 19 +- source/lac/trilinos_sparse_matrix.cc | 31 +- source/lac/trilinos_sparsity_pattern.cc | 60 +- tests/lac/sparsity_pattern_common.h | 126 +--- 72 files changed, 885 insertions(+), 3647 deletions(-) create mode 100644 include/deal.II/lac/dynamic_sparsity_pattern.h delete mode 100644 source/lac/compressed_set_sparsity_pattern.cc delete mode 100644 source/lac/compressed_sparsity_pattern.cc rename source/lac/{compressed_simple_sparsity_pattern.cc => dynamic_sparsity_pattern.cc} (80%) diff --git a/cmake/config/template-arguments.in b/cmake/config/template-arguments.in index 7e97a5eea3..e655291ad1 100644 --- a/cmake/config/template-arguments.in +++ b/cmake/config/template-arguments.in @@ -80,15 +80,11 @@ FEVALUES_BASES := { FEValuesBase; FEFaceValuesBase } SPARSITY_PATTERNS := { SparsityPattern; - CompressedSparsityPattern; - CompressedSetSparsityPattern; - CompressedSimpleSparsityPattern; + DynamicSparsityPattern; @DEAL_II_EXPAND_TRILINOS_SPARSITY_PATTERN@; BlockSparsityPattern; - BlockCompressedSparsityPattern; - BlockCompressedSetSparsityPattern; - BlockCompressedSimpleSparsityPattern; + BlockDynamicSparsityPattern; @DEAL_II_EXPAND_TRILINOS_BLOCK_SPARSITY_PATTERN@; } DIMENSIONS := { 1; 2; 3 } diff --git a/examples/doxygen/compressed_block_sparsity_pattern.cc b/examples/doxygen/compressed_block_sparsity_pattern.cc index c8f6eb556c..7ade2ed7fb 100644 --- a/examples/doxygen/compressed_block_sparsity_pattern.cc +++ b/examples/doxygen/compressed_block_sparsity_pattern.cc @@ -1,6 +1,6 @@ // --------------------------------------------------------------------- // -// Copyright (C) 2006 - 2014 by the deal.II authors +// Copyright (C) 2006 - 2015 by the deal.II authors // // This file is part of the deal.II library. // @@ -14,7 +14,7 @@ // --------------------------------------------------------------------- -// See documentation of BlockCompressedSparsityPattern for documentation of this example +// See documentation of BlockDynamicSparsityPattern for documentation of this example #include #include @@ -55,7 +55,7 @@ int main() std::vector dofs_per_block(fe.n_blocks()); DoFTools::count_dofs_per_block(dof, dofs_per_block); - BlockCompressedSparsityPattern c_sparsity(fe.n_blocks(), fe.n_blocks()); + BlockDynamicSparsityPattern c_sparsity(fe.n_blocks(), fe.n_blocks()); for (unsigned int i=0; i // Just this one is new: it declares a class -// CompressedSparsityPattern, which we will use and explain +// DynamicSparsityPattern, which we will use and explain // further down below. -#include +#include // We will make use of the std::find algorithm of the C++ standard library, so // we have to include the following file for its declaration: @@ -202,7 +202,7 @@ namespace Step11 // // Since this can be so difficult that no reasonable answer can be given // that allows allocation of only a reasonable amount of memory, there is - // a class CompressedSparsityPattern, that can help us out + // a class DynamicSparsityPattern, that can help us out // here. It does not require that we know in advance how many entries rows // could have, but allows just about any length. It is thus significantly // more flexible in case you do not have good estimates of row lengths, @@ -215,15 +215,15 @@ namespace Step11 // pattern due to the differential operator, then condense it with the // constraints object which adds those positions in the sparsity pattern // that are required for the elimination of the constraint. - CompressedSparsityPattern csp (dof_handler.n_dofs(), - dof_handler.n_dofs()); + DynamicSparsityPattern csp (dof_handler.n_dofs(), + dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, csp); mean_value_constraints.condense (csp); // Finally, once we have the full pattern, we can initialize an object of // type SparsityPattern from it and in turn initialize the // matrix with it. Note that this is actually necessary, since the - // CompressedSparsityPattern is so inefficient compared to + // DynamicSparsityPattern is so inefficient compared to // the SparsityPattern class due to the more flexible data // structures it has to use, that we can impossibly base the sparse matrix // class on it, but rather need an object of type diff --git a/examples/step-12/step-12.cc b/examples/step-12/step-12.cc index 6c79a26074..5800662b3c 100644 --- a/examples/step-12/step-12.cc +++ b/examples/step-12/step-12.cc @@ -23,7 +23,7 @@ #include #include #include -#include +#include #include #include #include @@ -215,14 +215,14 @@ namespace Step12 dof_handler.distribute_dofs (fe); // We start by generating the sparsity pattern. To this end, we first fill - // an intermediate object of type CompressedSparsityPattern with the + // an intermediate object of type DynamicSparsityPattern with the // couplings appearing in the system. After building the pattern, this // object is copied to sparsity_pattern and can be discarded. // To build the sparsity pattern for DG discretizations, we can call the // function analogue to DoFTools::make_sparsity_pattern, which is called // DoFTools::make_flux_sparsity_pattern: - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_flux_sparsity_pattern (dof_handler, c_sparsity); sparsity_pattern.copy_from(c_sparsity); diff --git a/examples/step-13/step-13.cc b/examples/step-13/step-13.cc index d9de739577..7bc173e742 100644 --- a/examples/step-13/step-13.cc +++ b/examples/step-13/step-13.cc @@ -32,6 +32,7 @@ #include #include #include +#include #include #include #include @@ -1035,20 +1036,20 @@ namespace Step13 Threads::Task<> side_task(std_cxx11::bind(mhnc_p,std_cxx11::cref(dof_handler), std_cxx11::ref(hanging_node_constraints))); - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); + DynamicSparsityPattern csp(dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, csp); + + // Wait for the side task to be done before going further side_task.join(); hanging_node_constraints.close (); - hanging_node_constraints.condense (sparsity_pattern); + hanging_node_constraints.condense (csp); + sparsity_pattern.copy_from(csp); + - // Finally, close the sparsity pattern, initialize the matrix, and set - // the right hand side vector to the right size. - sparsity_pattern.compress(); + // Finally initialize the matrix and right hand side vector matrix.reinit (sparsity_pattern); rhs.reinit (dof_handler.n_dofs()); } diff --git a/examples/step-14/step-14.cc b/examples/step-14/step-14.cc index 42d98fbcb7..061fa9ee0c 100644 --- a/examples/step-14/step-14.cc +++ b/examples/step-14/step-14.cc @@ -27,6 +27,7 @@ #include #include #include +#include #include #include #include @@ -709,22 +710,22 @@ namespace Step14 ConstraintMatrix &) = &DoFTools::make_hanging_node_constraints; - Threads::Task<> side_task - = Threads::new_task (mhnc_p, - dof_handler, - hanging_node_constraints); + // Start a side task then continue on the main thread + Threads::Task<> side_task(std_cxx11::bind(mhnc_p,std_cxx11::cref(dof_handler), + std_cxx11::ref(hanging_node_constraints))); - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); + DynamicSparsityPattern csp(dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, csp); + + + // Wait for the side task to be done before going further side_task.join(); hanging_node_constraints.close (); - hanging_node_constraints.condense (sparsity_pattern); + hanging_node_constraints.condense (csp); + sparsity_pattern.copy_from(csp); - sparsity_pattern.compress(); matrix.reinit (sparsity_pattern); rhs.reinit (dof_handler.n_dofs()); } diff --git a/examples/step-15/step-15.cc b/examples/step-15/step-15.cc index 7682ae4aff..691d7bc761 100644 --- a/examples/step-15/step-15.cc +++ b/examples/step-15/step-15.cc @@ -30,7 +30,7 @@ #include #include #include -#include +#include #include #include #include @@ -208,7 +208,7 @@ namespace Step15 newton_update.reinit (dof_handler.n_dofs()); system_rhs.reinit (dof_handler.n_dofs()); - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, c_sparsity); hanging_node_constraints.condense (c_sparsity); diff --git a/examples/step-16/step-16.cc b/examples/step-16/step-16.cc index f879864ea5..4c4edee95d 100644 --- a/examples/step-16/step-16.cc +++ b/examples/step-16/step-16.cc @@ -277,10 +277,8 @@ namespace Step16 ? ")" : ", "); deallog << std::endl; - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); + DynamicSparsityPattern csp(dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, csp); solution.reinit (dof_handler.n_dofs()); system_rhs.reinit (dof_handler.n_dofs()); @@ -298,8 +296,8 @@ namespace Step16 constraints); constraints.close (); hanging_node_constraints.close (); - constraints.condense (sparsity_pattern); - sparsity_pattern.compress(); + constraints.condense (csp); + sparsity_pattern.copy_from (csp); system_matrix.reinit (sparsity_pattern); // The multigrid constraints have to be initialized. They need to know @@ -345,9 +343,8 @@ namespace Step16 // matrices. for (unsigned int level=0; level #include #include -#include +#include #include #include #include @@ -966,11 +966,11 @@ namespace Step18 // going to work with, and make sure that the condensation of hanging node // constraints add the necessary additional entries in the sparsity // pattern: - CompressedSparsityPattern sparsity_pattern (dof_handler.n_dofs(), - dof_handler.n_dofs()); + DynamicSparsityPattern sparsity_pattern (dof_handler.n_dofs(), + dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); hanging_node_constraints.condense (sparsity_pattern); - // Note that we have used the CompressedSparsityPattern class + // Note that we have used the DynamicSparsityPattern class // here that was already introduced in step-11, rather than the // SparsityPattern class that we have used in all other // cases. The reason for this is that for the latter class to work we have @@ -989,7 +989,7 @@ namespace Step18 // too much memory can lead to out-of-memory situations. // // In order to avoid this, we resort to the - // CompressedSparsityPattern class that is slower but does + // DynamicSparsityPattern class that is slower but does // not require any up-front estimate on the number of nonzero entries per // row. It therefore only ever allocates as much memory as it needs at any // given time, and we can build it even for large 3d problems. diff --git a/examples/step-2/step-2.cc b/examples/step-2/step-2.cc index 9036bbbe35..9702a20f35 100644 --- a/examples/step-2/step-2.cc +++ b/examples/step-2/step-2.cc @@ -48,7 +48,7 @@ #include // We will also need to use an intermediate sparsity pattern structure, which // is found in this file: -#include +#include // We will want to use a special algorithm to renumber degrees of freedom. It // is declared here: @@ -195,15 +195,15 @@ void distribute_dofs (DoFHandler<2> &dof_handler) // number, leading to a lot of wasted memory, sometimes too much for the // machine used, even if the unused memory can be released immediately after // computing the sparsity pattern. In order to avoid this, we use an - // intermediate object of type CompressedSparsityPattern that uses a + // intermediate object of type DynamicSparsityPattern that uses a // different %internal data structure and that we can later copy into the // SparsityPattern object without much overhead. (Some more information on // these data structures can be found in the @ref Sparsity module.) In order // to initialize this intermediate data structure, we have to give it the // size of the matrix, which in our case will be square with as many rows // and columns as there are degrees of freedom on the grid: - CompressedSparsityPattern compressed_sparsity_pattern(dof_handler.n_dofs(), - dof_handler.n_dofs()); + DynamicSparsityPattern compressed_sparsity_pattern(dof_handler.n_dofs(), + dof_handler.n_dofs()); // We then fill this object with the places where nonzero elements will be // located given the present numbering of degrees of freedom: @@ -211,7 +211,7 @@ void distribute_dofs (DoFHandler<2> &dof_handler) // Now we are ready to create the actual sparsity pattern that we could // later use for our matrix. It will just contain the data already assembled - // in the CompressedSparsityPattern. + // in the DynamicSparsityPattern. SparsityPattern sparsity_pattern; sparsity_pattern.copy_from (compressed_sparsity_pattern); @@ -265,8 +265,8 @@ void renumber_dofs (DoFHandler<2> &dof_handler) { DoFRenumbering::Cuthill_McKee (dof_handler); - CompressedSparsityPattern compressed_sparsity_pattern(dof_handler.n_dofs(), - dof_handler.n_dofs()); + DynamicSparsityPattern compressed_sparsity_pattern(dof_handler.n_dofs(), + dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, compressed_sparsity_pattern); SparsityPattern sparsity_pattern; diff --git a/examples/step-20/step-20.cc b/examples/step-20/step-20.cc index 08a76fa2a6..81e9c73a97 100644 --- a/examples/step-20/step-20.cc +++ b/examples/step-20/step-20.cc @@ -358,14 +358,14 @@ namespace Step20 // The next task is to allocate a sparsity pattern for the matrix that we // will create. We use a compressed sparsity pattern like in the previous // steps, but as system_matrix is a block matrix we use the - // class BlockCompressedSparsityPattern instead of just - // CompressedSparsityPattern. This block sparsity pattern has + // class BlockDynamicSparsityPattern instead of just + // DynamicSparsityPattern. This block sparsity pattern has // four blocks in a $2 \times 2$ pattern. The blocks' sizes depend on // n_u and n_p, which hold the number of velocity // and pressure variables. In the second step we have to instruct the block // system to update its knowledge about the sizes of the blocks it manages; // this happens with the c_sparsity.collect_sizes () call. - BlockCompressedSparsityPattern c_sparsity(2, 2); + BlockDynamicSparsityPattern c_sparsity(2, 2); c_sparsity.block(0, 0).reinit (n_u, n_u); c_sparsity.block(1, 0).reinit (n_p, n_u); c_sparsity.block(0, 1).reinit (n_u, n_p); diff --git a/examples/step-22/step-22.cc b/examples/step-22/step-22.cc index ad80976407..ce1458b395 100644 --- a/examples/step-22/step-22.cc +++ b/examples/step-22/step-22.cc @@ -521,32 +521,11 @@ namespace Step22 // BlockSparsityPattern. This is entirely analogous to what we already did // in step-11 and step-18. // - // There is one snag again here, though: it turns out that using the - // CompressedSparsityPattern (or the block version - // BlockCompressedSparsityPattern we would use here) has a bottleneck that - // makes the algorithm to build the sparsity pattern be quadratic in the - // number of degrees of freedom. This doesn't become noticeable until we - // get well into the range of several 100,000 degrees of freedom, but - // eventually dominates the setup of the linear system when we get to more - // than a million degrees of freedom. This is due to the data structures - // used in the CompressedSparsityPattern class, nothing that can easily be - // changed. Fortunately, there is an easy solution: the - // CompressedSimpleSparsityPattern class (and its block variant - // BlockCompressedSimpleSparsityPattern) has exactly the same interface, - // uses a different %internal data structure and is linear in the number - // of degrees of freedom and therefore much more efficient for large - // problems. As another alternative, we could also have chosen the class - // BlockCompressedSetSparsityPattern that uses yet another strategy for - // %internal memory management. Though, that class turns out to be more - // memory-demanding than BlockCompressedSimpleSparsityPattern for this - // example. - // - // Consequently, this is the class that we will use for our intermediate - // sparsity representation. All this is done inside a new scope, which + // All this is done inside a new scope, which // means that the memory of csp will be released once the // information has been copied to sparsity_pattern. { - BlockCompressedSimpleSparsityPattern csp (2,2); + BlockDynamicSparsityPattern csp (2,2); csp.block(0,0).reinit (n_u, n_u); csp.block(1,0).reinit (n_p, n_u); diff --git a/examples/step-23/step-23.cc b/examples/step-23/step-23.cc index d588b12be6..429c565d78 100644 --- a/examples/step-23/step-23.cc +++ b/examples/step-23/step-23.cc @@ -29,6 +29,7 @@ #include #include #include +#include #include #include #include @@ -332,11 +333,9 @@ namespace Step23 << std::endl << std::endl; - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); - sparsity_pattern.compress(); + DynamicSparsityPattern csp(dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, csp); + sparsity_pattern.copy_from (csp); // Then comes a block where we have to initialize the 3 matrices we need // in the course of the program: the mass matrix, the Laplace matrix, and diff --git a/examples/step-24/step-24.cc b/examples/step-24/step-24.cc index 3302780e16..700aeeaaa7 100644 --- a/examples/step-24/step-24.cc +++ b/examples/step-24/step-24.cc @@ -29,6 +29,7 @@ #include #include #include +#include #include #include #include @@ -289,11 +290,9 @@ namespace Step24 << std::endl << std::endl; - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); - sparsity_pattern.compress(); + DynamicSparsityPattern csp(dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, csp); + sparsity_pattern.copy_from (csp); system_matrix.reinit (sparsity_pattern); mass_matrix.reinit (sparsity_pattern); diff --git a/examples/step-25/step-25.cc b/examples/step-25/step-25.cc index a5cd3e3924..d182d7dd3a 100644 --- a/examples/step-25/step-25.cc +++ b/examples/step-25/step-25.cc @@ -33,6 +33,7 @@ #include #include #include +#include #include #include #include @@ -306,11 +307,9 @@ namespace Step25 << dof_handler.n_dofs() << std::endl; - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); - sparsity_pattern.compress (); + DynamicSparsityPattern csp(dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, csp); + sparsity_pattern.copy_from (csp); system_matrix.reinit (sparsity_pattern); mass_matrix.reinit (sparsity_pattern); diff --git a/examples/step-26/step-26.cc b/examples/step-26/step-26.cc index 2ba5c01932..6d6781f28c 100644 --- a/examples/step-26/step-26.cc +++ b/examples/step-26/step-26.cc @@ -26,7 +26,7 @@ #include #include #include -#include +#include #include #include #include @@ -249,7 +249,7 @@ namespace Step26 constraints); constraints.close(); - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_sparsity_pattern(dof_handler, c_sparsity, constraints, diff --git a/examples/step-27/step-27.cc b/examples/step-27/step-27.cc index fa4491bd80..c1ed5552ab 100644 --- a/examples/step-27/step-27.cc +++ b/examples/step-27/step-27.cc @@ -46,11 +46,11 @@ #include // These are the new files we need. The first one provides an alternative to -// the usual SparsityPattern class and the CompressedSparsityPattern class +// the usual SparsityPattern class and the DynamicSparsityPattern class // already discussed in step-11 and step-18. The last two provide hp // versions of the DoFHandler and FEValues classes as described in the // introduction of this program. -#include +#include #include #include @@ -212,8 +212,8 @@ namespace Step27 constraints); constraints.close (); - CompressedSetSparsityPattern csp (dof_handler.n_dofs(), - dof_handler.n_dofs()); + DynamicSparsityPattern csp (dof_handler.n_dofs(), + dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, csp, constraints, false); sparsity_pattern.copy_from (csp); diff --git a/examples/step-28/step-28.cc b/examples/step-28/step-28.cc index f457ad3fd5..296fd7dbd4 100644 --- a/examples/step-28/step-28.cc +++ b/examples/step-28/step-28.cc @@ -31,6 +31,7 @@ #include #include #include +#include #include #include #include @@ -592,11 +593,10 @@ namespace Step28 system_matrix.clear (); - sparsity_pattern.reinit (n_dofs, n_dofs, - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); - hanging_node_constraints.condense (sparsity_pattern); - sparsity_pattern.compress (); + DynamicSparsityPattern csp(n_dofs, n_dofs); + DoFTools::make_sparsity_pattern (dof_handler, csp); + hanging_node_constraints.condense (csp); + sparsity_pattern.copy_from (csp); system_matrix.reinit (sparsity_pattern); diff --git a/examples/step-29/step-29.cc b/examples/step-29/step-29.cc index 99e88375a0..f18b368ae5 100644 --- a/examples/step-29/step-29.cc +++ b/examples/step-29/step-29.cc @@ -30,6 +30,7 @@ #include #include #include +#include #include #include @@ -537,12 +538,9 @@ namespace Step29 dof_handler.distribute_dofs (fe); - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); - sparsity_pattern.compress(); + DynamicSparsityPattern csp(dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, csp); + sparsity_pattern.copy_from (csp); system_matrix.reinit (sparsity_pattern); system_rhs.reinit (dof_handler.n_dofs()); diff --git a/examples/step-3/step-3.cc b/examples/step-3/step-3.cc index bc7faaa162..60ca98c3b3 100644 --- a/examples/step-3/step-3.cc +++ b/examples/step-3/step-3.cc @@ -66,7 +66,7 @@ #include #include #include -#include +#include #include #include @@ -208,7 +208,7 @@ void Step3::setup_system () // first creating a temporary structure, tagging those entries that might be // nonzero, and then copying the data over to the SparsityPattern object // that can then be used by the system matrix. - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, c_sparsity); sparsity_pattern.copy_from(c_sparsity); diff --git a/examples/step-31/step-31.cc b/examples/step-31/step-31.cc index e20e382f60..7f311fd9cd 100644 --- a/examples/step-31/step-31.cc +++ b/examples/step-31/step-31.cc @@ -919,16 +919,13 @@ namespace Step31 // The next step is to create the sparsity pattern for the Stokes and // temperature system matrices as well as the preconditioner matrix from // which we build the Stokes preconditioner. As in step-22, we choose to - // create the pattern not as in the first few tutorial programs, but by - // using the blocked version of CompressedSimpleSparsityPattern. The - // reason for doing this is mainly memory, that is, the SparsityPattern - // class would consume too much memory when used in three spatial - // dimensions as we intend to do for this program. + // create the pattern by + // using the blocked version of DynamicSparsityPattern. // // So, we first release the memory stored in the matrices, then set up an - // object of type BlockCompressedSimpleSparsityPattern consisting of + // object of type BlockDynamicSparsityPattern consisting of // $2\times 2$ blocks (for the Stokes system matrix and preconditioner) or - // CompressedSimpleSparsityPattern (for the temperature part). We then + // DynamicSparsityPattern (for the temperature part). We then // fill these objects with the nonzero pattern, taking into account that // for the Stokes system matrix, there are no entries in the // pressure-pressure block (but all velocity vector components couple with @@ -961,7 +958,7 @@ namespace Step31 { stokes_matrix.clear (); - BlockCompressedSimpleSparsityPattern csp (2,2); + BlockDynamicSparsityPattern csp (2,2); csp.block(0,0).reinit (n_u, n_u); csp.block(0,1).reinit (n_u, n_p); @@ -990,7 +987,7 @@ namespace Step31 Mp_preconditioner.reset (); stokes_preconditioner_matrix.clear (); - BlockCompressedSimpleSparsityPattern csp (2,2); + BlockDynamicSparsityPattern csp (2,2); csp.block(0,0).reinit (n_u, n_u); csp.block(0,1).reinit (n_u, n_p); @@ -1030,7 +1027,7 @@ namespace Step31 temperature_stiffness_matrix.clear (); temperature_matrix.clear (); - CompressedSimpleSparsityPattern csp (n_T, n_T); + DynamicSparsityPattern csp (n_T, n_T); DoFTools::make_sparsity_pattern (temperature_dof_handler, csp, temperature_constraints, false); diff --git a/examples/step-32/step-32.cc b/examples/step-32/step-32.cc index e669208c46..021550ffce 100644 --- a/examples/step-32/step-32.cc +++ b/examples/step-32/step-32.cc @@ -1803,7 +1803,7 @@ namespace Step32 // is that the matrices we want to set up are distributed across multiple // processors. Since we still want to build up the sparsity pattern first // for efficiency reasons, we could continue to build the entire - // sparsity pattern as a BlockCompressedSimpleSparsityPattern, as we did in + // sparsity pattern as a BlockDynamicSparsityPattern, as we did in // step-31. However, that would be inefficient: every processor would build // the same sparsity pattern, but only initialize a small part of the matrix // using it. It also violates the principle that every processor should only diff --git a/examples/step-33/step-33.cc b/examples/step-33/step-33.cc index 3e466a14ec..b46fc60fda 100644 --- a/examples/step-33/step-33.cc +++ b/examples/step-33/step-33.cc @@ -31,7 +31,7 @@ #include #include -#include +#include #include #include @@ -1401,8 +1401,8 @@ namespace Step33 template void ConservationLaw::setup_system () { - CompressedSparsityPattern sparsity_pattern (dof_handler.n_dofs(), - dof_handler.n_dofs()); + DynamicSparsityPattern sparsity_pattern (dof_handler.n_dofs(), + dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); system_matrix.reinit (sparsity_pattern); diff --git a/examples/step-35/step-35.cc b/examples/step-35/step-35.cc index b472a8f1dc..8742441d21 100644 --- a/examples/step-35/step-35.cc +++ b/examples/step-35/step-35.cc @@ -36,6 +36,7 @@ #include #include +#include #include #include #include @@ -789,13 +790,11 @@ namespace Step35 void NavierStokesProjection::initialize_velocity_matrices() { - sparsity_pattern_velocity.reinit (dof_handler_velocity.n_dofs(), - dof_handler_velocity.n_dofs(), - dof_handler_velocity.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler_velocity, - sparsity_pattern_velocity); - sparsity_pattern_velocity.compress(); - + { + DynamicSparsityPattern csp(dof_handler_velocity.n_dofs(), dof_handler_velocity.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler_velocity, csp); + sparsity_pattern_velocity.copy_from (csp); + } vel_Laplace_plus_Mass.reinit (sparsity_pattern_velocity); for (unsigned int d=0; d::initialize_pressure_matrices() { - sparsity_pattern_pressure.reinit (dof_handler_pressure.n_dofs(), dof_handler_pressure.n_dofs(), - dof_handler_pressure.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler_pressure, sparsity_pattern_pressure); - - sparsity_pattern_pressure.compress(); + { + DynamicSparsityPattern csp(dof_handler_pressure.n_dofs(), dof_handler_pressure.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler_pressure, csp); + sparsity_pattern_pressure.copy_from (csp); + } pres_Laplace.reinit (sparsity_pattern_pressure); pres_iterative.reinit (sparsity_pattern_pressure); @@ -847,13 +846,11 @@ namespace Step35 void NavierStokesProjection::initialize_gradient_operator() { - sparsity_pattern_pres_vel.reinit (dof_handler_velocity.n_dofs(), - dof_handler_pressure.n_dofs(), - dof_handler_velocity.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler_velocity, - dof_handler_pressure, - sparsity_pattern_pres_vel); - sparsity_pattern_pres_vel.compress(); + { + DynamicSparsityPattern csp(dof_handler_velocity.n_dofs(), dof_handler_pressure.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler_velocity, dof_handler_pressure, csp); + sparsity_pattern_pres_vel.copy_from (csp); + } InitGradPerTaskData per_task_data (0, fe_velocity.dofs_per_cell, fe_pressure.dofs_per_cell); diff --git a/examples/step-36/step-36.cc b/examples/step-36/step-36.cc index 9b047190a1..6cc02f2e9f 100644 --- a/examples/step-36/step-36.cc +++ b/examples/step-36/step-36.cc @@ -151,7 +151,7 @@ namespace Step36 // sure that we do not need to re-allocate memory and free the one used // previously. One way to do that would be to use code like this: // @code - // CompressedSimpleSparsityPattern + // DynamicSparsityPattern // csp (dof_handler.n_dofs(), // dof_handler.n_dofs()); // DoFTools::make_sparsity_pattern (dof_handler, csp); diff --git a/examples/step-38/step-38.cc b/examples/step-38/step-38.cc index acc6275fd8..0bc5e4435a 100644 --- a/examples/step-38/step-38.cc +++ b/examples/step-38/step-38.cc @@ -36,7 +36,7 @@ #include #include #include -#include +#include #include #include #include @@ -341,7 +341,7 @@ namespace Step38 << " degrees of freedom." << std::endl; - CompressedSparsityPattern csp (dof_handler.n_dofs(), dof_handler.n_dofs()); + DynamicSparsityPattern csp (dof_handler.n_dofs(), dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, csp); sparsity_pattern.copy_from (csp); diff --git a/examples/step-39/step-39.cc b/examples/step-39/step-39.cc index cf340a9ab5..03d5aa97dc 100644 --- a/examples/step-39/step-39.cc +++ b/examples/step-39/step-39.cc @@ -22,7 +22,7 @@ // turn will include the necessary files for SparsityPattern and Vector // classes. #include -#include +#include #include #include #include @@ -500,9 +500,9 @@ namespace Step39 // Next, we set up the sparsity pattern for the global matrix. Since we do // not know the row sizes in advance, we first fill a temporary - // CompressedSparsityPattern object and copy it to the regular + // DynamicSparsityPattern object and copy it to the regular // SparsityPattern once it is complete. - CompressedSparsityPattern c_sparsity(n_dofs); + DynamicSparsityPattern c_sparsity(n_dofs); DoFTools::make_flux_sparsity_pattern(dof_handler, c_sparsity); sparsity.copy_from(c_sparsity); matrix.reinit(sparsity); @@ -529,7 +529,7 @@ namespace Step39 { // These are roughly the same lines as above for the global matrix, // now for each level. - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs(level)); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs(level)); MGTools::make_flux_sparsity_pattern(dof_handler, c_sparsity, level); mg_sparsity[level].copy_from(c_sparsity); mg_matrix[level].reinit(mg_sparsity[level]); @@ -540,7 +540,7 @@ namespace Step39 // object on level 0. if (level>0) { - CompressedSparsityPattern ci_sparsity; + DynamicSparsityPattern ci_sparsity; ci_sparsity.reinit(dof_handler.n_dofs(level-1), dof_handler.n_dofs(level)); MGTools::make_flux_sparsity_pattern_edge(dof_handler, ci_sparsity, level); mg_sparsity_dg_interface[level].copy_from(ci_sparsity); diff --git a/examples/step-4/step-4.cc b/examples/step-4/step-4.cc index b26f2d045d..a8f06c66cf 100644 --- a/examples/step-4/step-4.cc +++ b/examples/step-4/step-4.cc @@ -38,7 +38,7 @@ #include #include #include -#include +#include #include #include @@ -271,7 +271,7 @@ void Step4::setup_system () << dof_handler.n_dofs() << std::endl; - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, c_sparsity); sparsity_pattern.copy_from(c_sparsity); diff --git a/examples/step-40/step-40.cc b/examples/step-40/step-40.cc index afc0da2d75..9dda199522 100644 --- a/examples/step-40/step-40.cc +++ b/examples/step-40/step-40.cc @@ -45,7 +45,7 @@ namespace LA #include #include #include -#include +#include #include #include @@ -295,7 +295,7 @@ namespace Step40 // The last part of this function deals with initializing the matrix with // accompanying sparsity pattern. As in previous tutorial programs, we use - // the CompressedSimpleSparsityPattern as an intermediate with which we + // the DynamicSparsityPattern as an intermediate with which we // then initialize the PETSc matrix. To do so we have to tell the sparsity // pattern its size but as above there is no way the resulting object will // be able to store even a single pointer for each global degree of @@ -315,7 +315,7 @@ namespace Step40 // entries that will exist in that part of the finite element matrix that // it will own. The final step is to initialize the matrix with the // sparsity pattern. - CompressedSimpleSparsityPattern csp (locally_relevant_dofs); + DynamicSparsityPattern csp (locally_relevant_dofs); DoFTools::make_sparsity_pattern (dof_handler, csp, constraints, false); diff --git a/examples/step-41/step-41.cc b/examples/step-41/step-41.cc index a95c310f18..b2211d7e42 100644 --- a/examples/step-41/step-41.cc +++ b/examples/step-41/step-41.cc @@ -31,7 +31,7 @@ #include #include -#include +#include #include #include #include @@ -246,7 +246,7 @@ namespace Step41 constraints); constraints.close (); - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, c_sparsity, constraints, diff --git a/examples/step-43/step-43.cc b/examples/step-43/step-43.cc index c534b2c9c6..1199c985ad 100644 --- a/examples/step-43/step-43.cc +++ b/examples/step-43/step-43.cc @@ -677,13 +677,10 @@ namespace Step43 // various blocks. This information is then used to create the sparsity // pattern for the Darcy and saturation system matrices as well as the // preconditioner matrix from which we build the Darcy preconditioner. As in - // step-31, we choose to create the pattern not as in the first few tutorial - // programs, but by using the blocked version of - // CompressedSimpleSparsityPattern. The reason for doing this is mainly - // memory, that is, the SparsityPattern class would consume too much memory - // when used in three spatial dimensions as we intend to do for this - // program. So, for this, we follow the same way as step-31 did and we don't - // have to repeat descriptions again for the rest of the member function. + // step-31, we choose to create the pattern using the blocked version of + // DynamicSparsityPattern. So, for this, we follow the same way as step-31 + // did and we don't have to repeat descriptions again for the rest of the + // member function. template void TwoPhaseFlowProblem::setup_dofs () { @@ -739,7 +736,7 @@ namespace Step43 { darcy_matrix.clear (); - BlockCompressedSimpleSparsityPattern csp (2,2); + BlockDynamicSparsityPattern csp (2,2); csp.block(0,0).reinit (n_u, n_u); csp.block(0,1).reinit (n_u, n_p); @@ -769,7 +766,7 @@ namespace Step43 Mp_preconditioner.reset (); darcy_preconditioner_matrix.clear (); - BlockCompressedSimpleSparsityPattern csp (2,2); + BlockDynamicSparsityPattern csp (2,2); csp.block(0,0).reinit (n_u, n_u); csp.block(0,1).reinit (n_u, n_p); @@ -796,7 +793,7 @@ namespace Step43 { saturation_matrix.clear (); - CompressedSimpleSparsityPattern csp (n_s, n_s); + DynamicSparsityPattern csp (n_s, n_s); DoFTools::make_sparsity_pattern (saturation_dof_handler, csp, saturation_constraints, false); diff --git a/examples/step-44/step-44.cc b/examples/step-44/step-44.cc index b72df4657f..e59bd88b53 100644 --- a/examples/step-44/step-44.cc +++ b/examples/step-44/step-44.cc @@ -50,7 +50,7 @@ #include #include -#include +#include #include #include #include @@ -1582,7 +1582,7 @@ namespace Step44 const types::global_dof_index n_dofs_p = dofs_per_block[p_dof]; const types::global_dof_index n_dofs_J = dofs_per_block[J_dof]; - BlockCompressedSimpleSparsityPattern csp(n_blocks, n_blocks); + BlockDynamicSparsityPattern csp(n_blocks, n_blocks); csp.block(u_dof, u_dof).reinit(n_dofs_u, n_dofs_u); csp.block(u_dof, p_dof).reinit(n_dofs_u, n_dofs_p); diff --git a/examples/step-45/step-45.cc b/examples/step-45/step-45.cc index d0b80883fa..72a1e1d67b 100644 --- a/examples/step-45/step-45.cc +++ b/examples/step-45/step-45.cc @@ -32,7 +32,7 @@ #include #include #include -#include +#include #include #include @@ -180,8 +180,8 @@ namespace Step45 // Then we create the sparsity pattern and the system matrix and // initialize the solution and right-hand side vectors. This is again as // in step-3 or step-6, for example: - CompressedSparsityPattern c_sparsity_pattern (dof_handler.n_dofs(), - dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity_pattern (dof_handler.n_dofs(), + dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, c_sparsity_pattern, constraints, diff --git a/examples/step-46/step-46.cc b/examples/step-46/step-46.cc index 252a0e7aa0..a0e46f9271 100644 --- a/examples/step-46/step-46.cc +++ b/examples/step-46/step-46.cc @@ -460,8 +460,8 @@ namespace Step46 // extensively in the introduction, and use it to initialize the matrix; // then also set vectors to their correct sizes: { - CompressedSimpleSparsityPattern csp (dof_handler.n_dofs(), - dof_handler.n_dofs()); + DynamicSparsityPattern csp (dof_handler.n_dofs(), + dof_handler.n_dofs()); Table<2,DoFTools::Coupling> cell_coupling (fe_collection.n_components(), fe_collection.n_components()); diff --git a/examples/step-47/step-47.cc b/examples/step-47/step-47.cc index ea3cdbbe15..3e30d75d92 100644 --- a/examples/step-47/step-47.cc +++ b/examples/step-47/step-47.cc @@ -24,7 +24,7 @@ #include #include #include -#include +#include #include #include #include @@ -259,7 +259,7 @@ namespace Step47 constraints.close(); - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, c_sparsity); constraints.condense (c_sparsity); diff --git a/examples/step-5/step-5.cc b/examples/step-5/step-5.cc index f51f193b76..a808db5c55 100644 --- a/examples/step-5/step-5.cc +++ b/examples/step-5/step-5.cc @@ -28,7 +28,7 @@ #include #include #include -#include +#include #include #include #include @@ -270,7 +270,7 @@ void Step5::setup_system () << dof_handler.n_dofs() << std::endl; - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, c_sparsity); sparsity_pattern.copy_from(c_sparsity); diff --git a/examples/step-50/step-50.cc b/examples/step-50/step-50.cc index 05a0d79ae7..ab47295877 100644 --- a/examples/step-50/step-50.cc +++ b/examples/step-50/step-50.cc @@ -371,7 +371,7 @@ namespace Step50 constraints.close (); hanging_node_constraints.close (); - CompressedSimpleSparsityPattern csp(mg_dof_handler.n_dofs(), mg_dof_handler.n_dofs()); + DynamicSparsityPattern csp(mg_dof_handler.n_dofs(), mg_dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (mg_dof_handler, csp, constraints); system_matrix.reinit (mg_dof_handler.locally_owned_dofs(), csp, MPI_COMM_WORLD, true); @@ -434,9 +434,8 @@ namespace Step50 // matrices. for (unsigned int level=0; level #include #include -#include +#include #include #include #include @@ -470,7 +470,7 @@ namespace Step51 // to the number of dofs on a face, when copying this into the final // sparsity pattern. { - CompressedSimpleSparsityPattern csp (dof_handler.n_dofs()); + DynamicSparsityPattern csp (dof_handler.n_dofs()); DoFTools::make_sparsity_pattern (dof_handler, csp, constraints, false); sparsity_pattern.copy_from(csp, fe.dofs_per_face); diff --git a/examples/step-52/step-52.cc b/examples/step-52/step-52.cc index dfef5db0df..81ee24d6b7 100644 --- a/examples/step-52/step-52.cc +++ b/examples/step-52/step-52.cc @@ -169,7 +169,7 @@ namespace Step52 VectorTools::interpolate_boundary_values(dof_handler,1,ZeroFunction<2>(),constraint_matrix); constraint_matrix.close(); - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_sparsity_pattern(dof_handler,c_sparsity,constraint_matrix); sparsity_pattern.copy_from(c_sparsity); diff --git a/examples/step-6/step-6.cc b/examples/step-6/step-6.cc index 73ca65448c..ac0fc3be25 100644 --- a/examples/step-6/step-6.cc +++ b/examples/step-6/step-6.cc @@ -28,7 +28,7 @@ #include #include #include -#include +#include #include #include #include @@ -284,9 +284,7 @@ Step6::~Step6 () // sparsity pattern, and initializing the solution and right hand side // vectors. Note that the sparsity pattern will have significantly more // entries per row now, since there are now 9 degrees of freedom per cell, not -// only four, that can couple with each other. The -// dof_Handler.max_couplings_between_dofs() call will take care -// of this, however: +// only four, that can couple with each other. template void Step6::setup_system () { @@ -346,7 +344,7 @@ void Step6::setup_system () // constraints after assembling, we would have to pass true // instead because then we would first write into these locations only to // later set them to zero again during condensation. - CompressedSparsityPattern c_sparsity(dof_handler.n_dofs()); + DynamicSparsityPattern c_sparsity(dof_handler.n_dofs()); DoFTools::make_sparsity_pattern(dof_handler, c_sparsity, constraints, diff --git a/examples/step-7/step-7.cc b/examples/step-7/step-7.cc index d60488a5d0..7442ff11c0 100644 --- a/examples/step-7/step-7.cc +++ b/examples/step-7/step-7.cc @@ -28,6 +28,7 @@ #include #include #include +#include #include #include #include @@ -530,12 +531,10 @@ namespace Step7 hanging_node_constraints); hanging_node_constraints.close (); - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); - hanging_node_constraints.condense (sparsity_pattern); - sparsity_pattern.compress(); + DynamicSparsityPattern csp (dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, csp); + hanging_node_constraints.condense (csp); + sparsity_pattern.copy_from (csp); system_matrix.reinit (sparsity_pattern); diff --git a/examples/step-8/step-8.cc b/examples/step-8/step-8.cc index 74b01ee845..a72fbda2a8 100644 --- a/examples/step-8/step-8.cc +++ b/examples/step-8/step-8.cc @@ -28,6 +28,7 @@ #include #include #include +#include #include #include #include @@ -340,14 +341,13 @@ namespace Step8 DoFTools::make_hanging_node_constraints (dof_handler, hanging_node_constraints); hanging_node_constraints.close (); - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); - hanging_node_constraints.condense (sparsity_pattern); - - sparsity_pattern.compress(); + DynamicSparsityPattern csp(dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern(dof_handler, + csp, + hanging_node_constraints, + /*keep_constrained_dofs = */ true); + sparsity_pattern.copy_from (csp); system_matrix.reinit (sparsity_pattern); diff --git a/examples/step-9/step-9.cc b/examples/step-9/step-9.cc index 092e9f9c43..b1610e4049 100644 --- a/examples/step-9/step-9.cc +++ b/examples/step-9/step-9.cc @@ -26,6 +26,7 @@ #include #include #include +#include #include #include #include @@ -547,20 +548,17 @@ namespace Step9 void AdvectionProblem::setup_system () { dof_handler.distribute_dofs (fe); - hanging_node_constraints.clear (); DoFTools::make_hanging_node_constraints (dof_handler, hanging_node_constraints); hanging_node_constraints.close (); - sparsity_pattern.reinit (dof_handler.n_dofs(), - dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity_pattern); - - hanging_node_constraints.condense (sparsity_pattern); - - sparsity_pattern.compress(); + DynamicSparsityPattern csp(dof_handler.n_dofs(), dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern(dof_handler, + csp, + hanging_node_constraints, + /*keep_constrained_dofs = */ true); + sparsity_pattern.copy_from (csp); system_matrix.reinit (sparsity_pattern); diff --git a/include/deal.II/lac/block_sparsity_pattern.h b/include/deal.II/lac/block_sparsity_pattern.h index 27c6477f08..e9a6b34e56 100644 --- a/include/deal.II/lac/block_sparsity_pattern.h +++ b/include/deal.II/lac/block_sparsity_pattern.h @@ -34,9 +34,7 @@ DEAL_II_NAMESPACE_OPEN template class BlockSparseMatrix; class BlockSparsityPattern; -class BlockCompressedSparsityPattern; -class BlockCompressedSimpleSparsityPattern; -class BlockCompressedSetSparsityPattern; +class BlockDynamicSparsityPattern; #ifdef DEAL_II_WITH_TRILINOS namespace TrilinosWrappers { @@ -443,31 +441,12 @@ public: std::size_t memory_consumption () const; /** - * Copy data from an object of type BlockCompressedSparsityPattern, i.e. + * Copy data from an object of type BlockDynamicSparsityPattern, i.e. * resize this object to the size of the given argument, and copy over the * contents of each of the subobjects. Previous content of this object is * lost. */ - void copy_from (const BlockCompressedSparsityPattern &csp); - - /** - * Copy data from an object of type BlockCompressedSetSparsityPattern, i.e. - * resize this object to the size of the given argument, and copy over the - * contents of each of the subobjects. Previous content of this object is - * lost. - */ - void copy_from (const BlockCompressedSetSparsityPattern &csp); - - /** - * Copy data from an object of type BlockCompressedSimpleSparsityPattern, - * i.e. resize this object to the size of the given argument, and copy over - * the contents of each of the subobjects. Previous content of this object - * is lost. - */ - void copy_from (const BlockCompressedSimpleSparsityPattern &csp); - - - + void copy_from (const BlockDynamicSparsityPattern &csp); }; @@ -484,14 +463,9 @@ public: * This class is an example of the "dynamic" type of * @ref Sparsity. * - * Note: There are several, exchangeable variations of this class, see - * @ref Sparsity, - * section 'Dynamic block sparsity patterns' for more information. - * - * *

Example

* - * Usage of this class is very similar to CompressedSparsityPattern, but since + * Usage of this class is very similar to DynamicSparsityPattern, but since * the use of block indices causes some additional complications, we give a * short example. * @@ -503,7 +477,7 @@ public: * * @skipline dofs_per_block @until count * - * Now, we are ready to set up the BlockCompressedSparsityPattern. + * Now, we are ready to set up the BlockDynamicSparsityPattern. * * @until collect * @@ -517,85 +491,8 @@ public: * * @author Wolfgang Bangerth, 2000, 2001, Guido Kanschat, 2006, 2007 */ -class BlockCompressedSparsityPattern : public BlockSparsityPatternBase -{ -public: - - /** - * Initialize the matrix empty, that is with no memory allocated. This is - * useful if you want such objects as member variables in other classes. You - * can make the structure usable by calling the reinit() function. - */ - BlockCompressedSparsityPattern (); - /** - * Initialize the matrix with the given number of block rows and columns. - * The blocks themselves are still empty, and you have to call - * collect_sizes() after you assign them sizes. - */ - BlockCompressedSparsityPattern (const size_type n_rows, - const size_type n_columns); - - /** - * Initialize the pattern with two BlockIndices for the block structures of - * matrix rows and columns. This function is equivalent to calling the - * previous constructor with the length of the two index vector and then - * entering the index values. - */ - BlockCompressedSparsityPattern (const std::vector &row_block_sizes, - const std::vector &col_block_sizes); - - /** - * Initialize the pattern with two BlockIndices for the block structures of - * matrix rows and columns. - */ - BlockCompressedSparsityPattern (const BlockIndices &row_indices, - const BlockIndices &col_indices); - - /** - * Resize the matrix to a tensor product of matrices with dimensions defined - * by the arguments. - * - * The matrix will have as many block rows and columns as there are entries - * in the two arguments. The block at position (i,j) will have the - * dimensions row_block_sizes[i] times col_block_sizes[j]. - */ - void reinit (const std::vector &row_block_sizes, - const std::vector &col_block_sizes); - - /** - * Resize the matrix to a tensor product of matrices with dimensions defined - * by the arguments. The two BlockIndices objects must be initialized and - * the sparsity pattern will have the same block structure afterwards. - */ - void reinit (const BlockIndices &row_indices, const BlockIndices &col_indices); - - /** - * Allow the use of the reinit functions of the base class as well. - */ - using BlockSparsityPatternBase::reinit; -}; - - - -/** - * This class extends the base class to implement an array of compressed - * sparsity patterns that can be used to initialize objects of type - * BlockSparsityPattern. It is used in the same way as the - * BlockCompressedSparsityPattern except that it builds upon the - * CompressedSetSparsityPattern instead of the CompressedSparsityPattern. See - * the documentation of the BlockCompressedSparsityPattern for examples. - * - * This class is an example of the "dynamic" type of - * @ref Sparsity. - * - * @note There are several, exchangeable variations of this class, see - * @ref Sparsity, - * section 'Dynamic block sparsity patterns' for more information. - * - * @author Wolfgang Bangerth, 2007 - */ -class BlockCompressedSetSparsityPattern : public BlockSparsityPatternBase +class BlockDynamicSparsityPattern : public BlockSparsityPatternBase { public: @@ -604,15 +501,15 @@ public: * useful if you want such objects as member variables in other classes. You * can make the structure usable by calling the reinit() function. */ - BlockCompressedSetSparsityPattern (); + BlockDynamicSparsityPattern (); /** * Initialize the matrix with the given number of block rows and columns. * The blocks themselves are still empty, and you have to call * collect_sizes() after you assign them sizes. */ - BlockCompressedSetSparsityPattern (const size_type n_rows, - const size_type n_columns); + BlockDynamicSparsityPattern (const size_type n_rows, + const size_type n_columns); /** * Initialize the pattern with two BlockIndices for the block structures of @@ -620,90 +517,8 @@ public: * previous constructor with the length of the two index vector and then * entering the index values. */ - BlockCompressedSetSparsityPattern (const std::vector &row_block_sizes, - const std::vector &col_block_sizes); - - /** - * Initialize the pattern with two BlockIndices for the block structures of - * matrix rows and columns. - */ - BlockCompressedSetSparsityPattern (const BlockIndices &row_indices, - const BlockIndices &col_indices); - - /** - * Resize the matrix to a tensor product of matrices with dimensions defined - * by the arguments. - * - * The matrix will have as many block rows and columns as there are entries - * in the two arguments. The block at position (i,j) will have the - * dimensions row_block_sizes[i] times col_block_sizes[j]. - */ - void reinit (const std::vector &row_block_sizes, - const std::vector &col_block_sizes); - - /** - * Resize the matrix to a tensor product of matrices with dimensions defined - * by the arguments. The two BlockIndices objects must be initialized and - * the sparsity pattern will have the same block structure afterwards. - */ - void reinit (const BlockIndices &row_indices, const BlockIndices &col_indices); - - /** - * Allow the use of the reinit functions of the base class as well. - */ - using BlockSparsityPatternBase::reinit; -}; - - - - - -/** - * This class extends the base class to implement an array of compressed - * sparsity patterns that can be used to initialize objects of type - * BlockSparsityPattern. It is used in the same way as the - * BlockCompressedSparsityPattern except that it builds upon the - * CompressedSimpleSparsityPattern instead of the CompressedSparsityPattern. - * See the documentation of the BlockCompressedSparsityPattern for examples. - * - * This class is an example of the "dynamic" type of - * @ref Sparsity. - * - * @note There are several, exchangeable variations of this class, see - * @ref Sparsity, - * section 'Dynamic block sparsity patterns' for more information. - * - * This class is used in step-22 and step-31. - * - * @author Timo Heister, 2008 - */ -class BlockCompressedSimpleSparsityPattern : public BlockSparsityPatternBase -{ -public: - - /** - * Initialize the matrix empty, that is with no memory allocated. This is - * useful if you want such objects as member variables in other classes. You - * can make the structure usable by calling the reinit() function. - */ - BlockCompressedSimpleSparsityPattern (); - - /** - * Initialize the matrix with the given number of block rows and columns. - * The blocks themselves are still empty, and you have to call - * collect_sizes() after you assign them sizes. - */ - BlockCompressedSimpleSparsityPattern (const size_type n_rows, - const size_type n_columns); - - /** - * Initialize the pattern with two BlockIndices for the block structures of - * matrix rows and columns. This function is equivalent to calling the - * previous constructor with the length of the two index vector and then - * entering the index values. - */ - BlockCompressedSimpleSparsityPattern (const std::vector &row_block_sizes, - const std::vector &col_block_sizes); + BlockDynamicSparsityPattern (const std::vector &row_block_sizes, + const std::vector &col_block_sizes); /** * Initialize the pattern with symmetric blocks. The number of IndexSets in @@ -713,7 +528,7 @@ public: * which is useful for distributed memory parallel computations and usually * corresponds to the locally owned DoFs. */ - BlockCompressedSimpleSparsityPattern (const std::vector &partitioning); + BlockDynamicSparsityPattern (const std::vector &partitioning); /** * Resize the pattern to a tensor product of matrices with dimensions @@ -742,9 +557,24 @@ public: /** * Allow the use of the reinit functions of the base class as well. */ - using BlockSparsityPatternBase::reinit; + using BlockSparsityPatternBase::reinit; }; +/** + * @deprecated Use BlockDynamicSparsityPattern instead. + */ +typedef BlockDynamicSparsityPattern BlockCompressedSparsityPattern DEAL_II_DEPRECATED; + +/** + * @deprecated Use BlockDynamicSparsityPattern instead. + */ +typedef BlockDynamicSparsityPattern BlockCompressedSetSparsityPattern DEAL_II_DEPRECATED; + +/** + * @deprecated Use BlockDynamicSparsityPattern instead. + */ +typedef BlockDynamicSparsityPattern BlockCompressedSimpleSparsityPattern DEAL_II_DEPRECATED; + @@ -1108,9 +938,9 @@ BlockSparsityPatternBase::n_block_rows () const inline -BlockCompressedSimpleSparsityPattern::size_type -BlockCompressedSimpleSparsityPattern::column_number (const size_type row, - const unsigned int index) const +BlockDynamicSparsityPattern::size_type +BlockDynamicSparsityPattern::column_number (const size_type row, + const unsigned int index) const { // .first= ith block, .second = jth row in that block const std::pair diff --git a/include/deal.II/lac/compressed_set_sparsity_pattern.h b/include/deal.II/lac/compressed_set_sparsity_pattern.h index 379fd72480..7a7aa12ce1 100644 --- a/include/deal.II/lac/compressed_set_sparsity_pattern.h +++ b/include/deal.II/lac/compressed_set_sparsity_pattern.h @@ -1,6 +1,6 @@ // --------------------------------------------------------------------- // -// Copyright (C) 2001 - 2014 by the deal.II authors +// Copyright (C) 2001 - 2015 by the deal.II authors // // This file is part of the deal.II library. // @@ -18,438 +18,20 @@ #include -#include -#include - -#include -#include -#include +#include DEAL_II_NAMESPACE_OPEN -template class SparseMatrix; - /*! @addtogroup Sparsity *@{ */ - /** - * This class acts as an intermediate form of the SparsityPattern class. From - * the interface it mostly represents a SparsityPattern object that is kept - * compressed at all times. However, since the final sparsity pattern is not - * known while constructing it, keeping the pattern compressed at all times - * can only be achieved at the expense of either increased memory or run time - * consumption upon use. The main purpose of this class is to avoid some - * memory bottlenecks, so we chose to implement it memory conservative, but - * the chosen data format is too unsuited to be used for actual matrices. It - * is therefore necessary to first copy the data of this object over to an - * object of type SparsityPattern before using it in actual matrices. - * - * Another viewpoint is that this class does not need up front allocation of a - * certain amount of memory, but grows as necessary. An extensive description - * of sparsity patterns can be found in the documentation of the - * @ref Sparsity - * module. - * - * This class is an example of the "dynamic" type of - * @ref Sparsity. - * It is discussed in the step-27 and - * @ref step_22 "step-22" - * tutorial programs. - * - *

Interface

- * - * Since this class is intended as an intermediate replacement of the - * SparsityPattern class, it has mostly the same interface, with small changes - * where necessary. In particular, the add() function, and the functions - * inquiring properties of the sparsity pattern are the same. - * - * - *

Usage

- * - * Use this class as follows: - * @code - * CompressedSetSparsityPattern compressed_pattern (dof_handler.n_dofs()); - * DoFTools::make_sparsity_pattern (dof_handler, - * compressed_pattern); - * constraints.condense (compressed_pattern); - * - * SparsityPattern sp; - * sp.copy_from (compressed_pattern); - * @endcode - * - * See also step-11 and step-18 for usage patterns of the related - * CompressedSparsityPattern class, and step-27 of the current class. - * - *

Notes

- * - * There are several, exchangeable variations of this class, see - * @ref Sparsity, - * section '"Dynamic" or "compressed" sparsity patterns' for more information. - * - * This class is a variation of the CompressedSparsityPattern class. Instead - * of using sorted vectors together with a caching algorithm for storing the - * column indices of nonzero entries, the std::set container is used. This - * solution might not be the fastest in all situations, but seems to work much - * better than the CompressedSparsityPattern in the context of hp-adaptivity - * (see for example step-27), or generally when there are many nonzero entries - * in each row of a matrix (see - * @ref step_22 "step-22"). - * On the other hand, a benchmark where nonzero entries were randomly inserted - * into the sparsity pattern revealed that this class is slower by a factor - * 4-6 in this situation. Hence, currently the suggestion is to carefully - * analyze which of the CompressedSparsityPattern classes works best in a - * certain setting. An algorithm which performs equally well in all situations - * still has to be found. - * - * - * @author Oliver Kayser-Herold, 2007 + * @deprecated Use DynamicSparsityPattern instead. */ -class CompressedSetSparsityPattern : public Subscriptor -{ -public: - /** - * Declare the type for container size. - */ - typedef types::global_dof_index size_type; - - /** - * An iterator that can be used to iterate over the elements of a single - * row. The result of dereferencing such an iterator is a column index. - */ - typedef std::set::const_iterator row_iterator; - - - /** - * Initialize the matrix empty, that is with no memory allocated. This is - * useful if you want such objects as member variables in other classes. You - * can make the structure usable by calling the reinit() function. - */ - CompressedSetSparsityPattern (); - - /** - * Copy constructor. This constructor is only allowed to be called if the - * matrix structure to be copied is empty. This is so in order to prevent - * involuntary copies of objects for temporaries, which can use large - * amounts of computing time. However, copy constructors are needed if yo - * want to use the STL data types on classes like this, e.g. to write such - * statements like v.push_back (CompressedSetSparsityPattern());, - * with @p v a vector of @p CompressedSetSparsityPattern objects. - */ - CompressedSetSparsityPattern (const CompressedSetSparsityPattern &); - - /** - * Initialize a rectangular matrix with @p m rows and @p n columns. - */ - CompressedSetSparsityPattern (const size_type m, - const size_type n); - - /** - * Initialize a square matrix of dimension @p n. - */ - CompressedSetSparsityPattern (const size_type n); - - /** - * Copy operator. For this the same holds as for the copy constructor: it is - * declared, defined and fine to be called, but the latter only for empty - * objects. - */ - CompressedSetSparsityPattern &operator = (const CompressedSetSparsityPattern &); - - /** - * Reallocate memory and set up data structures for a new matrix with @p m - * rows and @p n columns, with at most max_entries_per_row() nonzero entries - * per row. - */ - void reinit (const size_type m, - const size_type n); - - /** - * Since this object is kept compressed at all times anway, this function - * does nothing, but is declared to make the interface of this class as much - * alike as that of the SparsityPattern class. - */ - void compress (); - - /** - * Return whether the object is empty. It is empty if no memory is - * allocated, which is the same as that both dimensions are zero. - */ - bool empty () const; - - /** - * Return the maximum number of entries per row. Note that this number may - * change as entries are added. - */ - size_type max_entries_per_row () const; - - /** - * Add a nonzero entry to the matrix. If the entry already exists, nothing - * bad happens. - */ - void add (const size_type i, - const size_type j); - - /** - * Add several nonzero entries to the specified row of the matrix. If the - * entries already exist, nothing bad happens. - */ - template - void add_entries (const size_type row, - ForwardIterator begin, - ForwardIterator end, - const bool indices_are_sorted = false); - - /** - * Check if a value at a certain position may be non-zero. - */ - bool exists (const size_type i, - const size_type j) const; - - /** - * Make the sparsity pattern symmetric by adding the sparsity pattern of the - * transpose object. - * - * This function throws an exception if the sparsity pattern does not - * represent a square matrix. - */ - void symmetrize (); - - /** - * Print the sparsity of the matrix. The output consists of one line per row - * of the format [i,j1,j2,j3,...]. i is the row number and - * jn are the allocated columns in this row. - */ - void print (std::ostream &out) const; - - /** - * Print the sparsity of the matrix in a format that @p gnuplot understands - * and which can be used to plot the sparsity pattern in a graphical way. - * The format consists of pairs i j of nonzero elements, each - * representing one entry of this matrix, one per line of the output file. - * Indices are counted from zero on, as usual. Since sparsity patterns are - * printed in the same way as matrices are displayed, we print the negative - * of the column index, which means that the (0,0) element is in - * the top left rather than in the bottom left corner. - * - * Print the sparsity pattern in gnuplot by setting the data style to dots - * or points and use the @p plot command. - */ - void print_gnuplot (std::ostream &out) const; - - /** - * Return number of rows of this matrix, which equals the dimension of the - * image space. - */ - size_type n_rows () const; - - /** - * Return number of columns of this matrix, which equals the dimension of - * the range space. - */ - size_type n_cols () const; - - /** - * Number of entries in a specific row. - */ - size_type row_length (const size_type row) const; - - /** - * Return an iterator that can loop over all entries in the given row. - * Dereferencing the iterator yields a column index. - */ - row_iterator row_begin (const size_type row) const; - - /** - * End iterator for the given row. - */ - row_iterator row_end (const size_type row) const; - - - /** - * Compute the bandwidth of the matrix represented by this structure. The - * bandwidth is the maximum of $|i-j|$ for which the index pair $(i,j)$ - * represents a nonzero entry of the matrix. - */ - size_type bandwidth () const; - - /** - * Return the number of nonzero elements allocated through this sparsity - * pattern. - */ - size_type n_nonzero_elements () const; - - /** - * Return whether this object stores only those entries that have been added - * explicitly, or if the sparsity pattern contains elements that have been - * added through other means (implicitly) while building it. For the current - * class, the result is always true. - * - * This function mainly serves the purpose of describing the current class - * in cases where several kinds of sparsity patterns can be passed as - * template arguments. - */ - static - bool stores_only_added_elements (); - -private: - /** - * Number of rows that this sparsity structure shall represent. - */ - size_type rows; - - /** - * Number of columns that this sparsity structure shall represent. - */ - size_type cols; - - /** - * For each row of the matrix, store the allocated non-zero entries as a - * std::set of column indices. For a discussion of storage schemes see the - * CompressedSparsityPattern::Line class. - */ - struct Line - { - std::set entries; - - /** - * Constructor. - */ - Line (); - - /** - * Add the given column number to this line. - */ - void add (const size_type col_num); - - /** - * Add the columns specified by the iterator range to this line. - */ - template - void add_entries (ForwardIterator begin, - ForwardIterator end); - }; - - - /** - * Actual data: store for each row the set of nonzero entries. - */ - std::vector lines; -}; +typedef DynamicSparsityPattern CompressedSetSparsityPattern DEAL_II_DEPRECATED; /*@}*/ -/*---------------------- Inline functions -----------------------------------*/ - - -inline -CompressedSetSparsityPattern::Line::Line () -{} - - - -inline -void -CompressedSetSparsityPattern::Line::add (const size_type j) -{ - entries.insert (j); -} - - - -template -inline -void -CompressedSetSparsityPattern::Line::add_entries (ForwardIterator begin, - ForwardIterator end) -{ - entries.insert (begin, end); -} - - - -inline -CompressedSetSparsityPattern::size_type -CompressedSetSparsityPattern::n_rows () const -{ - return rows; -} - - - -inline -CompressedSetSparsityPattern::size_type -CompressedSetSparsityPattern::n_cols () const -{ - return cols; -} - - - -inline -void -CompressedSetSparsityPattern::add (const size_type i, - const size_type j) -{ - Assert (i(i, 0, rows)); - Assert (j(j, 0, cols)); - - lines[i].add (j); -} - - - -template -inline -void -CompressedSetSparsityPattern::add_entries (const size_type row, - ForwardIterator begin, - ForwardIterator end, - const bool /*indices_are_sorted*/) -{ - Assert (row < rows, ExcIndexRangeType (row, 0, rows)); - - lines[row].add_entries (begin, end); -} - - - -inline -CompressedSetSparsityPattern::size_type -CompressedSetSparsityPattern::row_length (const size_type row) const -{ - Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); - - return lines[row].entries.size(); -} - - - -inline -CompressedSetSparsityPattern::row_iterator -CompressedSetSparsityPattern::row_begin (const size_type row) const -{ - return (lines[row].entries.begin ()); -} - - - -inline -CompressedSetSparsityPattern::row_iterator -CompressedSetSparsityPattern::row_end (const size_type row) const -{ - return (lines[row].entries.end ()); -} - - - -inline -bool -CompressedSetSparsityPattern::stores_only_added_elements () -{ - return true; -} - DEAL_II_NAMESPACE_CLOSE diff --git a/include/deal.II/lac/compressed_simple_sparsity_pattern.h b/include/deal.II/lac/compressed_simple_sparsity_pattern.h index 222c933977..fb846cf20c 100644 --- a/include/deal.II/lac/compressed_simple_sparsity_pattern.h +++ b/include/deal.II/lac/compressed_simple_sparsity_pattern.h @@ -1,6 +1,6 @@ // --------------------------------------------------------------------- // -// Copyright (C) 2001 - 2014 by the deal.II authors +// Copyright (C) 2001 - 2015 by the deal.II authors // // This file is part of the deal.II library. // @@ -23,6 +23,8 @@ #include #include +#include + #include #include #include @@ -36,501 +38,12 @@ template class SparseMatrix; *@{ */ - /** - * This class acts as an intermediate form of the SparsityPattern class. From - * the interface it mostly represents a SparsityPattern object that is kept - * compressed at all times. However, since the final sparsity pattern is not - * known while constructing it, keeping the pattern compressed at all times - * can only be achieved at the expense of either increased memory or run time - * consumption upon use. The main purpose of this class is to avoid some - * memory bottlenecks, so we chose to implement it memory conservative. The - * chosen data format is too unsuited to be used for actual matrices, though. - * It is therefore necessary to first copy the data of this object over to an - * object of type SparsityPattern before using it in actual matrices. - * - * Another viewpoint is that this class does not need up front allocation of a - * certain amount of memory, but grows as necessary. An extensive description - * of sparsity patterns can be found in the documentation of the - * @ref Sparsity - * module. - * - * This class is an example of the "dynamic" type of - * @ref Sparsity. - * - *

Interface

- * - * Since this class is intended as an intermediate replacement of the - * SparsityPattern class, it has mostly the same interface, with small changes - * where necessary. In particular, the add() function, and the functions - * inquiring properties of the sparsity pattern are the same. - * - * - *

Usage

- * - * Use this class as follows: - * @code - * CompressedSimpleSparsityPattern compressed_pattern (dof_handler.n_dofs()); - * DoFTools::make_sparsity_pattern (dof_handler, - * compressed_pattern); - * constraints.condense (compressed_pattern); - * - * SparsityPattern sp; - * sp.copy_from (compressed_pattern); - * @endcode - * - * - *

Notes

- * - * There are several, exchangeable variations of this class, see - * @ref Sparsity, - * section '"Dynamic" or "compressed" sparsity patterns' for more information. - * - * @author Timo Heister, 2008 + * @deprecated Use DynamicSparsityPattern instead. */ -class CompressedSimpleSparsityPattern : public Subscriptor -{ -public: - /** - * Declare the type for container size. - */ - typedef types::global_dof_index size_type; - - /** - * An iterator that can be used to iterate over the elements of a single - * row. The result of dereferencing such an iterator is a column index. - */ - typedef std::vector::const_iterator row_iterator; - - /** - * Initialize the matrix empty, that is with no memory allocated. This is - * useful if you want such objects as member variables in other classes. You - * can make the structure usable by calling the reinit() function. - */ - CompressedSimpleSparsityPattern (); - - /** - * Copy constructor. This constructor is only allowed to be called if the - * matrix structure to be copied is empty. This is so in order to prevent - * involuntary copies of objects for temporaries, which can use large - * amounts of computing time. However, copy constructors are needed if you - * want to use the STL data types on classes like this, e.g. to write such - * statements like v.push_back (CompressedSparsityPattern());, with - * @p v a vector of @p CompressedSparsityPattern objects. - */ - CompressedSimpleSparsityPattern (const CompressedSimpleSparsityPattern &); - - /** - * Initialize a rectangular matrix with @p m rows and @p n columns. The @p - * rowset restricts the storage to elements in rows of this set. Adding - * elements outside of this set has no effect. The default argument keeps - * all entries. - */ - CompressedSimpleSparsityPattern (const size_type m, - const size_type n, - const IndexSet &rowset = IndexSet()); - - /** - * Create a square SparsityPattern using the index set. - */ - CompressedSimpleSparsityPattern (const IndexSet &indexset); - - /** - * Initialize a square matrix of dimension @p n. - */ - CompressedSimpleSparsityPattern (const size_type n); - - /** - * Copy operator. For this the same holds as for the copy constructor: it is - * declared, defined and fine to be called, but the latter only for empty - * objects. - */ - CompressedSimpleSparsityPattern &operator = (const CompressedSimpleSparsityPattern &); - - /** - * Reallocate memory and set up data structures for a new matrix with @p m - * rows and @p n columns, with at most max_entries_per_row() nonzero entries - * per row. The @p rowset restricts the storage to elements in rows of this - * set. Adding elements outside of this set has no effect. The default - * argument keeps all entries. - */ - void reinit (const size_type m, - const size_type n, - const IndexSet &rowset = IndexSet()); - - /** - * Since this object is kept compressed at all times anway, this function - * does nothing, but is declared to make the interface of this class as much - * alike as that of the SparsityPattern class. - */ - void compress (); - - /** - * Return whether the object is empty. It is empty if no memory is - * allocated, which is the same as that both dimensions are zero. - */ - bool empty () const; - - /** - * Return the maximum number of entries per row. Note that this number may - * change as entries are added. - */ - size_type max_entries_per_row () const; - - /** - * Add a nonzero entry to the matrix. If the entry already exists, nothing - * bad happens. - */ - void add (const size_type i, - const size_type j); - - /** - * Add several nonzero entries to the specified row of the matrix. If the - * entries already exist, nothing bad happens. - */ - template - void add_entries (const size_type row, - ForwardIterator begin, - ForwardIterator end, - const bool indices_are_unique_and_sorted = false); - - /** - * Check if a value at a certain position may be non-zero. - */ - bool exists (const size_type i, - const size_type j) const; - - /** - * Make the sparsity pattern symmetric by adding the sparsity pattern of the - * transpose object. - * - * This function throws an exception if the sparsity pattern does not - * represent a square matrix. - */ - void symmetrize (); - - /** - * Print the sparsity of the matrix. The output consists of one line per row - * of the format [i,j1,j2,j3,...]. i is the row number and - * jn are the allocated columns in this row. - */ - void print (std::ostream &out) const; - - /** - * Print the sparsity of the matrix in a format that @p gnuplot understands - * and which can be used to plot the sparsity pattern in a graphical way. - * The format consists of pairs i j of nonzero elements, each - * representing one entry of this matrix, one per line of the output file. - * Indices are counted from zero on, as usual. Since sparsity patterns are - * printed in the same way as matrices are displayed, we print the negative - * of the column index, which means that the (0,0) element is in - * the top left rather than in the bottom left corner. - * - * Print the sparsity pattern in gnuplot by setting the data style to dots - * or points and use the @p plot command. - */ - void print_gnuplot (std::ostream &out) const; - - /** - * Return number of rows of this matrix, which equals the dimension of the - * image space. - */ - size_type n_rows () const; - - /** - * Return number of columns of this matrix, which equals the dimension of - * the range space. - */ - size_type n_cols () const; - - /** - * Number of entries in a specific row. This function can only be called if - * the given row is a member of the index set of rows that we want to store. - */ - size_type row_length (const size_type row) const; - - /** - * Access to column number field. Return the column number of the @p - * indexth entry in @p row. - */ - size_type column_number (const size_type row, - const size_type index) const; - - /** - * Return an iterator that can loop over all entries in the given row. - * Dereferencing the iterator yields a column index. - */ - row_iterator row_begin (const size_type row) const; - - /** - * Returns the end of the current row. - */ - row_iterator row_end (const size_type row) const; - /** - * Compute the bandwidth of the matrix represented by this structure. The - * bandwidth is the maximum of $|i-j|$ for which the index pair $(i,j)$ - * represents a nonzero entry of the matrix. - */ - size_type bandwidth () const; - - /** - * Return the number of nonzero elements allocated through this sparsity - * pattern. - */ - size_type n_nonzero_elements () const; - - /** - * Return the IndexSet that sets which rows are active on the current - * processor. It corresponds to the IndexSet given to this class in the - * constructor or in the reinit function. - */ - const IndexSet &row_index_set () const; - - /** - * return whether this object stores only those entries that have been added - * explicitly, or if the sparsity pattern contains elements that have been - * added through other means (implicitly) while building it. For the current - * class, the result is always true. - * - * This function mainly serves the purpose of describing the current class - * in cases where several kinds of sparsity patterns can be passed as - * template arguments. - */ - static - bool stores_only_added_elements (); - - /** - * Determine an estimate for the memory consumption (in bytes) of this - * object. - */ - size_type memory_consumption () const; - -private: - /** - * Number of rows that this sparsity structure shall represent. - */ - size_type rows; - - /** - * Number of columns that this sparsity structure shall represent. - */ - size_type cols; - - /** - * A set that contains the valid rows. - */ - - IndexSet rowset; - - - /** - * Store some data for each row describing which entries of this row are - * nonzero. Data is stored sorted in the @p entries std::vector. The vector - * per row is dynamically growing upon insertion doubling its memory each - * time. - */ - struct Line - { - public: - /** - * Storage for the column indices of this row. This array is always kept - * sorted. - */ - std::vector entries; - - /** - * Constructor. - */ - Line (); - - /** - * Add the given column number to this line. - */ - void add (const size_type col_num); - - /** - * Add the columns specified by the iterator range to this line. - */ - template - void add_entries (ForwardIterator begin, - ForwardIterator end, - const bool indices_are_sorted); - - /** - * estimates memory consumption. - */ - size_type memory_consumption () const; - }; - - - /** - * Actual data: store for each row the set of nonzero entries. - */ - std::vector lines; -}; +typedef DynamicSparsityPattern CompressedSimpleSparsityPattern DEAL_II_DEPRECATED; /*@}*/ -/*---------------------- Inline functions -----------------------------------*/ - - -inline -void -CompressedSimpleSparsityPattern::Line::add (const size_type j) -{ - // first check the last element (or if line is still empty) - if ( (entries.size()==0) || ( entries.back() < j) ) - { - entries.push_back(j); - return; - } - - // do a binary search to find the place where to insert: - std::vector::iterator - it = Utilities::lower_bound(entries.begin(), - entries.end(), - j); - - // If this entry is a duplicate, exit immediately - if (*it == j) - return; - - // Insert at the right place in the vector. Vector grows automatically to - // fit elements. Always doubles its size. - entries.insert(it, j); -} - - - -inline -CompressedSimpleSparsityPattern::size_type -CompressedSimpleSparsityPattern::n_rows () const -{ - return rows; -} - - - -inline -types::global_dof_index -CompressedSimpleSparsityPattern::n_cols () const -{ - return cols; -} - - - -inline -void -CompressedSimpleSparsityPattern::add (const size_type i, - const size_type j) -{ - Assert (i(i, 0, rows)); - Assert (j(j, 0, cols)); - - if (rowset.size() > 0 && !rowset.is_element(i)) - return; - - const size_type rowindex = - rowset.size()==0 ? i : rowset.index_within_set(i); - lines[rowindex].add (j); -} - - - -template -inline -void -CompressedSimpleSparsityPattern::add_entries (const size_type row, - ForwardIterator begin, - ForwardIterator end, - const bool indices_are_sorted) -{ - Assert (row < rows, ExcIndexRangeType (row, 0, rows)); - - if (rowset.size() > 0 && !rowset.is_element(row)) - return; - - const size_type rowindex = - rowset.size()==0 ? row : rowset.index_within_set(row); - lines[rowindex].add_entries (begin, end, indices_are_sorted); -} - - - -inline -CompressedSimpleSparsityPattern::Line::Line () -{} - - - -inline -types::global_dof_index -CompressedSimpleSparsityPattern::row_length (const size_type row) const -{ - Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); - if (rowset.size() > 0 && !rowset.is_element(row)) - return 0; - - const size_type rowindex = - rowset.size()==0 ? row : rowset.index_within_set(row); - return lines[rowindex].entries.size(); -} - - - -inline -types::global_dof_index -CompressedSimpleSparsityPattern::column_number (const size_type row, - const size_type index) const -{ - Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); - Assert( rowset.size() == 0 || rowset.is_element(row), ExcInternalError()); - - const size_type local_row = rowset.size() ? rowset.index_within_set(row) : row; - Assert (index < lines[local_row].entries.size(), - ExcIndexRangeType (index, 0, lines[local_row].entries.size())); - return lines[local_row].entries[index]; -} - - - -inline -CompressedSimpleSparsityPattern::row_iterator -CompressedSimpleSparsityPattern::row_begin (const size_type row) const -{ - Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); - const size_type local_row = rowset.size() ? rowset.index_within_set(row) : row; - return lines[local_row].entries.begin(); -} - - - -inline -CompressedSimpleSparsityPattern::row_iterator -CompressedSimpleSparsityPattern::row_end (const size_type row) const -{ - Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); - const size_type local_row = rowset.size() ? rowset.index_within_set(row) : row; - return lines[local_row].entries.end(); -} - - - -inline -const IndexSet & -CompressedSimpleSparsityPattern::row_index_set () const -{ - return rowset; -} - - - -inline -bool -CompressedSimpleSparsityPattern::stores_only_added_elements () -{ - return true; -} DEAL_II_NAMESPACE_CLOSE diff --git a/include/deal.II/lac/compressed_sparsity_pattern.h b/include/deal.II/lac/compressed_sparsity_pattern.h index b4024a7d29..b98d4c0d42 100644 --- a/include/deal.II/lac/compressed_sparsity_pattern.h +++ b/include/deal.II/lac/compressed_sparsity_pattern.h @@ -1,6 +1,6 @@ // --------------------------------------------------------------------- // -// Copyright (C) 2001 - 2014 by the deal.II authors +// Copyright (C) 2001 - 2015 by the deal.II authors // // This file is part of the deal.II library. // @@ -18,512 +18,20 @@ #include -#include -#include - -#include -#include +#include DEAL_II_NAMESPACE_OPEN -template class SparseMatrix; - - -// TODO[WB]: Unify implementation with the CompressedSetSparsityPattern -// since really all that's different is the Line structure in the two -// classes. We should have a templatized base class that simply gets the -// particular Line structure from a derived class. - /*! @addtogroup Sparsity *@{ */ - /** - * This class acts as an intermediate form of the SparsityPattern class. From - * the interface it mostly represents a SparsityPattern object that is kept - * compressed at all times. However, since the final sparsity pattern is not - * known while constructing it, keeping the pattern compressed at all times - * can only be achieved at the expense of either increased memory or run time - * consumption upon use. The main purpose of this class is to avoid some - * memory bottlenecks, so we chose to implement it memory conservative, but - * the chosen data format is too unsuited to be used for actual matrices. It - * is therefore necessary to first copy the data of this object over to an - * object of type SparsityPattern before using it in actual matrices. - * - * Another viewpoint is that this class does not need up front allocation of a - * certain amount of memory, but grows as necessary. An extensive description - * of sparsity patterns can be found in the documentation of the - * @ref Sparsity - * module. - * - * This class is an example of the "dynamic" type of - * @ref Sparsity. - * - *

Interface

- * - * Since this class is intended as an intermediate replacement of the - * SparsityPattern class, it has mostly the same interface, with small changes - * where necessary. In particular, the add() function, and the functions - * inquiring properties of the sparsity pattern are the same. - * - * - *

Usage

- * - * Use this class as follows: - * @code - * CompressedSparsityPattern compressed_pattern (dof_handler.n_dofs()); - * DoFTools::make_sparsity_pattern (dof_handler, - * compressed_pattern); - * constraints.condense (compressed_pattern); - * - * SparsityPattern sp; - * sp.copy_from (compressed_pattern); - * @endcode - * - * See also step-11 and step-18 for usage patterns. - * - *

Notes

- * - * There are several, exchangeable variations of this class, see - * @ref Sparsity, - * section '"Dynamic" or "compressed" sparsity patterns' for more information. - * - * @author Wolfgang Bangerth, 2001 + * @deprecated Use DynamicSparsityPattern instead. */ -class CompressedSparsityPattern : public Subscriptor -{ -public: - /** - * Declare the type for container size. - */ - typedef types::global_dof_index size_type; - - /** - * An iterator that can be used to iterate over the elements of a single - * row. The result of dereferencing such an iterator is a column index. - */ - typedef std::vector::const_iterator row_iterator; - - /** - * Initialize the matrix empty, that is with no memory allocated. This is - * useful if you want such objects as member variables in other classes. You - * can make the structure usable by calling the reinit() function. - */ - CompressedSparsityPattern (); - - /** - * Copy constructor. This constructor is only allowed to be called if the - * matrix structure to be copied is empty. This is so in order to prevent - * involuntary copies of objects for temporaries, which can use large - * amounts of computing time. However, copy constructors are needed if yo - * want to use the STL data types on classes like this, e.g. to write such - * statements like v.push_back (CompressedSparsityPattern());, with - * @p v a vector of @p CompressedSparsityPattern objects. - */ - CompressedSparsityPattern (const CompressedSparsityPattern &); - - /** - * Initialize a rectangular matrix with @p m rows and @p n columns. - */ - CompressedSparsityPattern (const size_type m, - const size_type n); - - /** - * Initialize a square matrix of dimension @p n. - */ - CompressedSparsityPattern (const size_type n); - - /** - * Copy operator. For this the same holds as for the copy constructor: it is - * declared, defined and fine to be called, but the latter only for empty - * objects. - */ - CompressedSparsityPattern &operator = (const CompressedSparsityPattern &); - - /** - * Reallocate memory and set up data structures for a new matrix with @p m - * rows and @p n columns, with at most max_entries_per_row() nonzero entries - * per row. - */ - void reinit (const size_type m, - const size_type n); - - /** - * Since this object is kept compressed at all times anway, this function - * does nothing, but is declared to make the interface of this class as much - * alike as that of the SparsityPattern class. - */ - void compress (); - - /** - * Return whether the object is empty. It is empty if no memory is - * allocated, which is the same as that both dimensions are zero. - */ - bool empty () const; - - /** - * Return the maximum number of entries per row. Note that this number may - * change as entries are added. - */ - size_type max_entries_per_row () const; - - /** - * Add a nonzero entry to the matrix. If the entry already exists, nothing - * bad happens. - */ - void add (const size_type i, - const size_type j); - - /** - * Add several nonzero entries to the specified row of the matrix. If the - * entries already exist, nothing bad happens. - */ - template - void add_entries (const size_type row, - ForwardIterator begin, - ForwardIterator end, - const bool indices_are_unique_and_sorted = false); - - /** - * Check if a value at a certain position may be non-zero. - */ - bool exists (const size_type i, - const size_type j) const; - - /** - * Make the sparsity pattern symmetric by adding the sparsity pattern of the - * transpose object. - * - * This function throws an exception if the sparsity pattern does not - * represent a square matrix. - */ - void symmetrize (); - - /** - * Print the sparsity of the matrix. The output consists of one line per row - * of the format [i,j1,j2,j3,...]. i is the row number and - * jn are the allocated columns in this row. - */ - void print (std::ostream &out) const; - - /** - * Print the sparsity of the matrix in a format that @p gnuplot understands - * and which can be used to plot the sparsity pattern in a graphical way. - * The format consists of pairs i j of nonzero elements, each - * representing one entry of this matrix, one per line of the output file. - * Indices are counted from zero on, as usual. Since sparsity patterns are - * printed in the same way as matrices are displayed, we print the negative - * of the column index, which means that the (0,0) element is in - * the top left rather than in the bottom left corner. - * - * Print the sparsity pattern in gnuplot by setting the data style to dots - * or points and use the @p plot command. - */ - void print_gnuplot (std::ostream &out) const; - - /** - * Return number of rows of this matrix, which equals the dimension of the - * image space. - */ - size_type n_rows () const; - - /** - * Return number of columns of this matrix, which equals the dimension of - * the range space. - */ - size_type n_cols () const; - - /** - * Number of entries in a specific row. - */ - size_type row_length (const size_type row) const; - - /** - * Access to column number field. Return the column number of the @p indexth - * entry in @p row. - */ - size_type column_number (const size_type row, - const size_type index) const; - - /** - * Return an iterator that can loop over all entries in the given row. - * Dereferencing the iterator yields a column index. - */ - row_iterator row_begin (const size_type row) const; - - /** - * Returns the end of the current row. - */ - row_iterator row_end (const size_type row) const; - - /** - * Compute the bandwidth of the matrix represented by this structure. The - * bandwidth is the maximum of $|i-j|$ for which the index pair $(i,j)$ - * represents a nonzero entry of the matrix. - */ - size_type bandwidth () const; - - /** - * Return the number of nonzero elements allocated through this sparsity - * pattern. - */ - size_type n_nonzero_elements () const; - - /** - * Return whether this object stores only those entries that have been added - * explicitly, or if the sparsity pattern contains elements that have been - * added through other means (implicitly) while building it. For the current - * class, the result is always true. - * - * This function mainly serves the purpose of describing the current class - * in cases where several kinds of sparsity patterns can be passed as - * template arguments. - */ - static - bool stores_only_added_elements (); - -private: - /** - * Number of rows that this sparsity structure shall represent. - */ - size_type rows; - - /** - * Number of columns that this sparsity structure shall represent. - */ - size_type cols; - - /** - * Store some data for each row describing which entries of this row are - * nonzero. Data is organized as follows: if an entry is added to a row, it - * is first added to the #cache variable, irrespective of whether an entry - * with same column number has already been added. Only if the cache is full - * do we flush it by removing duplicates, removing entries that are already - * stored in the @p entries array, sorting everything, and merging the two - * arrays. - * - * The reasoning behind this scheme is that memory allocation is expensive, - * and we only want to do it when really necessary. Previously (in deal.II - * versions up to 5.0), we used to store the column indices inside a - * std::set, but this would allocate 20 bytes each time we added an entry. - * (A std::set based class has later been revived in form of the - * CompressedSetSparsityPattern class, as this turned out to be more - * efficient for hp finite element programs such as step-27). Using the - * present scheme, we only need to allocate memory once for every 8 added - * entries, and we waste a lot less memory by not using a balanced tree for - * storing column indices. - * - * Since some functions that are @p const need to access the data of this - * object, but need to flush caches before, the flush_cache() function is - * marked const, and the data members are marked @p mutable. - * - * A small testseries about the size of the cache showed that the run time - * of a small program just testing the compressed sparsity pattern element - * insertion routine ran for 3.6 seconds with a cache size of 8, and 4.2 - * seconds with a cache size of 16. We deem even smaller cache sizes - * undesirable, since they lead to more memory allocations, while larger - * cache sizes lead to waste of memory. The original version of this class, - * with one std::set per row took 8.2 seconds on the same program. - */ - struct Line - { - private: - /** - * Size of the cache. - */ - static const unsigned int cache_size = 8; - - public: - /** - * Storage for the column indices of this row, unless they are still in - * the cache. This array is always kept sorted. - */ - mutable std::vector entries; - - /** - * Cache of entries that have not yet been written to #entries; - */ - mutable size_type cache[cache_size]; - - /** - * Number of entries in the cache. - */ - mutable unsigned int cache_entries; - - /** - * Constructor. - */ - Line (); - - /** - * Add the given column number to this line. - */ - void add (const size_type col_num); - - /** - * Add the columns specified by the iterator range to this line. - */ - template - void add_entries (ForwardIterator begin, - ForwardIterator end, - const bool indices_are_sorted); - - /** - * Flush the cache my merging it with the #entries array. - */ - void flush_cache () const; - }; - - - /** - * Actual data: store for each row the set of nonzero entries. - */ - std::vector lines; -}; +typedef DynamicSparsityPattern CompressedSparsityPattern DEAL_II_DEPRECATED; /*@}*/ -/*---------------------- Inline functions -----------------------------------*/ - - -inline -void -CompressedSparsityPattern::Line::add (const size_type j) -{ - // first check whether this entry is - // already in the cache. if so, we can - // safely return - for (unsigned int i=0; i(i, 0, rows)); - Assert (j(j, 0, cols)); - - lines[i].add (j); -} - - - -template -inline -void -CompressedSparsityPattern::add_entries (const size_type row, - ForwardIterator begin, - ForwardIterator end, - const bool indices_are_sorted) -{ - Assert (row < rows, ExcIndexRange (row, 0, rows)); - - lines[row].add_entries (begin, end, indices_are_sorted); -} - - - -inline -CompressedSparsityPattern::Line::Line () - : - cache_entries (0) -{} - - - -inline -types::global_dof_index -CompressedSparsityPattern::row_length (const size_type row) const -{ - Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); - - if (lines[row].cache_entries != 0) - lines[row].flush_cache (); - return lines[row].entries.size(); -} - - - -inline -types::global_dof_index -CompressedSparsityPattern::column_number (const size_type row, - const size_type index) const -{ - Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); - Assert (index < lines[row].entries.size(), - ExcIndexRangeType (index, 0, lines[row].entries.size())); - - if (lines[row].cache_entries != 0) - lines[row].flush_cache (); - return lines[row].entries[index]; -} - - - -inline -CompressedSparsityPattern::row_iterator -CompressedSparsityPattern::row_begin (const size_type row) const -{ - Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); - - if (lines[row].cache_entries != 0) - lines[row].flush_cache (); - return lines[row].entries.begin(); -} - - - -inline -CompressedSparsityPattern::row_iterator -CompressedSparsityPattern::row_end (const size_type row) const -{ - Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); - return lines[row].entries.end(); -} - - - -inline -bool -CompressedSparsityPattern::stores_only_added_elements () -{ - return true; -} - - - DEAL_II_NAMESPACE_CLOSE diff --git a/include/deal.II/lac/constraint_matrix.h b/include/deal.II/lac/constraint_matrix.h index d237a17916..64de8f3d6c 100644 --- a/include/deal.II/lac/constraint_matrix.h +++ b/include/deal.II/lac/constraint_matrix.h @@ -40,13 +40,9 @@ DEAL_II_NAMESPACE_OPEN template class Table; template class FullMatrix; class SparsityPattern; -class CompressedSparsityPattern; -class CompressedSetSparsityPattern; -class CompressedSimpleSparsityPattern; +class DynamicSparsityPattern; class BlockSparsityPattern; -class BlockCompressedSparsityPattern; -class BlockCompressedSetSparsityPattern; -class BlockCompressedSimpleSparsityPattern; +class BlockDynamicSparsityPattern; template class SparseMatrix; template class BlockSparseMatrix; class BlockIndices; @@ -544,63 +540,17 @@ public: */ void condense (BlockSparsityPattern &sparsity) const; - /** - * Same function as above, but condenses square compressed sparsity - * patterns. - * - * Given the data structure used by CompressedSparsityPattern, this function - * becomes quadratic in the number of degrees of freedom for large problems - * and can dominate setting up linear systems when several hundred thousand - * or millions of unknowns are involved and for problems with many nonzero - * elements per row (for example for vector-valued problems or hp finite - * elements). In this case, it is advisable to use the - * CompressedSetSparsityPattern class instead, see for example - * @ref step_27 "step-27", - * or to use the CompressedSimpleSparsityPattern class, see for example - * @ref step_31 "step-31". - */ - void condense (CompressedSparsityPattern &sparsity) const; - - /** - * Same function as above, but condenses compressed sparsity patterns, which - * are based on the std::set container. - */ - void condense (CompressedSetSparsityPattern &sparsity) const; - - /** - * Same function as above, but condenses compressed sparsity patterns, which - * are based on the ''simple'' aproach. - */ - void condense (CompressedSimpleSparsityPattern &sparsity) const; - - /** - * Same function as above, but condenses square compressed sparsity - * patterns. - * - * Given the data structure used by BlockCompressedSparsityPattern, this - * function becomes quadratic in the number of degrees of freedom for large - * problems and can dominate setting up linear systems when several hundred - * thousand or millions of unknowns are involved and for problems with many - * nonzero elements per row (for example for vector-valued problems or hp - * finite elements). In this case, it is advisable to use the - * BlockCompressedSetSparsityPattern class instead, see for example - * @ref step_27 "step-27" - * and - * @ref step_31 "step-31". - */ - void condense (BlockCompressedSparsityPattern &sparsity) const; - /** * Same function as above, but condenses square compressed sparsity * patterns. */ - void condense (BlockCompressedSetSparsityPattern &sparsity) const; + void condense (DynamicSparsityPattern &sparsity) const; /** * Same function as above, but condenses square compressed sparsity * patterns. */ - void condense (BlockCompressedSimpleSparsityPattern &sparsity) const; + void condense (BlockDynamicSparsityPattern &sparsity) const; /** * Condense a given matrix, i.e., eliminate the rows and columns of the diff --git a/include/deal.II/lac/dynamic_sparsity_pattern.h b/include/deal.II/lac/dynamic_sparsity_pattern.h new file mode 100644 index 0000000000..4078822cfc --- /dev/null +++ b/include/deal.II/lac/dynamic_sparsity_pattern.h @@ -0,0 +1,528 @@ +// --------------------------------------------------------------------- +// +// Copyright (C) 2011 - 2015 by the deal.II authors +// +// This file is part of the deal.II library. +// +// The deal.II library is free software; you can use it, redistribute +// it, and/or modify it under the terms of the GNU Lesser General +// Public License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// The full text of the license can be found in the file LICENSE at +// the top level of the deal.II distribution. +// +// --------------------------------------------------------------------- + +#ifndef __deal2__dynamic_sparsity_pattern_h +#define __deal2__dynamic_sparsity_pattern_h + + +#include +#include +#include +#include +#include + +#include +#include +#include + +DEAL_II_NAMESPACE_OPEN + +template class SparseMatrix; + + +/*! @addtogroup Sparsity + *@{ + */ + + +/** + * This class acts as an intermediate form of the SparsityPattern class. From + * the interface it mostly represents a SparsityPattern object that is kept + * compressed at all times. However, since the final sparsity pattern is not + * known while constructing it, keeping the pattern compressed at all times + * can only be achieved at the expense of either increased memory or run time + * consumption upon use. The main purpose of this class is to avoid some + * memory bottlenecks, so we chose to implement it memory conservative. The + * chosen data format is too unsuited to be used for actual matrices, though. + * It is therefore necessary to first copy the data of this object over to an + * object of type SparsityPattern before using it in actual matrices. + * + * Another viewpoint is that this class does not need up front allocation of a + * certain amount of memory, but grows as necessary. An extensive description + * of sparsity patterns can be found in the documentation of the + * @ref Sparsity + * module. + * + * This class is an example of the "dynamic" type of + * @ref Sparsity. + * + *

Interface

+ * + * Since this class is intended as an intermediate replacement of the + * SparsityPattern class, it has mostly the same interface, with small changes + * where necessary. In particular, the add() function, and the functions + * inquiring properties of the sparsity pattern are the same. + * + * + *

Usage

+ * + * Use this class as follows: + * @code + * DynamicSparsityPattern compressed_pattern (dof_handler.n_dofs()); + * DoFTools::make_sparsity_pattern (dof_handler, + * compressed_pattern); + * constraints.condense (compressed_pattern); + * + * SparsityPattern sp; + * sp.copy_from (compressed_pattern); + * @endcode + * + * @author Timo Heister, 2008 + */ +class DynamicSparsityPattern : public Subscriptor +{ +public: + /** + * Declare the type for container size. + */ + typedef types::global_dof_index size_type; + + /** + * An iterator that can be used to iterate over the elements of a single + * row. The result of dereferencing such an iterator is a column index. + */ + typedef std::vector::const_iterator row_iterator; + + /** + * Initialize as an empty object. This is + * useful if you want such objects as member variables in other classes. You + * can make the structure usable by calling the reinit() function. + */ + DynamicSparsityPattern (); + + /** + * Copy constructor. This constructor is only allowed to be called if the + * sparsity structure to be copied is empty. This is so in order to prevent + * involuntary copies of objects for temporaries, which can use large + * amounts of computing time. However, copy constructors are needed if you + * want to use the STL data types on classes like this, e.g. to write such + * statements like v.push_back (DynamicSparsityPattern());, with + * @p v a vector of @p DynamicSparsityPattern objects. + */ + DynamicSparsityPattern (const DynamicSparsityPattern &); + + /** + * Initialize a rectangular sparsity pattern with @p m rows and @p n columns. The @p + * rowset restricts the storage to elements in rows of this set. Adding + * elements outside of this set has no effect. The default argument keeps + * all entries. + */ + DynamicSparsityPattern (const size_type m, + const size_type n, + const IndexSet &rowset = IndexSet()); + + /** + * Create a square SparsityPattern using the index set. + */ + DynamicSparsityPattern (const IndexSet &indexset); + + /** + * Initialize a square pattern of dimension @p n. + */ + DynamicSparsityPattern (const size_type n); + + /** + * Copy operator. For this the same holds as for the copy constructor: it is + * declared, defined and fine to be called, but the latter only for empty + * objects. + */ + DynamicSparsityPattern &operator = (const DynamicSparsityPattern &); + + /** + * Reallocate memory and set up data structures for a new sparsity pattern with @p m + * rows and @p n columns. The @p rowset restricts the storage to elements in rows of this + * set. Adding elements outside of this set has no effect. The default + * argument keeps all entries. + */ + void reinit (const size_type m, + const size_type n, + const IndexSet &rowset = IndexSet()); + + /** + * Since this object is kept compressed at all times anyway, this function + * does nothing, but is declared to make the interface of this class as much + * alike as that of the SparsityPattern class. + */ + void compress (); + + /** + * Return whether the object is empty. It is empty if no memory is + * allocated, which is the same as that both dimensions are zero. + */ + bool empty () const; + + /** + * Return the maximum number of entries per row. Note that this number may + * change as entries are added. + */ + size_type max_entries_per_row () const; + + /** + * Add a nonzero entry. If the entry already exists, this call does nothing. + */ + void add (const size_type i, + const size_type j); + + /** + * Add several nonzero entries to the specified row. Already existing entries are ignored. + */ + template + void add_entries (const size_type row, + ForwardIterator begin, + ForwardIterator end, + const bool indices_are_unique_and_sorted = false); + + /** + * Check if a value at a certain position may be non-zero. + */ + bool exists (const size_type i, + const size_type j) const; + + /** + * Make the sparsity pattern symmetric by adding the sparsity pattern of the + * transpose object. + * + * This function throws an exception if the sparsity pattern does not + * represent a square matrix. + */ + void symmetrize (); + + /** + * Print the sparsity pattern. The output consists of one line per row + * of the format [i,j1,j2,j3,...]. i is the row number and + * jn are the allocated columns in this row. + */ + void print (std::ostream &out) const; + + /** + * Print the sparsity pattern in a format that @p gnuplot understands + * and which can be used to plot the sparsity pattern in a graphical way. + * The format consists of pairs i j of nonzero elements, each + * representing one entry, one per line of the output file. + * Indices are counted from zero on, as usual. Since sparsity patterns are + * printed in the same way as matrices are displayed, we print the negative + * of the column index, which means that the (0,0) element is in + * the top left rather than in the bottom left corner. + * + * Print the sparsity pattern in gnuplot by setting the data style to dots + * or points and use the @p plot command. + */ + void print_gnuplot (std::ostream &out) const; + + /** + * Return the number of rows, which equals the dimension of the + * image space. + */ + size_type n_rows () const; + + /** + * Return the number of columns, which equals the dimension of + * the range space. + */ + size_type n_cols () const; + + /** + * Number of entries in a specific row. This function can only be called if + * the given row is a member of the index set of rows that we want to store. + */ + size_type row_length (const size_type row) const; + + /** + * Access to column number field. Return the column number of the @p + * indexth entry in @p row. + */ + size_type column_number (const size_type row, + const size_type index) const; + + /** + * Return an iterator that can loop over all entries in the given row. + * Dereferencing the iterator yields a column index. + */ + row_iterator row_begin (const size_type row) const; + + /** + * Returns the end of the current row. + */ + row_iterator row_end (const size_type row) const; + /** + * Compute the bandwidth of the matrix represented by this structure. The + * bandwidth is the maximum of $|i-j|$ for which the index pair $(i,j)$ + * represents a nonzero entry of the matrix. + */ + size_type bandwidth () const; + + /** + * Return the number of nonzero elements allocated through this sparsity + * pattern. + */ + size_type n_nonzero_elements () const; + + /** + * Return the IndexSet that sets which rows are active on the current + * processor. It corresponds to the IndexSet given to this class in the + * constructor or in the reinit function. + */ + const IndexSet &row_index_set () const; + + /** + * return whether this object stores only those entries that have been added + * explicitly, or if the sparsity pattern contains elements that have been + * added through other means (implicitly) while building it. For the current + * class, the result is always true. + * + * This function mainly serves the purpose of describing the current class + * in cases where several kinds of sparsity patterns can be passed as + * template arguments. + */ + static + bool stores_only_added_elements (); + + /** + * Determine an estimate for the memory consumption (in bytes) of this + * object. + */ + size_type memory_consumption () const; + +private: + /** + * Number of rows that this sparsity structure shall represent. + */ + size_type rows; + + /** + * Number of columns that this sparsity structure shall represent. + */ + size_type cols; + + /** + * A set that contains the valid rows. + */ + + IndexSet rowset; + + + /** + * Store some data for each row describing which entries of this row are + * nonzero. Data is stored sorted in the @p entries std::vector. The vector + * per row is dynamically growing upon insertion doubling its memory each + * time. + */ + struct Line + { + public: + /** + * Storage for the column indices of this row. This array is always kept + * sorted. + */ + std::vector entries; + + /** + * Constructor. + */ + Line (); + + /** + * Add the given column number to this line. + */ + void add (const size_type col_num); + + /** + * Add the columns specified by the iterator range to this line. + */ + template + void add_entries (ForwardIterator begin, + ForwardIterator end, + const bool indices_are_sorted); + + /** + * estimates memory consumption. + */ + size_type memory_consumption () const; + }; + + + /** + * Actual data: store for each row the set of nonzero entries. + */ + std::vector lines; +}; + +/*@}*/ +/*---------------------- Inline functions -----------------------------------*/ + + +inline +void +DynamicSparsityPattern::Line::add (const size_type j) +{ + // first check the last element (or if line is still empty) + if ( (entries.size()==0) || ( entries.back() < j) ) + { + entries.push_back(j); + return; + } + + // do a binary search to find the place where to insert: + std::vector::iterator + it = Utilities::lower_bound(entries.begin(), + entries.end(), + j); + + // If this entry is a duplicate, exit immediately + if (*it == j) + return; + + // Insert at the right place in the vector. Vector grows automatically to + // fit elements. Always doubles its size. + entries.insert(it, j); +} + + + +inline +DynamicSparsityPattern::size_type +DynamicSparsityPattern::n_rows () const +{ + return rows; +} + + + +inline +types::global_dof_index +DynamicSparsityPattern::n_cols () const +{ + return cols; +} + + + +inline +void +DynamicSparsityPattern::add (const size_type i, + const size_type j) +{ + Assert (i(i, 0, rows)); + Assert (j(j, 0, cols)); + + if (rowset.size() > 0 && !rowset.is_element(i)) + return; + + const size_type rowindex = + rowset.size()==0 ? i : rowset.index_within_set(i); + lines[rowindex].add (j); +} + + + +template +inline +void +DynamicSparsityPattern::add_entries (const size_type row, + ForwardIterator begin, + ForwardIterator end, + const bool indices_are_sorted) +{ + Assert (row < rows, ExcIndexRangeType (row, 0, rows)); + + if (rowset.size() > 0 && !rowset.is_element(row)) + return; + + const size_type rowindex = + rowset.size()==0 ? row : rowset.index_within_set(row); + lines[rowindex].add_entries (begin, end, indices_are_sorted); +} + + + +inline +DynamicSparsityPattern::Line::Line () +{} + + + +inline +types::global_dof_index +DynamicSparsityPattern::row_length (const size_type row) const +{ + Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); + if (rowset.size() > 0 && !rowset.is_element(row)) + return 0; + + const size_type rowindex = + rowset.size()==0 ? row : rowset.index_within_set(row); + return lines[rowindex].entries.size(); +} + + + +inline +types::global_dof_index +DynamicSparsityPattern::column_number (const size_type row, + const size_type index) const +{ + Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); + Assert( rowset.size() == 0 || rowset.is_element(row), ExcInternalError()); + + const size_type local_row = rowset.size() ? rowset.index_within_set(row) : row; + Assert (index < lines[local_row].entries.size(), + ExcIndexRangeType (index, 0, lines[local_row].entries.size())); + return lines[local_row].entries[index]; +} + + + +inline +DynamicSparsityPattern::row_iterator +DynamicSparsityPattern::row_begin (const size_type row) const +{ + Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); + const size_type local_row = rowset.size() ? rowset.index_within_set(row) : row; + return lines[local_row].entries.begin(); +} + + + +inline +DynamicSparsityPattern::row_iterator +DynamicSparsityPattern::row_end (const size_type row) const +{ + Assert (row < n_rows(), ExcIndexRangeType (row, 0, n_rows())); + const size_type local_row = rowset.size() ? rowset.index_within_set(row) : row; + return lines[local_row].entries.end(); +} + + + +inline +const IndexSet & +DynamicSparsityPattern::row_index_set () const +{ + return rowset; +} + + + +inline +bool +DynamicSparsityPattern::stores_only_added_elements () +{ + return true; +} + + +DEAL_II_NAMESPACE_CLOSE + +#endif diff --git a/include/deal.II/lac/generic_linear_algebra.h b/include/deal.II/lac/generic_linear_algebra.h index 25a5ba0648..12f319eab4 100644 --- a/include/deal.II/lac/generic_linear_algebra.h +++ b/include/deal.II/lac/generic_linear_algebra.h @@ -91,7 +91,7 @@ namespace LinearAlgebraPETSc */ typedef PETScWrappers::MPI::BlockSparseMatrix BlockSparseMatrix; - typedef dealii::BlockCompressedSimpleSparsityPattern BlockCompressedSparsityPattern; + typedef dealii::BlockDynamicSparsityPattern BlockCompressedSparsityPattern; /** * Typedef for the AMG preconditioner type. diff --git a/include/deal.II/lac/petsc_parallel_block_sparse_matrix.h b/include/deal.II/lac/petsc_parallel_block_sparse_matrix.h index 63efc40e25..61ae9a1bcf 100644 --- a/include/deal.II/lac/petsc_parallel_block_sparse_matrix.h +++ b/include/deal.II/lac/petsc_parallel_block_sparse_matrix.h @@ -155,7 +155,7 @@ namespace PETScWrappers */ void reinit(const std::vector &rows, const std::vector &cols, - const BlockCompressedSimpleSparsityPattern &bcsp, + const BlockDynamicSparsityPattern &bcsp, const MPI_Comm &com); @@ -163,7 +163,7 @@ namespace PETScWrappers * Same as above but for a symmetric structure only. */ void reinit(const std::vector &sizes, - const BlockCompressedSimpleSparsityPattern &bcsp, + const BlockDynamicSparsityPattern &bcsp, const MPI_Comm &com); diff --git a/include/deal.II/lac/sparsity_pattern.h b/include/deal.II/lac/sparsity_pattern.h index 011cdbb472..eac33c0f2d 100644 --- a/include/deal.II/lac/sparsity_pattern.h +++ b/include/deal.II/lac/sparsity_pattern.h @@ -36,11 +36,6 @@ template class SparseLUDecomposition; template class SparseILU; template class VectorSlice; -class CompressedSparsityPattern; -class CompressedSetSparsityPattern; -class CompressedSimpleSparsityPattern; - - namespace ChunkSparsityPatternIterators { class Accessor; diff --git a/include/deal.II/lac/trilinos_block_sparse_matrix.h b/include/deal.II/lac/trilinos_block_sparse_matrix.h index 1249b739e4..179411b061 100644 --- a/include/deal.II/lac/trilinos_block_sparse_matrix.h +++ b/include/deal.II/lac/trilinos_block_sparse_matrix.h @@ -37,9 +37,6 @@ DEAL_II_NAMESPACE_OPEN // forward declarations class BlockSparsityPattern; -class BlockCompressedSparsityPattern; -class BlockCompressedSetSparsityPattern; -class BlockCompressedSimpleSparsityPattern; template class BlockSparseMatrix; diff --git a/include/deal.II/lac/trilinos_sparsity_pattern.h b/include/deal.II/lac/trilinos_sparsity_pattern.h index cbbc973d8e..86a9fe81a3 100644 --- a/include/deal.II/lac/trilinos_sparsity_pattern.h +++ b/include/deal.II/lac/trilinos_sparsity_pattern.h @@ -44,9 +44,7 @@ DEAL_II_NAMESPACE_OPEN // forward declarations class SparsityPattern; -class CompressedSparsityPattern; -class CompressedSetSparsityPattern; -class CompressedSimpleSparsityPattern; +class DynamicSparsityPattern; namespace TrilinosWrappers { diff --git a/include/deal.II/matrix_free/dof_info.h b/include/deal.II/matrix_free/dof_info.h index 349c6fcb82..1bd8435f55 100644 --- a/include/deal.II/matrix_free/dof_info.h +++ b/include/deal.II/matrix_free/dof_info.h @@ -22,6 +22,7 @@ #include #include #include +#include #include #include @@ -265,7 +266,7 @@ namespace internal const std::vector &renumbering, const std::vector &irregular_cells, const bool do_blocking, - CompressedSimpleSparsityPattern &connectivity) const; + DynamicSparsityPattern &connectivity) const; /** * Renumbers the degrees of freedom to give good access for this class. diff --git a/include/deal.II/matrix_free/dof_info.templates.h b/include/deal.II/matrix_free/dof_info.templates.h index ca4049c55d..a02bf78ef0 100644 --- a/include/deal.II/matrix_free/dof_info.templates.h +++ b/include/deal.II/matrix_free/dof_info.templates.h @@ -16,7 +16,7 @@ #include #include -#include +#include #include #include #include @@ -913,7 +913,7 @@ no_constraint: (task_info.block_size*(task_info.n_blocks-1)); // create the connectivity graph with internal blocking - CompressedSimpleSparsityPattern connectivity; + DynamicSparsityPattern connectivity; make_connectivity_graph (size_info, task_info, renumbering,irregular_cells, true, connectivity); @@ -977,7 +977,7 @@ no_constraint: { Assert(cell_partition[neighbor_list[j]]==partition-1, ExcInternalError()); - CompressedSimpleSparsityPattern::row_iterator neighbor = + DynamicSparsityPattern::row_iterator neighbor = connectivity.row_begin(neighbor_list[j]), end = connectivity.row_end(neighbor_list[j]); for (; neighbor!=end ; ++neighbor) @@ -1027,7 +1027,7 @@ no_constraint: color_finder.resize(n_neighbors+1); for (unsigned int j=0; j<=n_neighbors; ++j) color_finder[j]=true; - CompressedSimpleSparsityPattern::row_iterator + DynamicSparsityPattern::row_iterator neighbor = connectivity.row_begin(cell), end = connectivity.row_end(cell); for (; neighbor!=end ; ++neighbor) @@ -1167,7 +1167,7 @@ no_constraint: unsigned int cluster_size = task_info.block_size*vectorization_length; // create the connectivity graph without internal blocking - CompressedSimpleSparsityPattern connectivity; + DynamicSparsityPattern connectivity; make_connectivity_graph (size_info, task_info, renumbering,irregular_cells, false, connectivity); @@ -1249,7 +1249,7 @@ no_constraint: } index--; unsigned int additional = neighbor_list[index]; - CompressedSimpleSparsityPattern::row_iterator neighbor = + DynamicSparsityPattern::row_iterator neighbor = connectivity.row_begin(additional), end = connectivity.row_end(additional); for (; neighbor!=end ; ++neighbor) @@ -1277,7 +1277,7 @@ no_constraint: { Assert(cell_partition[neighbor_list[j]]==partition-1, ExcInternalError()); - CompressedSimpleSparsityPattern::row_iterator neighbor = + DynamicSparsityPattern::row_iterator neighbor = connectivity.row_begin(neighbor_list[j]), end = connectivity.row_end(neighbor_list[j]); for (; neighbor!=end ; ++neighbor) @@ -1312,7 +1312,7 @@ no_constraint: } index--; unsigned int additional = neighbor_neighbor_list[index]; - CompressedSimpleSparsityPattern::row_iterator neighbor = + DynamicSparsityPattern::row_iterator neighbor = connectivity.row_begin(additional), end = connectivity.row_end(additional); for (; neighbor!=end ; ++neighbor) @@ -1412,7 +1412,7 @@ not_connect: ExcInternalError()); Assert(cell_partition_l2[neighbor_list[j]]==partition_l2-1, ExcInternalError()); - CompressedSimpleSparsityPattern::row_iterator neighbor = + DynamicSparsityPattern::row_iterator neighbor = connectivity.row_begin(neighbor_list[j]), end = connectivity.row_end(neighbor_list[j]); for (; neighbor!=end ; ++neighbor) @@ -1504,7 +1504,7 @@ not_connect: // go through the neighbors of the last cell in the // current partition and check if we find some to // fill up with. - CompressedSimpleSparsityPattern::row_iterator + DynamicSparsityPattern::row_iterator neighbor = connectivity.row_begin(additional), end = connectivity.row_end(additional); @@ -1694,7 +1694,7 @@ not_connect: const std::vector &renumbering, const std::vector &irregular_cells, const bool do_blocking, - CompressedSimpleSparsityPattern &connectivity) const + DynamicSparsityPattern &connectivity) const { AssertDimension (row_starts.size()-1, size_info.n_active_cells); const unsigned int n_rows = diff --git a/source/lac/CMakeLists.txt b/source/lac/CMakeLists.txt index 271e9486ba..5f40c74ca4 100644 --- a/source/lac/CMakeLists.txt +++ b/source/lac/CMakeLists.txt @@ -23,9 +23,7 @@ SET(_src block_vector.cc chunk_sparse_matrix.cc chunk_sparsity_pattern.cc - compressed_set_sparsity_pattern.cc - compressed_simple_sparsity_pattern.cc - compressed_sparsity_pattern.cc + dynamic_sparsity_pattern.cc constraint_matrix.cc full_matrix.cc lapack_full_matrix.cc diff --git a/source/lac/block_sparsity_pattern.cc b/source/lac/block_sparsity_pattern.cc index de0de1ef45..c177c2ecbe 100644 --- a/source/lac/block_sparsity_pattern.cc +++ b/source/lac/block_sparsity_pattern.cc @@ -270,7 +270,7 @@ BlockSparsityPatternBase::print(std::ostream &out) const template <> void -BlockSparsityPatternBase::print(std::ostream &out) const +BlockSparsityPatternBase::print(std::ostream &out) const { size_type k=0; for (size_type ib=0; ib::print(std::ostream &o size_type l=0; for (size_type jb=0; jb::print_gnuplot(std::ostream &out) template class BlockSparsityPatternBase; -template class BlockSparsityPatternBase; -template class BlockSparsityPatternBase; -template class BlockSparsityPatternBase; +template class BlockSparsityPatternBase; #ifdef DEAL_II_WITH_TRILINOS template class BlockSparsityPatternBase; #endif @@ -421,7 +419,7 @@ BlockSparsityPattern::memory_consumption () const void -BlockSparsityPattern::copy_from (const BlockCompressedSparsityPattern &csp) +BlockSparsityPattern::copy_from (const BlockDynamicSparsityPattern &csp) { // delete old content, set block // sizes anew @@ -437,189 +435,30 @@ BlockSparsityPattern::copy_from (const BlockCompressedSparsityPattern &csp) collect_sizes(); } -void -BlockSparsityPattern::copy_from (const BlockCompressedSimpleSparsityPattern &csp) -{ - // delete old content, set block - // sizes anew - reinit (csp.n_block_rows(), csp.n_block_cols()); - - // copy over blocks - for (size_type i=0; i(n_rows, - n_columns) -{} - - -BlockCompressedSparsityPattern:: -BlockCompressedSparsityPattern ( - const std::vector &row_indices, - const std::vector &col_indices) -{ - reinit(row_indices, col_indices); -} - - -BlockCompressedSparsityPattern:: -BlockCompressedSparsityPattern ( - const BlockIndices &row_indices, - const BlockIndices &col_indices) -{ - reinit(row_indices, col_indices); -} - - -void -BlockCompressedSparsityPattern::reinit ( - const std::vector &row_block_sizes, - const std::vector &col_block_sizes) -{ - BlockSparsityPatternBase::reinit(row_block_sizes.size(), col_block_sizes.size()); - for (size_type i=0; iblock(i,j).reinit(row_block_sizes[i],col_block_sizes[j]); - this->collect_sizes(); -} - - - -void -BlockCompressedSparsityPattern::reinit ( - const BlockIndices &row_indices, - const BlockIndices &col_indices) -{ - BlockSparsityPatternBase::reinit(row_indices.size(), - col_indices.size()); - for (size_type i=0; iblock(i,j).reinit(row_indices.block_size(i), - col_indices.block_size(j)); - this->collect_sizes(); -} - - - -BlockCompressedSetSparsityPattern::BlockCompressedSetSparsityPattern () -{} - - - -BlockCompressedSetSparsityPattern:: -BlockCompressedSetSparsityPattern ( - const size_type n_rows, - const size_type n_columns) - : - BlockSparsityPatternBase(n_rows, - n_columns) -{} - - -BlockCompressedSetSparsityPattern:: -BlockCompressedSetSparsityPattern ( - const std::vector &row_indices, - const std::vector &col_indices) -{ - reinit(row_indices, col_indices); -} - - -BlockCompressedSetSparsityPattern:: -BlockCompressedSetSparsityPattern ( - const BlockIndices &row_indices, - const BlockIndices &col_indices) -{ - reinit(row_indices, col_indices); -} - - -void -BlockCompressedSetSparsityPattern::reinit ( - const std::vector &row_block_sizes, - const std::vector &col_block_sizes) -{ - BlockSparsityPatternBase::reinit(row_block_sizes.size(), col_block_sizes.size()); - for (size_type i=0; iblock(i,j).reinit(row_block_sizes[i],col_block_sizes[j]); - this->collect_sizes(); -} - - - -void -BlockCompressedSetSparsityPattern::reinit ( - const BlockIndices &row_indices, - const BlockIndices &col_indices) -{ - BlockSparsityPatternBase::reinit(row_indices.size(), - col_indices.size()); - for (size_type i=0; iblock(i,j).reinit(row_indices.block_size(i), - col_indices.block_size(j)); - this->collect_sizes(); -} -BlockCompressedSimpleSparsityPattern::BlockCompressedSimpleSparsityPattern () +BlockDynamicSparsityPattern::BlockDynamicSparsityPattern () {} -BlockCompressedSimpleSparsityPattern:: -BlockCompressedSimpleSparsityPattern (const size_type n_rows, - const size_type n_columns) +BlockDynamicSparsityPattern:: +BlockDynamicSparsityPattern (const size_type n_rows, + const size_type n_columns) : - BlockSparsityPatternBase(n_rows, - n_columns) + BlockSparsityPatternBase(n_rows, + n_columns) {} -BlockCompressedSimpleSparsityPattern:: -BlockCompressedSimpleSparsityPattern (const std::vector &row_indices, - const std::vector &col_indices) +BlockDynamicSparsityPattern:: +BlockDynamicSparsityPattern (const std::vector &row_indices, + const std::vector &col_indices) : - BlockSparsityPatternBase(row_indices.size(), - col_indices.size()) + BlockSparsityPatternBase(row_indices.size(), + col_indices.size()) { for (size_type i=0; i &row_indices, } -BlockCompressedSimpleSparsityPattern:: -BlockCompressedSimpleSparsityPattern (const std::vector &partitioning) +BlockDynamicSparsityPattern:: +BlockDynamicSparsityPattern (const std::vector &partitioning) : - BlockSparsityPatternBase(partitioning.size(), - partitioning.size()) + BlockSparsityPatternBase(partitioning.size(), + partitioning.size()) { for (size_type i=0; i &partitioning) void -BlockCompressedSimpleSparsityPattern::reinit ( +BlockDynamicSparsityPattern::reinit ( const std::vector &row_block_sizes, const std::vector &col_block_sizes) { - BlockSparsityPatternBase:: + BlockSparsityPatternBase:: reinit(row_block_sizes.size(), col_block_sizes.size()); for (size_type i=0; i &partitioning) { - BlockSparsityPatternBase:: + BlockSparsityPatternBase:: reinit(partitioning.size(), partitioning.size()); for (size_type i=0; i (const CompressedSparsityPattern &, - const size_type); -template -void ChunkSparsityPattern::copy_from (const CompressedSetSparsityPattern &, - const size_type); -template -void ChunkSparsityPattern::copy_from (const CompressedSimpleSparsityPattern &, +void ChunkSparsityPattern::copy_from (const DynamicSparsityPattern &, const size_type); template void ChunkSparsityPattern::create_from @@ -629,27 +623,13 @@ void ChunkSparsityPattern::create_from const unsigned int, const bool); template -void ChunkSparsityPattern::create_from +void ChunkSparsityPattern::create_from (const unsigned int, const unsigned int, const CompressedSparsityPattern &, const unsigned int, const bool); template -void ChunkSparsityPattern::create_from -(const unsigned int, - const unsigned int, - const CompressedSetSparsityPattern &, - const unsigned int, - const bool); -template -void ChunkSparsityPattern::create_from -(const unsigned int, - const unsigned int, - const CompressedSimpleSparsityPattern &, - const unsigned int, - const bool); -template void ChunkSparsityPattern::copy_from (const FullMatrix &, const size_type); template diff --git a/source/lac/compressed_set_sparsity_pattern.cc b/source/lac/compressed_set_sparsity_pattern.cc deleted file mode 100644 index 3bec4a3747..0000000000 --- a/source/lac/compressed_set_sparsity_pattern.cc +++ /dev/null @@ -1,245 +0,0 @@ -// --------------------------------------------------------------------- -// -// Copyright (C) 2001 - 2014 by the deal.II authors -// -// This file is part of the deal.II library. -// -// The deal.II library is free software; you can use it, redistribute -// it, and/or modify it under the terms of the GNU Lesser General -// Public License as published by the Free Software Foundation; either -// version 2.1 of the License, or (at your option) any later version. -// The full text of the license can be found in the file LICENSE at -// the top level of the deal.II distribution. -// -// --------------------------------------------------------------------- - -#include - -#include -#include -#include -#include -#include -#include - -DEAL_II_NAMESPACE_OPEN - - - -CompressedSetSparsityPattern::CompressedSetSparsityPattern () - : - rows(0), - cols(0) -{} - - - -CompressedSetSparsityPattern:: -CompressedSetSparsityPattern (const CompressedSetSparsityPattern &s) - : - Subscriptor(), - rows(0), - cols(0) -{ - Assert (s.rows == 0, ExcInvalidConstructorCall()); - Assert (s.cols == 0, ExcInvalidConstructorCall()); -} - - - -CompressedSetSparsityPattern::CompressedSetSparsityPattern (const size_type m, - const size_type n) - : - rows(0), - cols(0) -{ - reinit (m,n); -} - - - -CompressedSetSparsityPattern::CompressedSetSparsityPattern (const size_type n) - : - rows(0), - cols(0) -{ - reinit (n,n); -} - - - -CompressedSetSparsityPattern & -CompressedSetSparsityPattern::operator = (const CompressedSetSparsityPattern &s) -{ - Assert (s.rows == 0, ExcInvalidConstructorCall()); - Assert (s.cols == 0, ExcInvalidConstructorCall()); - - Assert (rows == 0, ExcInvalidConstructorCall()); - Assert (cols == 0, ExcInvalidConstructorCall()); - - return *this; -} - - - -void -CompressedSetSparsityPattern::reinit (const size_type m, - const size_type n) -{ - rows = m; - cols = n; - - std::vector new_lines (rows); - lines.swap (new_lines); -} - - - -void -CompressedSetSparsityPattern::compress () -{} - - - -bool -CompressedSetSparsityPattern::empty () const -{ - return ((rows==0) && (cols==0)); -} - - - -CompressedSetSparsityPattern::size_type -CompressedSetSparsityPattern::max_entries_per_row () const -{ - size_type m = 0; - for (size_type i=0; i(lines[i].entries.size())); - } - - return m; -} - - - -bool -CompressedSetSparsityPattern::exists (const size_type i, - const size_type j) const -{ - Assert (i::const_iterator - j=lines[row].entries.begin(); - j != lines[row].entries.end(); - ++j) - // add the transpose entry if - // this is not the diagonal - if (row != *j) - add (*j, row); - } -} - - - -void -CompressedSetSparsityPattern::print (std::ostream &out) const -{ - AssertThrow (out, ExcIO()); - - for (size_type row=0; row::const_iterator - j=lines[row].entries.begin(); - j != lines[row].entries.end(); ++j) - out << ',' << *j; - - out << ']' << std::endl; - } - - AssertThrow (out, ExcIO()); -} - - - -void -CompressedSetSparsityPattern::print_gnuplot (std::ostream &out) const -{ - AssertThrow (out, ExcIO()); - - for (size_type row=0; row::const_iterator - j=lines[row].entries.begin(); - j != lines[row].entries.end(); ++j) - // while matrix entries are usually - // written (i,j), with i vertical and - // j horizontal, gnuplot output is - // x-y, that is we have to exchange - // the order of output - out << *j << " " << -static_cast(row) << std::endl; - } - - - AssertThrow (out, ExcIO()); -} - - - -CompressedSetSparsityPattern::size_type -CompressedSetSparsityPattern::bandwidth () const -{ - size_type b=0; - for (size_type row=0; row::const_iterator - j=lines[row].entries.begin(); - j != lines[row].entries.end(); ++j) - if (static_cast(std::abs(static_cast(row-*j))) > b) - b = std::abs(static_cast(row-*j)); - } - - return b; -} - - - -CompressedSetSparsityPattern::size_type -CompressedSetSparsityPattern::n_nonzero_elements () const -{ - size_type n=0; - for (size_type i=0; i - -#include -#include -#include -#include -#include -#include - -DEAL_II_NAMESPACE_OPEN - - -#ifdef DEAL_II_MSVC -__declspec(selectany) // weak external binding because of multiple link error -#endif -const unsigned int CompressedSparsityPattern::Line::cache_size; - - - -// This function was originally inlined, because it was called very -// often without any need, because cache_entries==0. On the other -// hand, it is very long and causes linker warnings on certain -// systems. - -// Therefore, we require now, that the caller checks if this function -// is necessary and only calls it, if it is actually used. Since it is -// called less often, it is removed from the inlined section. -void -CompressedSparsityPattern::Line::flush_cache () const -{ - // Make sure the caller checked - // necessity of this function. - Assert(cache_entries != 0, ExcInternalError()); - - // first sort the entries in the cache, so - // that it is easier to merge it with the - // main array. note that due to the way - // add() inserts elements, there can be no - // duplicates in the cache - // - // do the sorting in a way that is fast for - // the small cache sizes we have - // here. basically, use bubble sort - switch (cache_entries) - { - case 1: - { - break; - } - - case 2: - { - if (cache[1] < cache[0]) - std::swap (cache[0], cache[1]); - break; - } - - case 3: - { - if (cache[1] < cache[0]) - std::swap (cache[0], cache[1]); - if (cache[2] < cache[1]) - std::swap (cache[1], cache[2]); - if (cache[1] < cache[0]) - std::swap (cache[0], cache[1]); - break; - } - - case 4: - case 5: - case 6: - case 7: - { - for (unsigned int i=0; i= entries.size(), - ExcInternalError()); - if (n_new_entries > entries.size()) - { - std::vector new_entries; - new_entries.reserve (n_new_entries); - unsigned int cache_position = 0; - unsigned int entry_position = 0; - while ((entry_position -void -CompressedSparsityPattern::Line::add_entries (ForwardIterator begin, - ForwardIterator end, - const bool indices_are_sorted) -{ - // use the same code as when flushing the - // cache in case we have many (more than - // three) entries in a sorted - // list. Otherwise, go on to the single - // add() function. - const int n_elements = end - begin; - if (n_elements <= 0) - return; - - const unsigned int n_cols = static_cast(n_elements); - - if (indices_are_sorted == true) - { - - // next job is to merge the two - // arrays. special case the case that the - // original array is empty. - if (entries.size() == 0) - { - entries.resize (n_cols); - ForwardIterator my_it = begin; - for (unsigned int i=0; i= entries.size(), - ExcInternalError()); - if (n_new_entries > entries.size()) - { - std::vector new_entries; - new_entries.reserve (n_new_entries); - ForwardIterator my_it = begin; - unsigned int entry_position = 0; - while ((entry_position new_lines (rows); - lines.swap (new_lines); -} - - - -void -CompressedSparsityPattern::compress () -{} - - - -bool -CompressedSparsityPattern::empty () const -{ - return ((rows==0) && (cols==0)); -} - - - -CompressedSparsityPattern::size_type -CompressedSparsityPattern::max_entries_per_row () const -{ - size_type m = 0; - for (size_type i=0; i(lines[i].entries.size())); - } - - return m; -} - - - -bool -CompressedSparsityPattern::exists (const size_type i, - const size_type j) const -{ - Assert (i::const_iterator - j=lines[row].entries.begin(); - j != lines[row].entries.end(); - ++j) - // add the transpose entry if - // this is not the diagonal - if (row != *j) - add (*j, row); - } -} - - - -void -CompressedSparsityPattern::print (std::ostream &out) const -{ - for (size_type row=0; row::const_iterator - j=lines[row].entries.begin(); - j != lines[row].entries.end(); ++j) - out << ',' << *j; - - out << ']' << std::endl; - } - - AssertThrow (out, ExcIO()); -} - - - -void -CompressedSparsityPattern::print_gnuplot (std::ostream &out) const -{ - for (size_type row=0; row::const_iterator - j=lines[row].entries.begin(); - j != lines[row].entries.end(); ++j) - // while matrix entries are usually - // written (i,j), with i vertical and - // j horizontal, gnuplot output is - // x-y, that is we have to exchange - // the order of output - out << *j << " " << -static_cast(row) << std::endl; - } - - AssertThrow (out, ExcIO()); -} - - - -CompressedSparsityPattern::size_type -CompressedSparsityPattern::bandwidth () const -{ - size_type b=0; - for (size_type row=0; row::const_iterator - j=lines[row].entries.begin(); - j != lines[row].entries.end(); ++j) - if (static_cast(std::abs(static_cast(row-*j))) > b) - b = std::abs(static_cast(row-*j)); - } - - return b; -} - - - -CompressedSparsityPattern::size_type -CompressedSparsityPattern::n_nonzero_elements () const -{ - size_type n=0; - for (size_type i=0; i::iterator, - std::vector::iterator, - const bool); -#endif - -DEAL_II_NAMESPACE_CLOSE diff --git a/source/lac/constraint_matrix.cc b/source/lac/constraint_matrix.cc index a8d149398f..3da83d75d1 100644 --- a/source/lac/constraint_matrix.cc +++ b/source/lac/constraint_matrix.cc @@ -17,9 +17,7 @@ #include #include -#include -#include -#include +#include #include #include #include @@ -724,174 +722,8 @@ void ConstraintMatrix::condense (SparsityPattern &sparsity) const -void ConstraintMatrix::condense (CompressedSparsityPattern &sparsity) const -{ - Assert (sorted == true, ExcMatrixNotClosed()); - Assert (sparsity.n_rows() == sparsity.n_cols(), - ExcNotQuadratic()); - - // store for each index whether it must be distributed or not. If entry - // is numbers::invalid_unsigned_int, no distribution is necessary. - // otherwise, the number states which line in the constraint matrix - // handles this index - std::vector distribute(sparsity.n_rows(), - numbers::invalid_size_type); - - for (size_type c=0; c distribute(sparsity.n_rows(), - numbers::invalid_size_type); - - for (size_type c=0; c distribute (sparsity.n_rows(), - numbers::invalid_size_type); - - for (size_type c=0; c(c); - - const size_type n_rows = sparsity.n_rows(); - for (size_type row=0; row - block_index = index_mapping.global_to_local(row); - const size_type block_row = block_index.first; - const size_type local_row = block_index.second; - - if (distribute[row] == numbers::invalid_size_type) - // regular line. loop over all columns and see whether this column - // must be distributed. note that as we proceed to distribute cols, - // the loop over cols may get longer. - // - // don't try to be clever here as in the algorithm for the - // CompressedSparsityPattern, as that would be much more - // complicated here. after all, we know that compressed patterns - // are inefficient... - { - - // to loop over all entries in this row, we have to loop over all - // blocks in this blockrow and the corresponding row therein - for (size_type block_col=0; block_col distribute (sparsity.n_rows(), - numbers::invalid_size_type); - - for (size_type c=0; c(c); - - const size_type n_rows = sparsity.n_rows(); - for (size_type row=0; row - block_index = index_mapping.global_to_local(row); - const size_type block_row = block_index.first; - const size_type local_row = block_index.second; - - if (distribute[row] == numbers::invalid_size_type) - // regular line. loop over all columns and see whether this column - // must be distributed. note that as we proceed to distribute cols, - // the loop over cols may get longer. - // - // don't try to be clever here as in the algorithm for the - // CompressedSparsityPattern, as that would be much more - // complicated here. after all, we know that compressed patterns - // are inefficient... - { - - // to loop over all entries in this row, we have to loop over all - // blocks in this blockrow and the corresponding row therein - for (size_type block_col=0; block_col &) const SPARSITY_FUNCTIONS(SparsityPattern); -SPARSITY_FUNCTIONS(CompressedSparsityPattern); -SPARSITY_FUNCTIONS(CompressedSetSparsityPattern); -SPARSITY_FUNCTIONS(CompressedSimpleSparsityPattern); +SPARSITY_FUNCTIONS(DynamicSparsityPattern); BLOCK_SPARSITY_FUNCTIONS(BlockSparsityPattern); -BLOCK_SPARSITY_FUNCTIONS(BlockCompressedSparsityPattern); -BLOCK_SPARSITY_FUNCTIONS(BlockCompressedSetSparsityPattern); -BLOCK_SPARSITY_FUNCTIONS(BlockCompressedSimpleSparsityPattern); +BLOCK_SPARSITY_FUNCTIONS(BlockDynamicSparsityPattern); #ifdef DEAL_II_WITH_TRILINOS SPARSITY_FUNCTIONS(TrilinosWrappers::SparsityPattern); diff --git a/source/lac/compressed_simple_sparsity_pattern.cc b/source/lac/dynamic_sparsity_pattern.cc similarity index 80% rename from source/lac/compressed_simple_sparsity_pattern.cc rename to source/lac/dynamic_sparsity_pattern.cc index 0d2e972352..e43f56c585 100644 --- a/source/lac/compressed_simple_sparsity_pattern.cc +++ b/source/lac/dynamic_sparsity_pattern.cc @@ -1,6 +1,6 @@ // --------------------------------------------------------------------- // -// Copyright (C) 2008 - 2014 by the deal.II authors +// Copyright (C) 2008 - 2015 by the deal.II authors // // This file is part of the deal.II library. // @@ -13,7 +13,7 @@ // // --------------------------------------------------------------------- -#include +#include #include #include @@ -27,9 +27,9 @@ DEAL_II_NAMESPACE_OPEN template void -CompressedSimpleSparsityPattern::Line::add_entries (ForwardIterator begin, - ForwardIterator end, - const bool indices_are_sorted) +DynamicSparsityPattern::Line::add_entries (ForwardIterator begin, + ForwardIterator end, + const bool indices_are_sorted) { const int n_elements = end - begin; if (n_elements <= 0) @@ -207,14 +207,14 @@ CompressedSimpleSparsityPattern::Line::add_entries (ForwardIterator begin, } -CompressedSimpleSparsityPattern::size_type -CompressedSimpleSparsityPattern::Line::memory_consumption () const +DynamicSparsityPattern::size_type +DynamicSparsityPattern::Line::memory_consumption () const { return entries.capacity()*sizeof(size_type)+sizeof(Line); } -CompressedSimpleSparsityPattern::CompressedSimpleSparsityPattern () +DynamicSparsityPattern::DynamicSparsityPattern () : rows(0), cols(0), @@ -223,8 +223,8 @@ CompressedSimpleSparsityPattern::CompressedSimpleSparsityPattern () -CompressedSimpleSparsityPattern:: -CompressedSimpleSparsityPattern (const CompressedSimpleSparsityPattern &s) +DynamicSparsityPattern:: +DynamicSparsityPattern (const DynamicSparsityPattern &s) : Subscriptor(), rows(0), @@ -237,10 +237,10 @@ CompressedSimpleSparsityPattern (const CompressedSimpleSparsityPattern &s) -CompressedSimpleSparsityPattern::CompressedSimpleSparsityPattern (const size_type m, - const size_type n, - const IndexSet &rowset_ - ) +DynamicSparsityPattern::DynamicSparsityPattern (const size_type m, + const size_type n, + const IndexSet &rowset_ + ) : rows(0), cols(0), @@ -250,7 +250,7 @@ CompressedSimpleSparsityPattern::CompressedSimpleSparsityPattern (const size_typ } -CompressedSimpleSparsityPattern::CompressedSimpleSparsityPattern (const IndexSet &rowset_) +DynamicSparsityPattern::DynamicSparsityPattern (const IndexSet &rowset_) : rows(0), cols(0), @@ -260,7 +260,7 @@ CompressedSimpleSparsityPattern::CompressedSimpleSparsityPattern (const IndexSet } -CompressedSimpleSparsityPattern::CompressedSimpleSparsityPattern (const size_type n) +DynamicSparsityPattern::DynamicSparsityPattern (const size_type n) : rows(0), cols(0), @@ -271,8 +271,8 @@ CompressedSimpleSparsityPattern::CompressedSimpleSparsityPattern (const size_typ -CompressedSimpleSparsityPattern & -CompressedSimpleSparsityPattern::operator = (const CompressedSimpleSparsityPattern &s) +DynamicSparsityPattern & +DynamicSparsityPattern::operator = (const DynamicSparsityPattern &s) { Assert (s.rows == 0, ExcInvalidConstructorCall()); Assert (s.cols == 0, ExcInvalidConstructorCall()); @@ -286,9 +286,9 @@ CompressedSimpleSparsityPattern::operator = (const CompressedSimpleSparsityPatte void -CompressedSimpleSparsityPattern::reinit (const size_type m, - const size_type n, - const IndexSet &rowset_) +DynamicSparsityPattern::reinit (const size_type m, + const size_type n, + const IndexSet &rowset_) { rows = m; cols = n; @@ -303,21 +303,21 @@ CompressedSimpleSparsityPattern::reinit (const size_type m, void -CompressedSimpleSparsityPattern::compress () +DynamicSparsityPattern::compress () {} bool -CompressedSimpleSparsityPattern::empty () const +DynamicSparsityPattern::empty () const { return ((rows==0) && (cols==0)); } -CompressedSimpleSparsityPattern::size_type -CompressedSimpleSparsityPattern::max_entries_per_row () const +DynamicSparsityPattern::size_type +DynamicSparsityPattern::max_entries_per_row () const { size_type m = 0; for (size_type i=0; i::iterator, std::vector::iterator, const bool); diff --git a/source/lac/petsc_parallel_block_sparse_matrix.cc b/source/lac/petsc_parallel_block_sparse_matrix.cc index 2aaaf4b0e9..011f6ecce7 100644 --- a/source/lac/petsc_parallel_block_sparse_matrix.cc +++ b/source/lac/petsc_parallel_block_sparse_matrix.cc @@ -71,7 +71,7 @@ namespace PETScWrappers BlockSparseMatrix:: reinit(const std::vector &rows, const std::vector &cols, - const BlockCompressedSimpleSparsityPattern &bcsp, + const BlockDynamicSparsityPattern &bcsp, const MPI_Comm &com) { Assert(rows.size() == bcsp.n_block_rows(), ExcMessage("invalid size")); @@ -112,7 +112,7 @@ namespace PETScWrappers void BlockSparseMatrix:: reinit(const std::vector &sizes, - const BlockCompressedSimpleSparsityPattern &bcsp, + const BlockDynamicSparsityPattern &bcsp, const MPI_Comm &com) { reinit(sizes, sizes, bcsp, com); diff --git a/source/lac/petsc_parallel_sparse_matrix.cc b/source/lac/petsc_parallel_sparse_matrix.cc index 0232e5a143..7e4c3c7c7b 100644 --- a/source/lac/petsc_parallel_sparse_matrix.cc +++ b/source/lac/petsc_parallel_sparse_matrix.cc @@ -19,8 +19,7 @@ # include # include -# include -# include +# include DEAL_II_NAMESPACE_OPEN @@ -818,14 +817,7 @@ namespace PETScWrappers const bool); template SparseMatrix::SparseMatrix (const MPI_Comm &, - const CompressedSparsityPattern &, - const std::vector &, - const std::vector &, - const unsigned int, - const bool); - template - SparseMatrix::SparseMatrix (const MPI_Comm &, - const CompressedSimpleSparsityPattern &, + const DynamicSparsityPattern &, const std::vector &, const std::vector &, const unsigned int, @@ -840,14 +832,7 @@ namespace PETScWrappers const bool); template void SparseMatrix::reinit (const MPI_Comm &, - const CompressedSparsityPattern &, - const std::vector &, - const std::vector &, - const unsigned int, - const bool); - template void - SparseMatrix::reinit (const MPI_Comm &, - const CompressedSimpleSparsityPattern &, + const DynamicSparsityPattern &, const std::vector &, const std::vector &, const unsigned int, @@ -857,7 +842,7 @@ namespace PETScWrappers SparseMatrix:: reinit (const IndexSet &, const IndexSet &, - const CompressedSimpleSparsityPattern &, + const DynamicSparsityPattern &, const MPI_Comm &); template void @@ -867,13 +852,7 @@ namespace PETScWrappers const unsigned int , const bool); template void - SparseMatrix::do_reinit (const CompressedSparsityPattern &, - const std::vector &, - const std::vector &, - const unsigned int , - const bool); - template void - SparseMatrix::do_reinit (const CompressedSimpleSparsityPattern &, + SparseMatrix::do_reinit (const DynamicSparsityPattern &, const std::vector &, const std::vector &, const unsigned int , @@ -883,7 +862,7 @@ namespace PETScWrappers SparseMatrix:: do_reinit (const IndexSet &, const IndexSet &, - const CompressedSimpleSparsityPattern &); + const DynamicSparsityPattern &); PetscScalar diff --git a/source/lac/petsc_sparse_matrix.cc b/source/lac/petsc_sparse_matrix.cc index 2835a27b46..9675843e7d 100644 --- a/source/lac/petsc_sparse_matrix.cc +++ b/source/lac/petsc_sparse_matrix.cc @@ -19,8 +19,7 @@ # include # include -# include -# include +# include DEAL_II_NAMESPACE_OPEN @@ -316,30 +315,21 @@ namespace PETScWrappers SparseMatrix::SparseMatrix (const SparsityPattern &, const bool); template - SparseMatrix::SparseMatrix (const CompressedSparsityPattern &, - const bool); - template - SparseMatrix::SparseMatrix (const CompressedSimpleSparsityPattern &, + SparseMatrix::SparseMatrix (const DynamicSparsityPattern &, const bool); template void SparseMatrix::reinit (const SparsityPattern &, const bool); template void - SparseMatrix::reinit (const CompressedSparsityPattern &, - const bool); - template void - SparseMatrix::reinit (const CompressedSimpleSparsityPattern &, + SparseMatrix::reinit (const DynamicSparsityPattern &, const bool); template void SparseMatrix::do_reinit (const SparsityPattern &, const bool); template void - SparseMatrix::do_reinit (const CompressedSparsityPattern &, - const bool); - template void - SparseMatrix::do_reinit (const CompressedSimpleSparsityPattern &, + SparseMatrix::do_reinit (const DynamicSparsityPattern &, const bool); PetscScalar diff --git a/source/lac/sparsity_pattern.cc b/source/lac/sparsity_pattern.cc index f854bc0e74..e7ac065ee6 100644 --- a/source/lac/sparsity_pattern.cc +++ b/source/lac/sparsity_pattern.cc @@ -19,9 +19,7 @@ #include #include #include -#include -#include -#include +#include #include #include @@ -966,9 +964,7 @@ SparsityPattern::memory_consumption () const // explicit instantiations template void SparsityPattern::copy_from (const SparsityPattern &); -template void SparsityPattern::copy_from (const CompressedSparsityPattern &); -template void SparsityPattern::copy_from (const CompressedSetSparsityPattern &); -template void SparsityPattern::copy_from (const CompressedSimpleSparsityPattern &); +template void SparsityPattern::copy_from (const DynamicSparsityPattern &); template void SparsityPattern::copy_from (const FullMatrix &); template void SparsityPattern::copy_from (const FullMatrix &); diff --git a/source/lac/sparsity_tools.cc b/source/lac/sparsity_tools.cc index 3a158a27ed..492ee1589c 100644 --- a/source/lac/sparsity_tools.cc +++ b/source/lac/sparsity_tools.cc @@ -24,9 +24,7 @@ #ifdef DEAL_II_WITH_MPI #include -#include -#include -#include +#include #include #endif @@ -642,8 +640,7 @@ namespace SparsityTools const IndexSet & myrange) #ifdef DEAL_II_WITH_MPI -SPARSITY_FUNCTIONS(CompressedSparsityPattern); -SPARSITY_FUNCTIONS(CompressedSimpleSparsityPattern); +SPARSITY_FUNCTIONS(DynamicSparsityPattern); template void SparsityTools::distribute_sparsity_pattern diff --git a/source/lac/trilinos_block_sparse_matrix.cc b/source/lac/trilinos_block_sparse_matrix.cc index 8366cee339..f5743f70ab 100644 --- a/source/lac/trilinos_block_sparse_matrix.cc +++ b/source/lac/trilinos_block_sparse_matrix.cc @@ -386,12 +386,7 @@ namespace TrilinosWrappers template void BlockSparseMatrix::reinit (const dealii::BlockSparsityPattern &); template void - BlockSparseMatrix::reinit (const dealii::BlockCompressedSparsityPattern &); - template void - BlockSparseMatrix::reinit (const dealii::BlockCompressedSetSparsityPattern &); - template void - BlockSparseMatrix::reinit (const dealii::BlockCompressedSimpleSparsityPattern &); - + BlockSparseMatrix::reinit (const dealii::BlockDynamicSparsityPattern &); template void BlockSparseMatrix::reinit (const std::vector &, @@ -399,20 +394,12 @@ namespace TrilinosWrappers const bool); template void BlockSparseMatrix::reinit (const std::vector &, - const dealii::BlockCompressedSparsityPattern &, - const bool); - template void - BlockSparseMatrix::reinit (const std::vector &, - const dealii::BlockCompressedSetSparsityPattern &, - const bool); - template void - BlockSparseMatrix::reinit (const std::vector &, - const dealii::BlockCompressedSimpleSparsityPattern &, + const dealii::BlockDynamicSparsityPattern &, const bool); template void BlockSparseMatrix::reinit (const std::vector &, - const dealii::BlockCompressedSimpleSparsityPattern &, + const dealii::BlockDynamicSparsityPattern &, const MPI_Comm &, const bool); diff --git a/source/lac/trilinos_sparse_matrix.cc b/source/lac/trilinos_sparse_matrix.cc index 2c464c1ead..d956100edc 100644 --- a/source/lac/trilinos_sparse_matrix.cc +++ b/source/lac/trilinos_sparse_matrix.cc @@ -21,9 +21,7 @@ # include # include # include -# include -# include -# include +# include # include # include @@ -616,7 +614,7 @@ namespace TrilinosWrappers void SparseMatrix::reinit (const Epetra_Map &input_row_map, const Epetra_Map &input_col_map, - const CompressedSimpleSparsityPattern &sparsity_pattern, + const DynamicSparsityPattern &sparsity_pattern, const bool exchange_data) { matrix.reset(); @@ -1710,12 +1708,9 @@ namespace TrilinosWrappers { template void SparseMatrix::reinit (const dealii::SparsityPattern &); + template void - SparseMatrix::reinit (const CompressedSparsityPattern &); - template void - SparseMatrix::reinit (const CompressedSetSparsityPattern &); - template void - SparseMatrix::reinit (const CompressedSimpleSparsityPattern &); + SparseMatrix::reinit (const DynamicSparsityPattern &); template void SparseMatrix::reinit (const Epetra_Map &, @@ -1723,15 +1718,7 @@ namespace TrilinosWrappers const bool); template void SparseMatrix::reinit (const Epetra_Map &, - const CompressedSparsityPattern &, - const bool); - template void - SparseMatrix::reinit (const Epetra_Map &, - const CompressedSetSparsityPattern &, - const bool); - template void - SparseMatrix::reinit (const Epetra_Map &, - const CompressedSimpleSparsityPattern &, + const DynamicSparsityPattern &, const bool); @@ -1740,15 +1727,11 @@ namespace TrilinosWrappers const Epetra_Map &, const dealii::SparsityPattern &, const bool); + template void SparseMatrix::reinit (const Epetra_Map &, const Epetra_Map &, - const CompressedSparsityPattern &, - const bool); - template void - SparseMatrix::reinit (const Epetra_Map &, - const Epetra_Map &, - const CompressedSetSparsityPattern &, + const DynamicSparsityPattern &, const bool); } diff --git a/source/lac/trilinos_sparsity_pattern.cc b/source/lac/trilinos_sparsity_pattern.cc index 3fa461ab4e..f348004b2e 100644 --- a/source/lac/trilinos_sparsity_pattern.cc +++ b/source/lac/trilinos_sparsity_pattern.cc @@ -19,9 +19,7 @@ # include # include -# include -# include -# include +# include # include @@ -1014,11 +1012,7 @@ namespace TrilinosWrappers template void SparsityPattern::copy_from (const dealii::SparsityPattern &); template void - SparsityPattern::copy_from (const dealii::CompressedSparsityPattern &); - template void - SparsityPattern::copy_from (const dealii::CompressedSetSparsityPattern &); - template void - SparsityPattern::copy_from (const dealii::CompressedSimpleSparsityPattern &); + SparsityPattern::copy_from (const dealii::DynamicSparsityPattern &); template void @@ -1027,17 +1021,8 @@ namespace TrilinosWrappers bool); template void SparsityPattern::reinit (const Epetra_Map &, - const dealii::CompressedSparsityPattern &, - bool); - template void - SparsityPattern::reinit (const Epetra_Map &, - const dealii::CompressedSetSparsityPattern &, + const dealii::DynamicSparsityPattern &, bool); - template void - SparsityPattern::reinit (const Epetra_Map &, - const dealii::CompressedSimpleSparsityPattern &, - bool); - template void SparsityPattern::reinit (const Epetra_Map &, @@ -1047,19 +1032,8 @@ namespace TrilinosWrappers template void SparsityPattern::reinit (const Epetra_Map &, const Epetra_Map &, - const dealii::CompressedSparsityPattern &, + const dealii::DynamicSparsityPattern &, bool); - template void - SparsityPattern::reinit (const Epetra_Map &, - const Epetra_Map &, - const dealii::CompressedSetSparsityPattern &, - bool); - template void - SparsityPattern::reinit (const Epetra_Map &, - const Epetra_Map &, - const dealii::CompressedSimpleSparsityPattern &, - bool); - template void @@ -1069,17 +1043,7 @@ namespace TrilinosWrappers bool); template void SparsityPattern::reinit (const IndexSet &, - const dealii::CompressedSparsityPattern &, - const MPI_Comm &, - bool); - template void - SparsityPattern::reinit (const IndexSet &, - const dealii::CompressedSetSparsityPattern &, - const MPI_Comm &, - bool); - template void - SparsityPattern::reinit (const IndexSet &, - const dealii::CompressedSimpleSparsityPattern &, + const dealii::DynamicSparsityPattern &, const MPI_Comm &, bool); @@ -1093,19 +1057,7 @@ namespace TrilinosWrappers template void SparsityPattern::reinit (const IndexSet &, const IndexSet &, - const dealii::CompressedSparsityPattern &, - const MPI_Comm &, - bool); - template void - SparsityPattern::reinit (const IndexSet &, - const IndexSet &, - const dealii::CompressedSetSparsityPattern &, - const MPI_Comm &, - bool); - template void - SparsityPattern::reinit (const IndexSet &, - const IndexSet &, - const dealii::CompressedSimpleSparsityPattern &, + const dealii::DynamicSparsityPattern &, const MPI_Comm &, bool); diff --git a/tests/lac/sparsity_pattern_common.h b/tests/lac/sparsity_pattern_common.h index d9504ae201..d992460d0f 100644 --- a/tests/lac/sparsity_pattern_common.h +++ b/tests/lac/sparsity_pattern_common.h @@ -19,6 +19,7 @@ #include #include #include +#include #include #include #include @@ -53,10 +54,6 @@ void do_reinit (ChunkSparsityPattern &sp) } -void do_reinit (CompressedSparsityPattern &sp) -{ - sp.reinit((N-1)*(N-1), (N-1)*(N-1)); -} void do_reinit (CompressedSimpleSparsityPattern &sp, const IndexSet &index_set = IndexSet()) @@ -64,10 +61,6 @@ void do_reinit (CompressedSimpleSparsityPattern &sp, sp.reinit((N-1)*(N-1), (N-1)*(N-1), index_set); } -void do_reinit (CompressedSetSparsityPattern &sp) -{ - sp.reinit((N-1)*(N-1), (N-1)*(N-1)); -} @@ -167,28 +160,13 @@ void copy_with_offdiagonals_1 () template <> -void copy_with_offdiagonals_1 () +void copy_with_offdiagonals_1 () { // this sparsity pattern doesn't have this // function deallog << "OK" << std::endl; } -template <> -void copy_with_offdiagonals_1 () -{ - // this sparsity pattern doesn't have this - // function - deallog << "OK" << std::endl; -} - -template <> -void copy_with_offdiagonals_1 () -{ - // this sparsity pattern doesn't have this - // function - deallog << "OK" << std::endl; -} @@ -225,7 +203,7 @@ void copy_with_offdiagonals_2 () template <> -void copy_with_offdiagonals_2 () +void copy_with_offdiagonals_2 () { // this sparsity pattern doesn't have this // function @@ -234,25 +212,6 @@ void copy_with_offdiagonals_2 () -template <> -void copy_with_offdiagonals_2 () -{ - // this sparsity pattern doesn't have this - // function - deallog << "OK" << std::endl; -} - - - -template <> -void copy_with_offdiagonals_2 () -{ - // this sparsity pattern doesn't have this - // function - deallog << "OK" << std::endl; -} - - void do_copy_from (const std::list > > &sparsity, @@ -274,49 +233,11 @@ do_copy_from (const std::list > } -template -void -do_copy_from (const CompressedSparsityPattern &sparsity, - SP &sp4) -{ - std::list > > sparsity_x; - for (unsigned int i=0; i >()); - - for (unsigned int j=0; j void -do_copy_from (const CompressedSimpleSparsityPattern &sparsity, - SP &sp4) -{ - std::list > > sparsity_x; - for (unsigned int i=0; i >()); - - for (unsigned int j=0; j -void -do_copy_from (const CompressedSetSparsityPattern &sparsity, +do_copy_from (const DynamicSparsityPattern &sparsity, SP &sp4) { std::list > > sparsity_x; @@ -513,16 +434,7 @@ void matrix_position () template <> -void matrix_position () -{ - // this class doesn't have that function - deallog << "OK" << std::endl; -} - - - -template <> -void matrix_position () +void matrix_position () { // this class doesn't have that function deallog << "OK" << std::endl; @@ -530,13 +442,6 @@ void matrix_position () -template <> -void matrix_position () -{ - // this class doesn't have that function - deallog << "OK" << std::endl; -} - template @@ -574,7 +479,7 @@ void block_read_write () template <> -void block_read_write () +void block_read_write () { // not implemented for this sparsity // pattern @@ -583,25 +488,6 @@ void block_read_write () -template <> -void block_read_write () -{ - // not implemented for this sparsity - // pattern - deallog << "OK" << std::endl; -} - - - -template <> -void block_read_write () -{ - // not implemented for this sparsity - // pattern - deallog << "OK" << std::endl; -} - - template void test_index_set (const bool contiguous) -- 2.39.5