\section{Graph Partitioning Using
\newline Separators}

\subsection{Partitioning of Sparse
\newline Matrix-Vector Multiplication}

In general, the sparse matrix-vector multiplications used in
scientific computing can have
millions of
variables, which is far more
than the number of processors in current parallel machines.  Therefore
we partition the problem into subproblems
and map the subproblems to the available
processors, while allowing for the necessary communication between
subproblems.

The most natural way to partition a graph $G$ is to remove some subset of
its edges, leaving some connected components of vertices remaining.
These connected components are assigned to processors.
This is called {\em vertex-partitioning}, because each vertex is assigned
to a single processor.

Current finite element implementations suggest a different partitioning
approach.  A finite element mesh (such as in Figure 2)
is a partitioning of space into elements.  An element is a polygon
(usually a triangle or rectangle) in two dimensions, or a polytope
(usually a tetrahedron or rectangular prism) in three dimensions.
The mesh is made up of nodes connected by edges in two dimensions, or
by faces in three dimensions.  Physical
quantities are associated with each node; for instance, the vector $x$,
whose length $n$ is the number of nodes in the mesh,
might specify the displacement of each node.  Nodes within a single
element have a direct physical effect on each other; thus, $A_{ij}$ is
nonzero if and only if nodes $i$ and $j$ are in some common element $e$.

Given a finite element mesh $M$, a corresponding graph $G$ is
generated by creating one vertex in $G$ for each node in $M$, and adding
an edge to $G$ for each pair of nodes which share a common element.
Thus, if $M$ is composed of triangular elements, $G$ will be identical
to $M$.  If $M$ is composed of square elements, $G$ will look similar to
$M$, but with the addition of edges between opposite corners of squares.

It is possible
to partition $G$ by cutting between mesh elements and storing a copy of
each vertex along the cut in each bordering block of the partition.
This is called {\em element-partitioning}, because each element is
assigned to a single processor, whereas some vertices
are assigned to several processors.

In order to write an efficient implementation there are two measures we must
keep in mind.  First, we must keep the sizes of the partition blocks
relatively balanced --- note that for this problem, the amount of local work
done on a processor is the number of edges contained in its partition block,
not the number of vertices.  Second, we wish to keep the boundaries of the
partition blocks as small as possible, as this corresponds to the amount of
interprocessor communication we must perform.  In the next subsection we will
discuss how graph separators allow us to address both of these concerns.

If we have partitioned $G$ into $p$ blocks, where $p$ is the
number of available processors, then we can define the {\em $p$-vertex
minor} $G'$ derived
from $G$ and the partition.  $G'$ is a weighted graph with
a supervertex for each block of the partition, and an edge between two
supervertices if their corresponding blocks need to communicate with each
other (i.e., they either have a cut edge between them or contain copies of the
same vertex, depending on the partitioning approach).
The weight on an edge of $G'$ is
the number of values which must be communicated between those two
supervertices
in order to perform a multiplication.  The weighted minor $G'$
is what we must place and route on the target machine.

\subsection{Implementation of Separators in
\newline Two and Three Dimensions}
\newdimen\pIR
\pIR=-131072sp
\newcommand\R{{\rm I\kern\pIR R}}

Miller, Teng, Thurston and Vavasis \cite{MTTV} give provably good
separators in two or three dimensions for the sort of combinatorial
graphs generated by these problems.  These separators can be used
recursively to obtain a partition of the graph with both good balance
among block sizes (corresponding to processor load) and a relatively
small number of cut edges or duplicated vertices (corresponding to data
which must be routed), depending on the method of partitioning.

We have implemented the random linear time separator algorithm of
Miller et al.\ \cite{MTTV} in MATLAB.  The input to the algorithm is
a pair $(G, xyz)$, representing a graph embedded in two or three dimensions.
$G$ is the graph we derive from the finite element mesh $M$, and $xyz$
is the coordinates of the vertices of $G$ (taken from $M$).

A detailed description of the graph partitioning algorithm can be found
in \cite{MTTV92a}. The following is an outline of the basic steps.

{\renewcommand{\baselinestretch}{1.3}
\begin{quotation}
\noindent {\bf Algorithm} (Vertex-Partition a Graph in $\R^d$)\\
{\bf Input}: $G$, $xyz$ in $\R^d$.
\begin{enumerate}
\item Choose a random sample $S$ of constant size\footnote{See \cite{MTTV92a} 
for the theoretical justification.  According to our experiments, 400
to 800 points work well in two dimensions, and 600 to 1100
points work well in three dimensions.} from $xyz$;

\item Map $S$ conformally onto the unit sphere in $\R^{d+1}$
in such a way that every hyperplane through the origin partitions $S$
approximately evenly.
% (This step takes constant time);

\item Choose hyperplanes randomly until a good split is found;

% \item Choose a good hyperplane by randomized search;

\item Map the great circle induced by the hyperplane back to $\R^d$
to obtain a sphere that partitions $G$ (as well as $xyz$) approximately
evenly;

\item The edges that cut this sphere form an edge separator.  This set
of edges can be found using the structure of $G$;
(If a vertex separator is desired, it can be computed from the edge 
separator above.  The structure of $G$ can be used to optimize the separator
size.)

\item Partition $G$ into two subgraphs, $G_1$ and $G_2$.  Each vertex
is placed into $G_1$ or $G_2$, depending on whether it is mapped to the
interior of the exterior of the sphere in $\R^d$;

\item Recursively partition $G_1$ and $G_2$.

\end{enumerate}
\end{quotation}
}

Element-partitioning can be done similarly.Each element is placed into
$G_1$ or $G_2$ depending on, for instance,
where the center of the element falls.

Two important aspects of the partitioning algorithm make it suitable
for efficient practical implementation:

\begin{itemize}
\item {\em Geometric Sampling}: Graphs derived from large-scale computational
problems may have millions of vertices. Geometric sampling is a
technique that reduces the problem size and simultaneously
guarantees a provably good approximation of the larger problem.  The
basic idea is to first choose a random sample of the
input, then solve the partitioning problem over the sample. The
underlying geometric structure of the mesh ensures the quality of
the partition.

\item {\em Exploiting both Geometric and Combinatorial Structures}:
The geometric structure of the mesh not only ensures the quality
of the approximation,
but also enables efficient implementation of some key
subroutines. One of the goals of the algorithm is to find a balanced
partition while minimizing the cost of the cut. The geometry of the
mesh is used to map the problem into a canonical form so that the
randomized selection can be performed efficiently.  Then the
combinatorial structure of the graph is used to derive and optimize the
final solution.
\end{itemize}

We have experimented with various examples, and the numerical results are
encouraging. With the help of some heuristics to speed up the
geometric transformation and the local optimization, the program is
fast (even in the MATLAB environment, which is interpretive and
lacks code optimization). In practice, our program generates
partitions much better than the theoretical results predict.  The
partitions are competitive with such previous methods as those
based on an expensive eigenvector computation \cite{PSL89}.

