From ab07dff39e518f64e96cec5b9d9b9e0101ca8fb5 Mon Sep 17 00:00:00 2001
From: wolf
Date: Mon, 8 Mar 2004 22:24:59 +0000
Subject: [PATCH] Detect and use METIS to partition triangulations.
git-svn-id: https://svn.dealii.org/trunk@8681 0785d39b-7218-0410-832d-ea1e28bc413d
---
deal.II/aclocal.m4 | 57 ++++
deal.II/base/include/base/config.h.in | 3 +
deal.II/configure | 69 +++-
deal.II/configure.in | 4 +
deal.II/deal.II/include/grid/grid_tools.h | 37 ++-
deal.II/deal.II/source/grid/grid_tools.cc | 90 +++++-
deal.II/doc/development/Makefile | 4 +
deal.II/doc/development/makefiles.1.html | 51 ++-
deal.II/lac/include/lac/sparsity_pattern.h | 78 ++++-
deal.II/lac/source/sparsity_pattern.cc | 80 +++++
tests/bits/metis_01.cc | 92 ++++++
.../bits/metis_01.output | 295 ++++++++++++++++++
12 files changed, 849 insertions(+), 11 deletions(-)
create mode 100644 tests/bits/metis_01.cc
create mode 100644 tests/results/i686-pc-linux-gnu+gcc3.2/bits/metis_01.output
diff --git a/deal.II/aclocal.m4 b/deal.II/aclocal.m4
index e63ca75f0f..44813481a5 100644
--- a/deal.II/aclocal.m4
+++ b/deal.II/aclocal.m4
@@ -3717,3 +3717,60 @@ AC_DEFUN(DEAL_II_CONFIGURE_PETSC, dnl
])
fi
])
+
+
+
+dnl ------------------------------------------------------------
+dnl Check whether Metis is installed, and if so store the
+dnl respective links
+dnl
+dnl Usage: DEAL_II_CONFIGURE_METIS
+dnl
+dnl ------------------------------------------------------------
+AC_DEFUN(DEAL_II_CONFIGURE_METIS, dnl
+[
+ dnl First check for the Metis directory
+ AC_MSG_CHECKING(for Metis library directory)
+
+ AC_ARG_WITH(metis,
+ [ --with-metis=/path/to/metis Specify the path to the Metis installation,
+ of which the include and library directories
+ are subdirs; use this if you want to
+ override the METIS_DIR environment variable],
+ [
+ USE_CONTRIB_METIS=yes
+ DEAL_II_METIS_DIR=$withval
+ AC_MSG_RESULT($DEAL_II_METIS_DIR)
+
+ dnl Make sure that what was specified is actually correct
+ if test ! -d $DEAL_II_METIS_DIR/Lib ; then
+ AC_MSG_ERROR([Path to Metis specified with --with-metis does not
+ point to a complete Metis installation])
+ fi
+ ],
+ [
+ dnl Take something from the environment variables, if it is there
+ if test "x$METIS_DIR" != "x" ; then
+ USE_CONTRIB_METIS=yes
+ DEAL_II_METIS_DIR="$METIS_DIR"
+ AC_MSG_RESULT($DEAL_II_METIS_DIR)
+
+ dnl Make sure that what this is actually correct
+ if test ! -d $DEAL_II_METIS_DIR/include \
+ -o ! -d $DEAL_II_METIS_DIR/lib ; then
+ AC_MSG_ERROR([The path to Metis specified in the METIS_DIR
+ environment variable does not
+ point to a complete Metis installation])
+ fi
+ else
+ USE_CONTRIB_METIS=no
+ DEAL_II_METIS_DIR=""
+ AC_MSG_RESULT(not found)
+ fi
+ ])
+ if test "$USE_CONTRIB_METIS" = "yes" ; then
+ AC_DEFINE(DEAL_II_USE_METIS, 1,
+ [Defined if a Metis installation was found and is going
+ to be used])
+ fi
+])
diff --git a/deal.II/base/include/base/config.h.in b/deal.II/base/include/base/config.h.in
index 865c05391f..cfcbb62c4d 100644
--- a/deal.II/base/include/base/config.h.in
+++ b/deal.II/base/include/base/config.h.in
@@ -164,6 +164,9 @@
provided by the compiler. */
#undef DEAL_II_USE_DIRECT_ERRNO_H
+/* Defined if a Metis installation was found and is going to be used */
+#undef DEAL_II_USE_METIS
+
/* Flag indicating whether the library shall be compiled for multithreaded
applications. If so, then it is set to one, otherwise to zero. */
#undef DEAL_II_USE_MT
diff --git a/deal.II/configure b/deal.II/configure
index cd87a4a653..0e4f390e0f 100755
--- a/deal.II/configure
+++ b/deal.II/configure
@@ -1,5 +1,5 @@
#! /bin/sh
-# From configure.in Revision: 1.163 .
+# From configure.in Revision.
# Guess values for system-dependent variables and create Makefiles.
# Generated by GNU Autoconf 2.57.
#
@@ -273,7 +273,7 @@ PACKAGE_BUGREPORT=
ac_unique_file="deal.II"
ac_subdirs_all="$ac_subdirs_all contrib tests"
-ac_subst_vars='SHELL PATH_SEPARATOR PACKAGE_NAME PACKAGE_TARNAME PACKAGE_VERSION PACKAGE_STRING PACKAGE_BUGREPORT exec_prefix prefix program_transform_name bindir sbindir libexecdir datadir sysconfdir sharedstatedir localstatedir libdir includedir oldincludedir infodir mandir build_alias host_alias target_alias DEFS ECHO_C ECHO_N ECHO_T LIBS DEAL_II_VERSION DEAL_II_MAJOR DEAL_II_MINOR DEAL_II_PATH DEAL2_DIR build build_cpu build_vendor build_os host host_cpu host_vendor host_os target target_cpu target_vendor target_os CC CFLAGS LDFLAGS CPPFLAGS ac_ct_CC EXEEXT OBJEXT CXX CXXFLAGS ac_ct_CXX GXX_VERSION CXXFLAGSG CXXFLAGSO CXXFLAGSPIC SHLIBLD LDFLAGSPIC enablemultithreading withmultithreading F77 F77_VERSION F77FLAGSO F77FLAGSG F77FLAGSPIC F77LIBS enableshared lib_suffix AR RANLIB ac_ct_RANLIB enablemultigrid TECPLOT_LIBRARY_PATH TECPLOT_INCLUDE_PATH USE_CONTRIB_HSL USE_CONTRIB_PETSC DEAL_II_PETSC_DIR DEAL_II_PETSC_ARCH kdocdir kdocversion DOXYGEN PERL subdirs LIBOBJS LTLIBOBJS'
+ac_subst_vars='SHELL PATH_SEPARATOR PACKAGE_NAME PACKAGE_TARNAME PACKAGE_VERSION PACKAGE_STRING PACKAGE_BUGREPORT exec_prefix prefix program_transform_name bindir sbindir libexecdir datadir sysconfdir sharedstatedir localstatedir libdir includedir oldincludedir infodir mandir build_alias host_alias target_alias DEFS ECHO_C ECHO_N ECHO_T LIBS DEAL_II_VERSION DEAL_II_MAJOR DEAL_II_MINOR DEAL_II_PATH DEAL2_DIR build build_cpu build_vendor build_os host host_cpu host_vendor host_os target target_cpu target_vendor target_os CC CFLAGS LDFLAGS CPPFLAGS ac_ct_CC EXEEXT OBJEXT CXX CXXFLAGS ac_ct_CXX GXX_VERSION CXXFLAGSG CXXFLAGSO CXXFLAGSPIC SHLIBLD LDFLAGSPIC enablemultithreading withmultithreading F77 F77_VERSION F77FLAGSO F77FLAGSG F77FLAGSPIC F77LIBS enableshared lib_suffix AR RANLIB ac_ct_RANLIB enablemultigrid TECPLOT_LIBRARY_PATH TECPLOT_INCLUDE_PATH USE_CONTRIB_HSL USE_CONTRIB_PETSC DEAL_II_PETSC_DIR DEAL_II_PETSC_ARCH USE_CONTRIB_METIS DEAL_II_METIS_DIR kdocdir kdocversion DOXYGEN PERL subdirs LIBOBJS LTLIBOBJS'
ac_subst_files=''
# Initialize some variables set by options.
@@ -833,6 +833,10 @@ Optional Packages:
installation; use this if you want to
override the PETSC_ARCH environment
variable
+ --with-metis=/path/to/metis Specify the path to the Metis installation,
+ of which the include and library directories
+ are subdirs; use this if you want to
+ override the METIS_DIR environment variable
--with-cpu=cpu Optimize specifically for the given CPU type,
rather than just generating code for this
processor family
@@ -7811,6 +7815,65 @@ fi;
+ echo "$as_me:$LINENO: checking for Metis library directory" >&5
+echo $ECHO_N "checking for Metis library directory... $ECHO_C" >&6
+
+
+# Check whether --with-metis or --without-metis was given.
+if test "${with_metis+set}" = set; then
+ withval="$with_metis"
+
+ USE_CONTRIB_METIS=yes
+ DEAL_II_METIS_DIR=$withval
+ echo "$as_me:$LINENO: result: $DEAL_II_METIS_DIR" >&5
+echo "${ECHO_T}$DEAL_II_METIS_DIR" >&6
+
+ if test ! -d $DEAL_II_METIS_DIR/Lib ; then
+ { { echo "$as_me:$LINENO: error: Path to Metis specified with --with-metis does not
+ point to a complete Metis installation" >&5
+echo "$as_me: error: Path to Metis specified with --with-metis does not
+ point to a complete Metis installation" >&2;}
+ { (exit 1); exit 1; }; }
+ fi
+
+else
+
+ if test "x$METIS_DIR" != "x" ; then
+ USE_CONTRIB_METIS=yes
+ DEAL_II_METIS_DIR="$METIS_DIR"
+ echo "$as_me:$LINENO: result: $DEAL_II_METIS_DIR" >&5
+echo "${ECHO_T}$DEAL_II_METIS_DIR" >&6
+
+ if test ! -d $DEAL_II_METIS_DIR/include \
+ -o ! -d $DEAL_II_METIS_DIR/lib ; then
+ { { echo "$as_me:$LINENO: error: The path to Metis specified in the METIS_DIR
+ environment variable does not
+ point to a complete Metis installation" >&5
+echo "$as_me: error: The path to Metis specified in the METIS_DIR
+ environment variable does not
+ point to a complete Metis installation" >&2;}
+ { (exit 1); exit 1; }; }
+ fi
+ else
+ USE_CONTRIB_METIS=no
+ DEAL_II_METIS_DIR=""
+ echo "$as_me:$LINENO: result: not found" >&5
+echo "${ECHO_T}not found" >&6
+ fi
+
+fi;
+ if test "$USE_CONTRIB_METIS" = "yes" ; then
+
+cat >>confdefs.h <<\_ACEOF
+#define DEAL_II_USE_METIS 1
+_ACEOF
+
+ fi
+
+
+
+
+
echo "$as_me:$LINENO: result: " >&5
@@ -8765,6 +8828,8 @@ s,@USE_CONTRIB_HSL@,$USE_CONTRIB_HSL,;t t
s,@USE_CONTRIB_PETSC@,$USE_CONTRIB_PETSC,;t t
s,@DEAL_II_PETSC_DIR@,$DEAL_II_PETSC_DIR,;t t
s,@DEAL_II_PETSC_ARCH@,$DEAL_II_PETSC_ARCH,;t t
+s,@USE_CONTRIB_METIS@,$USE_CONTRIB_METIS,;t t
+s,@DEAL_II_METIS_DIR@,$DEAL_II_METIS_DIR,;t t
s,@kdocdir@,$kdocdir,;t t
s,@kdocversion@,$kdocversion,;t t
s,@DOXYGEN@,$DOXYGEN,;t t
diff --git a/deal.II/configure.in b/deal.II/configure.in
index 3ae1b2bb3b..6c479d0387 100644
--- a/deal.II/configure.in
+++ b/deal.II/configure.in
@@ -342,6 +342,10 @@ AC_SUBST(USE_CONTRIB_PETSC)
AC_SUBST(DEAL_II_PETSC_DIR)
AC_SUBST(DEAL_II_PETSC_ARCH)
+DEAL_II_CONFIGURE_METIS
+AC_SUBST(USE_CONTRIB_METIS)
+AC_SUBST(DEAL_II_METIS_DIR)
+
dnl -------------------------------------------------------------
diff --git a/deal.II/deal.II/include/grid/grid_tools.h b/deal.II/deal.II/include/grid/grid_tools.h
index 6623d7ae3f..8ffa04747c 100644
--- a/deal.II/deal.II/include/grid/grid_tools.h
+++ b/deal.II/deal.II/include/grid/grid_tools.h
@@ -2,7 +2,7 @@
// $Id$
// Version: $Name$
//
-// Copyright (C) 2001, 2002, 2003 by the deal.II authors
+// Copyright (C) 2001, 2002, 2003, 2004 by the deal.II authors
//
// This file is subject to QPL and may not be distributed
// without copyright and license information. Please refer
@@ -28,7 +28,7 @@
* cell that contains a given point. See the descriptions of the
* individual functions for more information.
*
- * @author Wolfgang Bangerth, 2001, 2003
+ * @author Wolfgang Bangerth, 2001, 2003, 2004
*/
class GridTools
{
@@ -233,7 +233,38 @@ class GridTools
typename Container::active_cell_iterator
find_active_cell_around_point (const Container &container,
const Point &p);
-
+
+ /**
+ * Use the METIS partitioner to generate
+ * a partitioning of the active cells
+ * making up the entire domain. After
+ * calling this function, the subdomain
+ * ids of all active cells will have
+ * values between zero and
+ * @p{n_partitions-1}. You can access the
+ * subdomain id of a cell by using
+ * @p{cell->subdomain_id()}.
+ *
+ * This function will generate an error
+ * if METIS is not installed unless
+ * @p{n_partitions} is one. I.e., you can
+ * write a program so that it runs in the
+ * single-processor single-partition case
+ * without METIS installed, and only
+ * requires METIS when multiple
+ * partitions are required.
+ */
+ template
+ static
+ void partition_triangulation (Triangulation &triangulation,
+ const unsigned int n_partitions);
+ /**
+ * Exception
+ */
+ DeclException1 (ExcInvalidNumberOfPartitions,
+ int,
+ << "The number of partitions you gave is " << arg1
+ << ", but must be greater than zero.");
/**
* Exception
*/
diff --git a/deal.II/deal.II/source/grid/grid_tools.cc b/deal.II/deal.II/source/grid/grid_tools.cc
index 874b445376..66b0ef18db 100644
--- a/deal.II/deal.II/source/grid/grid_tools.cc
+++ b/deal.II/deal.II/source/grid/grid_tools.cc
@@ -2,7 +2,7 @@
// $Id$
// Version: $Name$
//
-// Copyright (C) 2001, 2002, 2003 by the deal.II authors
+// Copyright (C) 2001, 2002, 2003, 2004 by the deal.II authors
//
// This file is subject to QPL and may not be distributed
// without copyright and license information. Please refer
@@ -17,8 +17,12 @@
#include
#include
#include
+#include
+#include
#include
#include
+#include
+#include
#include
#include
@@ -238,6 +242,85 @@ GridTools::find_active_cell_around_point (const Container &container,
+template
+void
+GridTools::
+partition_triangulation (Triangulation &triangulation,
+ const unsigned int n_partitions)
+{
+ Assert (n_partitions > 0, ExcInvalidNumberOfPartitions(n_partitions));
+
+ // check for an easy return
+ if (n_partitions == 1)
+ {
+ for (typename Triangulation::active_cell_iterator
+ cell = triangulation.begin_active();
+ cell != triangulation.end(); ++cell)
+ cell->set_subdomain_id (0);
+ return;
+ }
+
+ // we decompose the domain by first
+ // generating the connection graph of all
+ // cells with their neighbors, and then
+ // passing this graph off to METIS. To make
+ // things a little simpler and more
+ // general, we let the function
+ // DoFTools:make_flux_sparsity_pattern
+ // function generate the connection graph
+ // for us and reuse the SparsityPattern
+ // data structure for the connection
+ // graph. The connection structure of the
+ // mesh is obtained by using a fake
+ // piecewise constant finite element
+ //
+ // Since in 3d the generation of a
+ // sparsity pattern can be expensive, we
+ // take the detour of the compressed
+ // sparsity pattern, which is a little
+ // slower but more efficient in terms of
+ // memory
+ FE_DGQ fake_q0(0);
+ DoFHandler dof_handler (triangulation);
+ dof_handler.distribute_dofs (fake_q0);
+ Assert (dof_handler.n_dofs() == triangulation.n_active_cells(),
+ ExcInternalError());
+
+ CompressedSparsityPattern csp (dof_handler.n_dofs(),
+ dof_handler.n_dofs());
+ DoFTools::make_flux_sparsity_pattern (dof_handler, csp);
+
+ SparsityPattern sparsity_pattern;
+ sparsity_pattern.copy_from (csp);
+
+ // partition this connection graph and get
+ // back a vector of indices, one per degree
+ // of freedom (which is associated with a
+ // cell)
+ std::vector partition_indices (triangulation.n_active_cells());
+ sparsity_pattern.partition (n_partitions, partition_indices);
+
+ // finally loop over all cells and set the
+ // subdomain ids. for this, get the DoF
+ // index of each cell and extract the
+ // subdomain id from the vector obtained
+ // above
+ std::vector dof_indices(1);
+ for (typename DoFHandler::active_cell_iterator
+ cell = dof_handler.begin_active();
+ cell != dof_handler.end(); ++cell)
+ {
+ cell->get_dof_indices(dof_indices);
+ Assert (dof_indices[0] < triangulation.n_active_cells(),
+ ExcInternalError());
+ Assert (partition_indices[dof_indices[0]] < n_partitions,
+ ExcInternalError());
+
+ cell->set_subdomain_id (partition_indices[dof_indices[0]]);
+ }
+}
+
+
#if deal_II_dimension != 1
template
@@ -267,3 +350,8 @@ template
MGDoFHandler::active_cell_iterator
GridTools::find_active_cell_around_point (const MGDoFHandler &,
const Point &p);
+
+template
+void
+GridTools::partition_triangulation (Triangulation &,
+ const unsigned int);
diff --git a/deal.II/doc/development/Makefile b/deal.II/doc/development/Makefile
index ff279d1f6a..1b86652764 100644
--- a/deal.II/doc/development/Makefile
+++ b/deal.II/doc/development/Makefile
@@ -27,6 +27,8 @@ makefiles.html: Makefile makefiles.1.html $D/common/Make.global_options makefile
@echo 'USE_CONTRIB_PETSC=$(USE_CONTRIB_PETSC)
' >> $@
@echo 'DEAL_II_PETSC_DIR=$(DEAL_II_PETSC_DIR)
' >> $@
@echo 'DEAL_II_PETSC_ARCH=$(DEAL_II_PETSC_ARCH)
' >> $@
+ @echo 'USE_CONTRIB_METIS=$(USE_CONTRIB_METIS)
' >> $@
+ @echo 'DEAL_II_METIS_DIR=$(DEAL_II_METIS_DIR)
' >> $@
@echo 'lib-path-base=$(lib-path-base)
' >> $@
@echo 'lib-path-lac=$(lib-path-lac)
' >> $@
@echo 'lib-path-deal2=$(lib-path-deal2)
' >> $@
@@ -45,6 +47,7 @@ makefiles.html: Makefile makefiles.1.html $D/common/Make.global_options makefile
@echo 'lib-contrib-hsl=$(lib-contrib-hsl)
' >> $@
@echo 'lib-contrib-petsc.g=$(lib-contrib-petsc.g)
' >> $@
@echo 'lib-contrib-petsc.o=$(lib-contrib-petsc.o)
' >> $@
+ @echo 'lib-contrib-metis=$(lib-contrib-metis)
' >> $@
@echo 'include-path-base=$(include-path-base)
' >> $@
@echo 'include-path-lac=$(include-path-lac)
' >> $@
@echo 'include-path-deal2=$(include-path-deal2)
' >> $@
@@ -52,6 +55,7 @@ makefiles.html: Makefile makefiles.1.html $D/common/Make.global_options makefile
@echo 'include-path-contrib-petsc=$(include-path-contrib-petsc)
' >> $@
@echo 'include-path-contrib-petsc-bmake=$(include-path-contrib-petsc-bmake)
' >> $@
@echo 'include-path-contrib-petsc-mpi=$(include-path-contrib-petsc-mpi)
' >> $@
+ @echo 'include-path-contrib-metis=$(include-path-contrib-metis)
' >> $@
@echo 'INCLUDE=$(INCLUDE)
' >> $@
@echo 'CXXFLAGS.g=$(CXXFLAGS.g)
' >> $@
@echo 'CXXFLAGS.o=$(CXXFLAGS.o)
' >> $@
diff --git a/deal.II/doc/development/makefiles.1.html b/deal.II/doc/development/makefiles.1.html
index 1dcb6c2b71..149b4f983f 100644
--- a/deal.II/doc/development/makefiles.1.html
+++ b/deal.II/doc/development/makefiles.1.html
@@ -210,6 +210,28 @@
upon configuration of the deal.II library.
+
+
+ USE_CONTRIB_METIS
+
+ yes
indicates whether the METIS library has been
+ detected upon configuration, and whether we shall interface with
+ it. no
otherwise. (See the
+ ReadMe
+ file for more information on installation of METIS.)
+
+
+
+
+ DEAL_II_METIS_DIR
+
+ If USE_CONTRIB_METIS
is yes
, then this
+ variable has the path to the METIS library, as either given by the
+ METIS_DIR
environment variable, or the
+ --with-metis
switch on the command line upon
+ configuration of the deal.II library.
+
+
@@ -321,6 +343,16 @@
file for more information on installation of PETSc.)
+
+ lib-contrib-metis
+
+ Path and name of the METIS libraries, if
+ found and used at configuration time.
+ (See the
+ ReadMe
+ file for more information on installation of METIS.)
+
+
@@ -349,6 +381,14 @@
+ include-path-deal2
+
+ Same for the /deal.II library. Include files are in
+ $(include-path-deal2)/*
.
+
+
+
+
include-path-contrib-hsl
If some HSL files are
@@ -377,11 +417,14 @@
- include-path-deal2
+ include-path-contrib-metis
+
- Same for the /deal.II library. Include files are in
- $(include-path-deal2)/*
.
-
+ If METIS is used, then this variable has the path to the METIS
+ include files. (See the
+ ReadMe
+ file for more information on installation of METIS.)
+
diff --git a/deal.II/lac/include/lac/sparsity_pattern.h b/deal.II/lac/include/lac/sparsity_pattern.h
index b8ad6e0755..a92886edf3 100644
--- a/deal.II/lac/include/lac/sparsity_pattern.h
+++ b/deal.II/lac/include/lac/sparsity_pattern.h
@@ -731,6 +731,65 @@ class SparsityPattern : public Subscriptor
*/
bool optimize_diagonal () const;
+ /**
+ * Use the METIS partitioner to generate
+ * a partitioning of the degrees of
+ * freedom represented by this sparsity
+ * pattern. In effect, we view this
+ * sparsity pattern as a graph of
+ * connections between various degrees of
+ * freedom, where each nonzero entry in
+ * the sparsity pattern corresponds to an
+ * edge between two nodes in the
+ * connection graph. The goal is then to
+ * decompose this graph into groups of
+ * nodes so that a minimal number of
+ * edges are cut by the boundaries
+ * between node groups. This partitioning
+ * is done by METIS. Note that METIS can
+ * only partition symmetric sparsity
+ * patterns, and that of course the
+ * sparsity pattern has to be square. We
+ * do not check for symmetry of the
+ * sparsity pattern, since this is an
+ * expensive operation, but rather leave
+ * this as the responsibility of caller
+ * of this function.
+ *
+ * After calling this function, the
+ * output array will have values between
+ * zero and @p{n_partitions-1} for each
+ * node (i.e. row or column of the
+ * matrix).
+ *
+ * This function will generate an error
+ * if METIS is not installed unless
+ * @p{n_partitions} is one. I.e., you can
+ * write a program so that it runs in the
+ * single-processor single-partition case
+ * without METIS installed, and only
+ * requires METIS when multiple
+ * partitions are required.
+ *
+ * Note that the sparsity pattern itself
+ * is not changed by calling this
+ * function. However, you will likely use
+ * the information generated by calling
+ * this function to renumber degrees of
+ * freedom, after which you will of
+ * course have to regenerate the sparsity
+ * pattern.
+ *
+ * This function will rarely be called
+ * separately, since in finite element
+ * methods you will want to partition the
+ * mesh, not the matrix. This can be done
+ * by calling
+ * @p{GridTools::partition_triangulation}.
+ */
+ void partition (const unsigned int n_partitions,
+ std::vector &partition_indices) const;
+
/**
* Write the data of this object
* en bloc to a file. This is
@@ -928,7 +987,24 @@ class SparsityPattern : public Subscriptor
int, int,
<< "The iterators denote a range of " << arg1
<< " elements, but the given number of rows was " << arg2);
-
+ /**
+ * Exception
+ */
+ DeclException0 (ExcMETISNotInstalled);
+ /**
+ * Exception
+ */
+ DeclException1 (ExcInvalidNumberOfPartitions,
+ int,
+ << "The number of partitions you gave is " << arg1
+ << ", but must be greater than zero.");
+ /**
+ * Exception
+ */
+ DeclException2 (ExcInvalidArraySize,
+ int, int,
+ << "The array has size " << arg1 << " but should have size "
+ << arg2);
private:
/**
* Maximum number of rows that can
diff --git a/deal.II/lac/source/sparsity_pattern.cc b/deal.II/lac/source/sparsity_pattern.cc
index 74de399834..537617041e 100644
--- a/deal.II/lac/source/sparsity_pattern.cc
+++ b/deal.II/lac/source/sparsity_pattern.cc
@@ -23,6 +23,11 @@
#include
#include
+#ifdef DEAL_II_USE_METIS
+extern "C" {
+# include
+}
+#endif
const unsigned int SparsityPattern::invalid_entry;
@@ -899,6 +904,81 @@ SparsityPattern::memory_consumption () const
+void
+SparsityPattern::
+partition (const unsigned int n_partitions,
+ std::vector &partition_indices) const
+{
+ Assert (rows==cols, ExcNotQuadratic());
+ Assert (is_compressed(), ExcNotCompressed());
+
+ Assert (n_partitions > 0, ExcInvalidNumberOfPartitions(n_partitions));
+ Assert (partition_indices.size() == rows,
+ ExcInvalidArraySize (partition_indices.size(),rows));
+
+ // check for an easy return
+ if (n_partitions == 1)
+ {
+ std::fill_n (partition_indices.begin(), partition_indices.size(), 0U);
+ return;
+ }
+
+ // Make sure that METIS is actually
+ // installed and detected
+#ifndef DEAL_II_USE_METIS
+ AssertThrow (false, ExcMETISNotInstalled());
+#else
+
+ // generate the data structures for
+ // METIS. Note that this is particularly
+ // simple, since METIS wants exactly our
+ // compressed row storage format. we only
+ // have to set up a few auxiliary arrays
+ int
+ n = static_cast(rows),
+ wgtflag = 0, // no weights on nodes or edges
+ numflag = 0, // C-style 0-based numbering
+ nparts = static_cast(n_partitions), // number of subdomains to create
+ dummy; // the numbers of edges cut by the
+ // resulting partition
+
+ // use default options for METIS
+ int options[5] = { 0,0,0,0,0 };
+
+ // one more nuisance: we have to copy our
+ // own data to arrays that store signed
+ // integers :-(
+ std::vector int_rowstart (rowstart, rowstart+cols+1);
+ std::vector int_colnums (colnums, colnums+max_vec_len+1);
+
+ std::vector int_partition_indices (rows);
+
+ // Select which type of partitioning to create
+
+ // Use recursive if the number of
+ // partitions is less than or equal to 8
+ if (n_partitions <= 8)
+ METIS_PartGraphRecursive(&n, &int_rowstart[0], &int_colnums[0],
+ NULL, NULL,
+ &wgtflag, &numflag, &nparts, &options[0],
+ &dummy, &int_partition_indices[0]);
+
+ // Otherwise use kway
+ else
+ METIS_PartGraphKway(&n, &int_rowstart[0], &int_colnums[0],
+ NULL, NULL,
+ &wgtflag, &numflag, &nparts, &options[0],
+ &dummy, &int_partition_indices[0]);
+
+ // now copy back generated indices into the
+ // output array
+ std::copy (int_partition_indices.begin(),
+ int_partition_indices.end(),
+ partition_indices.begin());
+#endif
+}
+
+
// explicit instantiations
template void SparsityPattern::copy_from (const FullMatrix &, bool);
template void SparsityPattern::copy_from (const FullMatrix &, bool);
diff --git a/tests/bits/metis_01.cc b/tests/bits/metis_01.cc
new file mode 100644
index 0000000000..c2ab67ef42
--- /dev/null
+++ b/tests/bits/metis_01.cc
@@ -0,0 +1,92 @@
+//---------------------------- metis_01.cc ---------------------------
+// $Id$
+// Version: $Name$
+//
+// Copyright (C) 2004 by the deal.II authors
+//
+// This file is subject to QPL and may not be distributed
+// without copyright and license information. Please refer
+// to the file deal.II/doc/license.html for the text and
+// further information on this license.
+//
+//---------------------------- metis_01.cc ---------------------------
+
+
+// check GridTools::partition_triangulation
+
+#include "../tests.h"
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+
+
+template
+void test ()
+{
+ Triangulation triangulation;
+ GridGenerator::hyper_cube (triangulation);
+ triangulation.refine_global (5-dim);
+
+ // subdivide into 5 subdomains
+ deallog << "RECURSIVE" << std::endl;
+ GridTools::partition_triangulation (triangulation, 5);
+ for (typename Triangulation::active_cell_iterator
+ cell = triangulation.begin_active();
+ cell != triangulation.end(); ++cell)
+ deallog << cell << ' ' << cell->subdomain_id() << std::endl;
+
+ // subdivide into 9 subdomains. note that
+ // this uses the k-way subdivision (for
+ // more than 8 subdomains) rather than the
+ // recursive one
+ deallog << "K-WAY" << std::endl;
+ GridTools::partition_triangulation (triangulation, 9);
+ for (typename Triangulation::active_cell_iterator
+ cell = triangulation.begin_active();
+ cell != triangulation.end(); ++cell)
+ deallog << cell << ' ' << cell->subdomain_id() << std::endl;
+}
+
+
+
+int main ()
+{
+ std::ofstream logfile("metis_01.output");
+ deallog.attach(logfile);
+ deallog.depth_console(0);
+
+ try
+ {
+ test<1> ();
+ test<2> ();
+ test<3> ();
+ }
+ catch (std::exception &exc)
+ {
+ std::cerr << std::endl << std::endl
+ << "----------------------------------------------------"
+ << std::endl;
+ std::cerr << "Exception on processing: " << std::endl
+ << exc.what() << std::endl
+ << "Aborting!" << std::endl
+ << "----------------------------------------------------"
+ << std::endl;
+
+ return 1;
+ }
+ catch (...)
+ {
+ std::cerr << std::endl << std::endl
+ << "----------------------------------------------------"
+ << std::endl;
+ std::cerr << "Unknown exception!" << std::endl
+ << "Aborting!" << std::endl
+ << "----------------------------------------------------"
+ << std::endl;
+ return 1;
+ };
+}
diff --git a/tests/results/i686-pc-linux-gnu+gcc3.2/bits/metis_01.output b/tests/results/i686-pc-linux-gnu+gcc3.2/bits/metis_01.output
new file mode 100644
index 0000000000..e7491ad159
--- /dev/null
+++ b/tests/results/i686-pc-linux-gnu+gcc3.2/bits/metis_01.output
@@ -0,0 +1,295 @@
+
+DEAL::RECURSIVE
+DEAL::4.0 3
+DEAL::4.1 3
+DEAL::4.2 3
+DEAL::4.3 4
+DEAL::4.4 4
+DEAL::4.5 4
+DEAL::4.6 4
+DEAL::4.7 2
+DEAL::4.8 2
+DEAL::4.9 2
+DEAL::4.10 1
+DEAL::4.11 1
+DEAL::4.12 1
+DEAL::4.13 0
+DEAL::4.14 0
+DEAL::4.15 0
+DEAL::K-WAY
+DEAL::4.0 7
+DEAL::4.1 7
+DEAL::4.2 8
+DEAL::4.3 6
+DEAL::4.4 6
+DEAL::4.5 1
+DEAL::4.6 1
+DEAL::4.7 0
+DEAL::4.8 2
+DEAL::4.9 2
+DEAL::4.10 3
+DEAL::4.11 3
+DEAL::4.12 4
+DEAL::4.13 4
+DEAL::4.14 5
+DEAL::4.15 5
+DEAL::RECURSIVE
+DEAL::3.0 3
+DEAL::3.1 3
+DEAL::3.2 3
+DEAL::3.3 3
+DEAL::3.4 3
+DEAL::3.5 3
+DEAL::3.6 0
+DEAL::3.7 3
+DEAL::3.8 3
+DEAL::3.9 0
+DEAL::3.10 0
+DEAL::3.11 3
+DEAL::3.12 3
+DEAL::3.13 3
+DEAL::3.14 3
+DEAL::3.15 3
+DEAL::3.16 0
+DEAL::3.17 0
+DEAL::3.18 0
+DEAL::3.19 0
+DEAL::3.20 0
+DEAL::3.21 1
+DEAL::3.22 1
+DEAL::3.23 0
+DEAL::3.24 1
+DEAL::3.25 1
+DEAL::3.26 1
+DEAL::3.27 1
+DEAL::3.28 0
+DEAL::3.29 0
+DEAL::3.30 1
+DEAL::3.31 0
+DEAL::3.32 1
+DEAL::3.33 1
+DEAL::3.34 2
+DEAL::3.35 2
+DEAL::3.36 1
+DEAL::3.37 1
+DEAL::3.38 1
+DEAL::3.39 1
+DEAL::3.40 2
+DEAL::3.41 2
+DEAL::3.42 2
+DEAL::3.43 2
+DEAL::3.44 2
+DEAL::3.45 2
+DEAL::3.46 2
+DEAL::3.47 2
+DEAL::3.48 4
+DEAL::3.49 4
+DEAL::3.50 4
+DEAL::3.51 4
+DEAL::3.52 4
+DEAL::3.53 4
+DEAL::3.54 4
+DEAL::3.55 4
+DEAL::3.56 4
+DEAL::3.57 2
+DEAL::3.58 2
+DEAL::3.59 2
+DEAL::3.60 4
+DEAL::3.61 4
+DEAL::3.62 4
+DEAL::3.63 4
+DEAL::K-WAY
+DEAL::3.0 0
+DEAL::3.1 0
+DEAL::3.2 4
+DEAL::3.3 4
+DEAL::3.4 0
+DEAL::3.5 0
+DEAL::3.6 0
+DEAL::3.7 0
+DEAL::3.8 4
+DEAL::3.9 4
+DEAL::3.10 4
+DEAL::3.11 4
+DEAL::3.12 4
+DEAL::3.13 4
+DEAL::3.14 4
+DEAL::3.15 5
+DEAL::3.16 0
+DEAL::3.17 2
+DEAL::3.18 1
+DEAL::3.19 1
+DEAL::3.20 2
+DEAL::3.21 2
+DEAL::3.22 1
+DEAL::3.23 2
+DEAL::3.24 2
+DEAL::3.25 1
+DEAL::3.26 2
+DEAL::3.27 2
+DEAL::3.28 1
+DEAL::3.29 1
+DEAL::3.30 2
+DEAL::3.31 1
+DEAL::3.32 8
+DEAL::3.33 3
+DEAL::3.34 6
+DEAL::3.35 8
+DEAL::3.36 3
+DEAL::3.37 3
+DEAL::3.38 3
+DEAL::3.39 3
+DEAL::3.40 6
+DEAL::3.41 3
+DEAL::3.42 3
+DEAL::3.43 6
+DEAL::3.44 8
+DEAL::3.45 6
+DEAL::3.46 6
+DEAL::3.47 6
+DEAL::3.48 5
+DEAL::3.49 5
+DEAL::3.50 5
+DEAL::3.51 5
+DEAL::3.52 8
+DEAL::3.53 8
+DEAL::3.54 8
+DEAL::3.55 7
+DEAL::3.56 7
+DEAL::3.57 8
+DEAL::3.58 6
+DEAL::3.59 7
+DEAL::3.60 7
+DEAL::3.61 7
+DEAL::3.62 7
+DEAL::3.63 7
+DEAL::RECURSIVE
+DEAL::2.0 3
+DEAL::2.1 3
+DEAL::2.2 3
+DEAL::2.3 3
+DEAL::2.4 3
+DEAL::2.5 3
+DEAL::2.6 3
+DEAL::2.7 3
+DEAL::2.8 0
+DEAL::2.9 0
+DEAL::2.10 0
+DEAL::2.11 0
+DEAL::2.12 0
+DEAL::2.13 0
+DEAL::2.14 0
+DEAL::2.15 0
+DEAL::2.16 1
+DEAL::2.17 1
+DEAL::2.18 1
+DEAL::2.19 1
+DEAL::2.20 1
+DEAL::2.21 1
+DEAL::2.22 1
+DEAL::2.23 1
+DEAL::2.24 3
+DEAL::2.25 3
+DEAL::2.26 4
+DEAL::2.27 3
+DEAL::2.28 3
+DEAL::2.29 3
+DEAL::2.30 4
+DEAL::2.31 4
+DEAL::2.32 2
+DEAL::2.33 2
+DEAL::2.34 2
+DEAL::2.35 2
+DEAL::2.36 2
+DEAL::2.37 2
+DEAL::2.38 2
+DEAL::2.39 2
+DEAL::2.40 0
+DEAL::2.41 0
+DEAL::2.42 0
+DEAL::2.43 0
+DEAL::2.44 2
+DEAL::2.45 2
+DEAL::2.46 1
+DEAL::2.47 2
+DEAL::2.48 1
+DEAL::2.49 1
+DEAL::2.50 1
+DEAL::2.51 4
+DEAL::2.52 2
+DEAL::2.53 1
+DEAL::2.54 4
+DEAL::2.55 4
+DEAL::2.56 4
+DEAL::2.57 4
+DEAL::2.58 4
+DEAL::2.59 4
+DEAL::2.60 4
+DEAL::2.61 2
+DEAL::2.62 4
+DEAL::2.63 4
+DEAL::K-WAY
+DEAL::2.0 4
+DEAL::2.1 0
+DEAL::2.2 4
+DEAL::2.3 4
+DEAL::2.4 4
+DEAL::2.5 0
+DEAL::2.6 3
+DEAL::2.7 4
+DEAL::2.8 0
+DEAL::2.9 0
+DEAL::2.10 1
+DEAL::2.11 1
+DEAL::2.12 1
+DEAL::2.13 1
+DEAL::2.14 1
+DEAL::2.15 1
+DEAL::2.16 7
+DEAL::2.17 7
+DEAL::2.18 7
+DEAL::2.19 7
+DEAL::2.20 8
+DEAL::2.21 8
+DEAL::2.22 8
+DEAL::2.23 7
+DEAL::2.24 4
+DEAL::2.25 5
+DEAL::2.26 5
+DEAL::2.27 5
+DEAL::2.28 5
+DEAL::2.29 5
+DEAL::2.30 7
+DEAL::2.31 5
+DEAL::2.32 4
+DEAL::2.33 2
+DEAL::2.34 3
+DEAL::2.35 3
+DEAL::2.36 2
+DEAL::2.37 2
+DEAL::2.38 3
+DEAL::2.39 3
+DEAL::2.40 0
+DEAL::2.41 0
+DEAL::2.42 1
+DEAL::2.43 1
+DEAL::2.44 0
+DEAL::2.45 0
+DEAL::2.46 2
+DEAL::2.47 2
+DEAL::2.48 8
+DEAL::2.49 8
+DEAL::2.50 8
+DEAL::2.51 8
+DEAL::2.52 2
+DEAL::2.53 2
+DEAL::2.54 6
+DEAL::2.55 6
+DEAL::2.56 3
+DEAL::2.57 6
+DEAL::2.58 6
+DEAL::2.59 5
+DEAL::2.60 3
+DEAL::2.61 6
+DEAL::2.62 6
+DEAL::2.63 6
--
2.39.5