From 685758a376a02959df01a53909977805942da62d Mon Sep 17 00:00:00 2001 From: Wolfgang Bangerth Date: Tue, 18 May 2004 23:23:44 +0000 Subject: [PATCH] Improve the algorithm in compute_CuthillMcKee to avoid excessive memory usage in 3d. git-svn-id: https://svn.dealii.org/trunk@9263 0785d39b-7218-0410-832d-ea1e28bc413d --- .../deal.II/source/dofs/dof_renumbering.cc | 48 +++++++++++++++---- deal.II/doc/news/c-4-0.html | 24 +++++++--- 2 files changed, 58 insertions(+), 14 deletions(-) diff --git a/deal.II/deal.II/source/dofs/dof_renumbering.cc b/deal.II/deal.II/source/dofs/dof_renumbering.cc index befe26f954..87e9bb7686 100644 --- a/deal.II/deal.II/source/dofs/dof_renumbering.cc +++ b/deal.II/deal.II/source/dofs/dof_renumbering.cc @@ -19,6 +19,7 @@ // of numbers. Simple task. #include +#include #include #include #include @@ -127,19 +128,48 @@ DoFRenumbering::compute_Cuthill_McKee ( const bool use_constraints, const std::vector& starting_indices) { - // make the connection graph - SparsityPattern sparsity (dof_handler.n_dofs(), - dof_handler.max_couplings_between_dofs()); - DoFTools::make_sparsity_pattern (dof_handler, sparsity); - + // make the connection graph. in + // more than 2d use an intermediate + // compressed sparsity pattern + // since the we don't have very + // good estimates for + // max_couplings_between_dofs() in + // 3d and this then leads to + // excessive memory consumption + // + // note that if constraints are not + // requested, then the + // 'constraints' object will be + // empty, and calling condense with + // it is a no-op + ConstraintMatrix constraints; if (use_constraints) { - ConstraintMatrix constraints; DoFTools::make_hanging_node_constraints (dof_handler, constraints); constraints.close (); - constraints.condense (sparsity); - }; + } + SparsityPattern sparsity; + if (dim <= 2) + { + sparsity.reinit (dof_handler.n_dofs(), + dof_handler.n_dofs(), + dof_handler.max_couplings_between_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, sparsity); + constraints.condense (sparsity); + } + else + { + CompressedSparsityPattern csp (dof_handler.n_dofs(), + dof_handler.n_dofs()); + DoFTools::make_sparsity_pattern (dof_handler, csp); + constraints.condense (csp); + sparsity.copy_from (csp); + } + + // constraints are not needed anymore + constraints.clear (); + const unsigned int n_dofs = sparsity.n_rows(); // store the new dof numbers; invalid_dof_index means // that no new number was chosen yet @@ -334,6 +364,8 @@ void DoFRenumbering::Cuthill_McKee ( const bool reversed_numbering, const std::vector &starting_indices) { +//TODO: we should be doing the same here as in the other compute_CMK function to preserve some memory + // make the connection graph SparsityPattern sparsity (dof_handler.n_dofs(level), dof_handler.max_couplings_between_dofs()); diff --git a/deal.II/doc/news/c-4-0.html b/deal.II/doc/news/c-4-0.html index f611b2eb89..a7be4f269d 100644 --- a/deal.II/doc/news/c-4-0.html +++ b/deal.II/doc/news/c-4-0.html @@ -631,16 +631,28 @@ inconvenience this causes.

deal.II

    +
  1. Improved: The DoFTools::compute_Cuthill_McKee function + needs to build a sparsity pattern for its operations, and uses + the DoFHandler::max_couplings_per_dof + function for this. However, the estimates returned by the + latter function are rather bad in 3d, leading to excessive + memory allocation in the Cuthill McKee algorithm in 3d. This is + fixed by using an intermediate compressed sparsity pattern + instead if we are in 3d. +
    + (WB 2004/05/18) +

  2. Improved: Triangulation has - functions n_faces and n_active_faces, globally as well as by level, - similar to n_cells. -
    - (GK 2004/05/18) + functions n_faces and n_active_faces, globally as well as by level, + similar to n_cells. +
    + (GK 2004/05/18)

    -
  3. New: Added support for gmsh mesh format in