multiblock structured mesh partitioning algorithm

[Michael Lee Crogan]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dear Jean Remacle and Christophe Geuzaine:

I am working for Lawrence Livermore National Laboratory researching
partitioning algorithms for multiblock-structured meshes.  The first
step in this process involves a query into existing technologies, as
it is easier to adapt a solution to our specific needs than it is to
design one from the ground up.  Thus far we have not found a
multiblock-structured partitioning algorithm that addresses our
problem in anything other than an ad-hoc manner (the method that we
are currently using is described below).

We would greatly appreciate it if you might have any information which
could point us in the right direction.  While finding a design
perfectly suited to our purposes is certainly the ideal, we can also
prosper by finding algorithms which ``come close'' since they can give
us new ideas on our own approaches to the problem.

We currently have existing (multi)block-structured meshes which need
to be partitioned so that our physical simulation code may run well in
parallel.  We want to distribute computational and network load as
evenly as possible, as we are (in general) bound by the slowest
processor or processors.  The optimizations we wish to include in our
resultant partitioning scheme are described below, and they model the
aforementioned properties (i.e., computational and network load).

Your suggestions, pointers, and feedback on this problem are greatly
appreciated.  I hope that the explanation of the code we are seeking
is clear.  We can benefit immensely from finding the right person(s)
to talk to, and of course from any direct insights about how to
implement the solution.  We appreciate your assistance.

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

Description of problem:

We've got an arbitrary abstract region of space that we want to divide
into N parts subject to the constraint that each of the resulting
parts must be rectangular in shape.  The original abstract region of
space is itself a collection of rectangular subregions of space that
abut one another, and that ``line up'' at the nodes along the
boundaries of subregions.

These rectangles are in the cartesian plane such that the vertices of
the rectangles fall at lattice points, and such that the set of points
interior to these rectangles are connected in the mathematical
sense. This union of rectangles will be called a mesh.

This mesh can be partitioned into N regions using somewhere between
N-1 and N-1+(mesh genus) separators, where a separator in the 2D case
is just a line segment (see below for definition), and the genus is
the number of 'holes' in the mesh.  The goal is to position the
separators within the mesh with respect to some constraints.

Necessary conditions:
- ---------------------
1) The separators must be oriented along the lattice axes(orthogonal).
2) k separators can be predefined by the user, where
   k is an integer in [0,N-2+(mesh genus)].

Optimization contraints:
- -----------------------
Necessary:
1) Regions must have approximately equal volumes (Some rectangular
   regions may have a volume multiplier/weight).

Desired:
2) All Regions should have a roughly equal number of separators.
3) The sum of the lengths of a given region's separtors should be
   roughly equal for all regions.

Desired computational properties
- --------------------------------
Less than 15 minutes to solve for the optimal separators on a parallel
machine.

Potentially helpful information for algorithm design:
- ----------------------------------------------------
1) The genus of the mesh will almost always be zero, and can be
   assumed as such.
2) There will typically be less than 100 rectangular regions in the
   mesh, and there will almost never be more than 1000.
3) The number of partitions will usually be around 1000, possibly
   increasing to around 10000.

Definition of a separator:
- -------------------------

A separator is a line segment whose endpoints meet other line segments
perpendicular to it, subject to the constraint that no perpendicular
segments can be adjacent to that separator except at the endpoints.
All separators are vertical or horizontal--never diagonal.  This is a
natural conceptual definition, and may very well be the nature of the
data structure when it is implemented.  Note that ``w'' becomes a
separator distinct from ``y'' in the diagram below, for instance:

  --------------
  |    x    y  |
  |    x    y  |
  |    x    y  \___________
  |    x    y             |
  | A  x B  y  C          |  [Note: capital letters are the regions while
  |    x    wzzzzzzzzzzzzz|   lower-cased ones signify the separators]
  |    x    w      D      |
  -------------------------

Hence, we can observe that a separator does not have to go all the way
across the entire mesh, but it does have to be constrained between two
existing separators.  Also, there are three ``types'' of separators:
the natural boundaries around the ``outside'' of the mesh, the imposed
separators that come from the user, or those created dynamically
during the course of the partitioning algorithm.

Definition of a region:
- ----------------------

A region is the partition of space that results after the separators
have all been applied.  i.e. it's the natural boundary of the mesh plus
any boundaries introduced by the separators.  A separator can be double
counted in terms of the language I was using.  i.e. if the mesh was a
single rectangle and it was partitioned into two parts by a single
separator, then it would result in two regions, each region having one
separator.

Current approach, and other useful information:
- ----------------------------------------------

Right now, if we want to create N global partitions, we first
apportion N among the rectangular subregions of the mesh based on the
volume weighting of the subregions.  If we look at one of these
subregions, that it must be partioned into A parts, where A is it's
apportionment from the global number of parts.  Currently we just
factor A into three values (one for each dimension), and then slice
the block into equally spaced slabs along each axis.  We have plans to
improve upon this approach, but our focus now is to determine what
type(s) of related software have been written.

We have a multiblock structured code we want to use this on, but we
also have an unstructured hexeheral mesh code we'd like to try it on.
The great thing about block partitioning is that it creates ``smooth''
interfaces betwen partition boundaries.  This will help us to greatly
reduce the amount of info we have to communicate in the two ghost
layers we require for our second order calculations.  The current
jagged edges produced by the unstructured partitioners can cause up to
40% inefficiency in three dimensions!

Michael Lee Crogan -- <mcrogan at purdue.edu> -- Purdue University

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.1e (SunOS)
Comment: Processed by Mailcrypt 3.5.5 and Gnu Privacy Guard <http://www.gnupg.org/>

iEYEARECAAYFAjlQbUQACgkQIw2dkfh5sRSZvgCgo1+dOleFOXBaDRokET3NOtrD
q8MAnAkuNRLVfvsb/LdDRsPL5cGgq0fy
=zqE1
-----END PGP SIGNATURE-----