From 685758a376a02959df01a53909977805942da62d Mon Sep 17 00:00:00 2001
From: Wolfgang Bangerth <bangerth@math.tamu.edu>
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 <lac/sparsity_pattern.h>
+#include <lac/compressed_sparsity_pattern.h>
 #include <dofs/dof_accessor.h>
 #include <grid/tria_iterator.h>
 #include <grid/tria.h>
@@ -127,19 +128,48 @@ DoFRenumbering::compute_Cuthill_McKee (
   const bool                 use_constraints,
   const std::vector<unsigned int>& 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<unsigned int> &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.
 <h3>deal.II</h3>
 
 <ol>
+  <li> <p> Improved: The <code
+       class="member">DoFTools::compute_Cuthill_McKee</code> function
+       needs to build a sparsity pattern for its operations, and uses
+       the <code
+       class="member">DoFHandler::max_couplings_per_dof</code>
+       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.
+       <br>
+       (WB 2004/05/18)
+  </p>
 
   <li> <p> Improved: <code class="class">Triangulation</code> has
-  functions <code class="member">n_faces</code> and <code
-  class="member">n_active_faces</code>, globally as well as by level,
-  similar to <code class="member">n_cells</code>.
-  <br>
-  (GK 2004/05/18)
+       functions <code class="member">n_faces</code> and <code
+       class="member">n_active_faces</code>, globally as well as by level,
+       similar to <code class="member">n_cells</code>.
+       <br>
+       (GK 2004/05/18)
   </p>
 
-
   <li> <p>
        New: Added support for <a href="http://www.geuz.org/gmsh/"
        target="_top">gmsh</a> mesh format in <code
-- 
2.39.5