\section*{Partitioning}

\newdimen\pIR
\pIR=-131072sp
\newcommand\R{{\rm I\kern\pIR R}}

The two most common types of partitioning algorithm
in the literature are known as 
{\em recursive spectral bisection} (RSB)
and {\em recursive geometric bisection} (RGB).  
Both methods bisect a
graph into two equal pieces, while attempting to minimize the size of the
cut.  Both methods are ``recursive'' because they first bisect a graph,
then bisect each of the two resulting pieces, and so on; they therefore
yield a number of subdomains that is a power of two.

RSB~\cite{pothen90} bisects a graph by exploiting spectral properties of its
combinatorial structure.  However, RSB does not take into account the positions
of the graph's vertices in space.  While RSB usually produces excellent
partitions in practice, it tends to be slow, as it relies on expensive
eigenvector calculations.
RGB uses the spatial coordinates of the vertices rather than the
combinatorial structure
of the graph, and typically executes more quickly.
One of the main advantages of constructing Archimedes
as a unified system is that the geometric information --- the node coordinates
and the node/element relationships --- is readily available at all stages
of the computation, including the partitioning and placement steps.

\begin{figure}
\ifcolor
\centerline{\epsfxsize=5in \epsfbox{guitar2.2.epart.eps.color}}
\else
\centerline{\epsfxsize=5in \epsfbox{guitar2.2.epart.eps}}
\fi
\caption{\label{partition} Partitioned guitar for
sixty-four processor machine.}
\end{figure}

\begin{figure}
\ifcolor
\centerline{\epsfxsize=5in \epsfbox{guitar2.2.adj.eps.color}}
\else
\centerline{\epsfxsize=5in \epsfbox{guitar2.2.adj.eps}}
\fi
\caption{\label{quotient} Sixty-four vertex quotient graph $E'$ for partitioned
guitar.}
\end{figure}

Archimedes' partitioner uses an advanced recursive geometric
bisection (RGB) algorithm due to Miller,
Teng, Thurston, and Vavasis~\cite{mttv93},
which finds provably good separators for a large class of 
geometrically defined graphs.
A {\em separator} is a small set of edges
whose removal divides the graph into roughly equal pieces.
For an $n$-vertex graph,
it produces (with high probability) a separator of size within a constant
factor of $\sqrt{n}$ in
two dimensions, or of size within a constant factor of 
$n^{2 / 3}$ in three dimensions.
This is the best possible guarantee, in a worst-case asymptotic sense.
In practice, our program usually generates
better partitions than the theoretical worst-case bounds predict.
The algorithm is applied to the element adjacency graph $E$ 
for the mesh being considered, yielding a quotient graph $E'$.
Figure~\ref{partition} illustrates our meshed guitar partitioned
into sixty-four pieces.  Figure \ref{quotient}
illustrates the corresponding quotient graph $E'$.

The Miller et al.\ algorithm runs in randomized linear time, and
is made more efficient
by a technique called {\em geometric sampling}. 
The idea is to choose a random sample of the vertices,
then solve the partitioning problem over the sample.
Thus the problem size is reduced, 
while the underlying geometric structure of the mesh ensures
the quality of the result.
Geometric sampling allows us to do most of the work on sets of only
a few hundred vertices, even if the graph itself has millions of vertices.

Another central idea of the algorithm is the stereographic projection
of vertices from a graph to the surface of a ball.  Figure~\ref{project}
illustrates such a projection.  Given a two-dimensional mesh in a plane,
a three-dimensional
ball is lain atop the plane.  Each point in the plane is projected onto
the ball by drawing a line that passes through the topmost point of the ball.
Note that the projection is modified if the ball is resized or moved along
the plane.
Similarly, a three-dimensional mesh can be projected onto the surface
of a four-dimensional ball.

\begin{figure}
\centerline{\epsfxsize=4in \epsfbox{project.ps}}
\caption{\label{project} Stereographic projection of a point onto a ball.
Point $p$ is mapped to point $q$.}
\end{figure}

The algorithm uses the following steps,
illustrated in Figure~\ref{mttv},
to recursively bisect the element adjacency graph $E$:

\begin{figure}
\ifcolor
  \centerline{\epsfxsize=6in \epsfbox{mttv.color.ps}}
