From e3ae3a45f2059c5815a4a5d777cc0377c34f6e00 Mon Sep 17 00:00:00 2001 From: bangerth Date: Wed, 5 Mar 2008 03:39:44 +0000 Subject: [PATCH] Initiate an implementation of some of the reordering algorithms using the Boost Graph library. The bandwidth of resulting matrices with their Cuthill-McKee algorithm is often significantly smaller. On step-22, this leads to the fact that the inner solver for the Schur complement, when using the ILU of the Laplace matrix, uses only about 48 iterations in the third refinement cycle, as compared to some 53 or 54 with our own algorithm. git-svn-id: https://svn.dealii.org/trunk@15856 0785d39b-7218-0410-832d-ea1e28bc413d --- .../deal.II/include/dofs/dof_renumbering.h | 53 +++++++++ .../deal.II/source/dofs/dof_renumbering.cc | 104 +++++++++++++++++- 2 files changed, 156 insertions(+), 1 deletion(-) diff --git a/deal.II/deal.II/include/dofs/dof_renumbering.h b/deal.II/deal.II/include/dofs/dof_renumbering.h index 4018bf0407..14ef002a63 100644 --- a/deal.II/deal.II/include/dofs/dof_renumbering.h +++ b/deal.II/deal.II/include/dofs/dof_renumbering.h @@ -213,6 +213,59 @@ DEAL_II_NAMESPACE_OPEN class DoFRenumbering { public: + /** + * A namespace for the + * implementation of some + * renumbering algorithms based + * on algorithms implemented in + * the Boost Graph Library (BGL) + * by Jeremy Siek and others. + * + * While often slight slower to + * compute, the algorithms using + * often lead to matrices with + * smaller bandwidths and sparse + * ILUs based on this numbering + * are therefore more efficient. + */ + class boost + { + public: + /** + * Renumber the degrees of + * freedom according to the + * Cuthill-McKee method, + * eventually using the reverse + * numbering scheme. + * + * See the general + * documentation of the + * parent class for details + * on the different methods. + */ + template + static void + Cuthill_McKee (DH& dof_handler, + const bool reversed_numbering = false, + const bool use_constraints = false); + + /** + * Computes the renumbering + * vector needed by the + * Cuthill_McKee() function. Does + * not perform the renumbering on + * the DoFHandler dofs but + * returns the renumbering + * vector. + */ + template + static void + compute_Cuthill_McKee (std::vector& new_dof_indices, + const DH&, + const bool reversed_numbering = false, + const bool use_constraints = false); + }; + /** * Renumber the degrees of * freedom according to the diff --git a/deal.II/deal.II/source/dofs/dof_renumbering.cc b/deal.II/deal.II/source/dofs/dof_renumbering.cc index f7b73d35f2..d371bee864 100644 --- a/deal.II/deal.II/source/dofs/dof_renumbering.cc +++ b/deal.II/deal.II/source/dofs/dof_renumbering.cc @@ -2,7 +2,7 @@ // $id$ // Version: $name$ // -// Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 by the deal.II authors +// Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 by the deal.II authors // // This file is subject to QPL and may not be distributed // without copyright and license information. Please refer @@ -35,6 +35,13 @@ #include #include +#include +#include +#include +#include "boost/graph/minimum_degree_ordering.hpp" +#include +#include + #include #include #include @@ -141,6 +148,98 @@ struct CompareDownstream }; +namespace types +{ + using namespace boost; + using namespace std; + + typedef vecS x; + + typedef adjacency_list > > Graph; + typedef graph_traits::vertex_descriptor Vertex; + typedef graph_traits::vertices_size_type size_type; + + typedef std::pair Pair; +} + + +namespace +{ + template + void create_graph (const DH &dof_handler, + const bool use_constraints, + types::Graph &graph, + types::property_map::type &graph_degree) + { + Assert (use_constraints == false, ExcNotImplemented()); + + std::vector dofs_on_this_cell; + dofs_on_this_cell.reserve (DoFTools::max_dofs_per_cell(dof_handler)); + typename DH::active_cell_iterator cell = dof_handler.begin_active(), + endc = dof_handler.end(); + for (; cell!=endc; ++cell) + { + const unsigned int dofs_per_cell = cell->get_fe().dofs_per_cell; + dofs_on_this_cell.resize (dofs_per_cell); + cell->get_dof_indices (dofs_on_this_cell); + + for (unsigned int i=0; i::vertex_iterator ui, ui_end; + + graph_degree = get(boost::vertex_degree, graph); + for (boost::tie(ui, ui_end) = vertices(graph); ui != ui_end; ++ui) + graph_degree[*ui] = degree(*ui, graph); + + } +} + + +template +void +DoFRenumbering::boost:: +Cuthill_McKee (DH& dof_handler, + const bool reversed_numbering, + const bool use_constraints) +{ + types::Graph + graph(dof_handler.n_dofs()); + types::property_map::type + graph_degree; + + create_graph (dof_handler, use_constraints, graph, graph_degree); + + types::property_map::type + index_map = get(::boost::vertex_index, graph); + + + std::vector inv_perm(num_vertices(graph)); + + if (reversed_numbering == false) + ::boost::cuthill_mckee_ordering(graph, inv_perm.rbegin(), + get(::boost::vertex_color, graph), + make_degree_map(graph)); + else + ::boost::cuthill_mckee_ordering(graph, inv_perm.begin(), + get(::boost::vertex_color, graph), + make_degree_map(graph)); + + std::vector perm(num_vertices(graph)); + for (types::size_type c = 0; c != inv_perm.size(); ++c) + perm[index_map[inv_perm[c]]] = c; + + dof_handler.renumber_dofs (perm); +} + + + + template void @@ -1520,6 +1619,9 @@ compute_subdomain_wise (std::vector &new_dof_indices, // explicit instantiations +template void DoFRenumbering::boost::Cuthill_McKee (DoFHandler &, bool, bool); + + template void DoFRenumbering::Cuthill_McKee > (DoFHandler&, -- 2.39.5