\else
  \centerline{\epsfxsize=6in \epsfbox{mttv.ps}}
\fi
\caption{\label{mttv} Illustration of partitioning algorithm.
1.\ A random sample $S$ is chosen.
2.\ Points are projected to the surface of a ball.  The large
X indicates the center point of the projected points.
3.\ The projection is modified to move the center point to the
center of the ball.
4.\ A random hyperplane splits the sample.  The intersection of the
plane and the surface of the ball form a great circle (bold).
5.\ The great circle is mapped to a circle in the plane that bisects
the domain.  (Only a small arc of the resulting circle is shown here.)
6.\ Subdomains are bisected recursively.}
\end{figure}

\begin{enumerate}

\item Choose a random sample $S$ of constant size
from the vertices of $E$.

\item For a $d$-dimensional mesh, stereographically project
$S$ onto the surface
of a $(d + 1)$-dimensional ball.  Compute an approximate {\em center point}
(defined below) of the points projected on the surface of the ball.

\item Using the center point as a guide, modify the projection so
that the center point coincides with the center of the ball.
Intuitively, this
is done by resizing or moving the ball relative to the graph $E$.

\item Choose a random $d$-dimensional
hyperplane that passes through the center of the ball.
The intersection of this hyperplane with the ball's surface is a
{\em great circle}.

\item Map this great circle back to the $d$-dimensional mesh
to obtain a circle that partitions $E$
into two pieces, $E_1$ and $E_2$.  If the circle intersects too many
edges of $E$, go back to step 4 and choose another random hyperplane.

\item Partition $E_1$ and $E_2$ recursively.

\end{enumerate}

\noindent
The resulting partition of the subdomain is then used to construct the
corresponding quotient graph $E'$ from $E$.

Informally, we can understand the operation of the algorithm as follows:
After the stereographic projection  is performed in Step 2, any great circle
will partition the points mapped to the sphere into two sets.  When projected
back into the plane as in Step 5, each great circle on the sphere
yields a circle that partitions the original set of points in the plane.
However, if the points are not even distributed over the sphere by the
stereographic projection, then it will be difficult to find a great circle
that partitions them evenly.  By modifying the stereographic projection
(i.e., changing the size of the sphere and/or its point of contact with
the plane) in Step 3, 
the distribution of the projected points on the sphere can
be ``evened out'' so that the randomly-chosen hyperplane through the center
of the sphere in Step 4 defines a great circle that is likely to split 
the points evenly.  

Two aspects of the algorithm deserve deeper examination:  the center points
which determine the modification of the stereographic projection,
and the random choice of hyperplanes.

By definition, a {\em center point}
for a set of $n$ input points in $d + 1$ dimensions is a point $c$
such that every $d$-dimensional hyperplane through $c$ has at most
$n \cdot d / (d + 1)$ points on each side.
A center point exists for any set of points,
and can be found by linear programming.
However, this method is much too slow to be practical;
thus Archimedes uses a heuristic
that finds good approximate center points in linear time.
Clarkson et al.~\cite{clarkson93} show that
the center point calculation is a good approximation for $E$
even though it is based on the small random sample $S$.
The sample size depends on the dimension but not the size of the input mesh.
In theory, the subset size is proportional to $d\log d$;
in practice, we use several hundred points in two dimensions and 
about a thousand points in three dimensions.

In theory, a randomly chosen hyperplane passing through the center of the
ball has a 50\% or better chance of cutting only a small number of edges
(roughly $\sqrt{n}$ in two dimensions and $n^{2 / 3}$ in three)~\cite{mttv93}.
In practice, not every hyperplane represents a good bisection.
We therefore generate a number of hyperplanes,
searching for one that gives a balanced partition with few edges cut.
To improve our luck,
the random hyperplanes are chosen from a biased distribution.
Gremban~\cite{gremban94} has suggested using the principal axis of the moment
of inertia of the projected points to bias the random choice.
Intuitively,
a hyperplane perpendicular to the principal axis of the collection of 
points is likely to cross far fewer
edges of $E$ than a hyperplane parallel to the principal axis.
Of course, the computation of the moment of inertia is fast because it is 
also only performed on the random sample $S$.
