\subsection{Implementation of Separators in 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 nodes (corresponding to data
which must be routed), depending on the method of partitioning.  This
approach to graph partitioning has been implemented in MATLAB.

We have implemented the random linear time separator algorithm of
Miller {\em et al.} \cite{MTTV}.  The input to the algorithm is a
finite element mesh (or graph embedded in two or three dimensions),
given as a pair $(A,xyz)$, where $A$ describes the combinatorial
structure of the mesh and $xyz$ gives the geometric information. For a
finite element mesh, $A$ could be the list of elements of the mesh,
where each element is given by the information describing the
hierarchical structure of the elements -- its lower dimensional
structures such as its faces, edges, and vertices.  Moreover, each
vertex has geometric coordinates in two or three dimensions given by
$xyz$.

The detailed description the mesh 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} (Partitioning Finite Element Meshes)\\
{\bf Input}: $A$, $xyz$ in $\R^d$.
\begin{enumerate}
\item Choose a random sample $P$ of constant size\footnote{See \ref{MTTV92a} 
for the theoretical justification.  According to our experiments, 400
to 800 points work very well in three dimensions, and 600 to 1100
points work very well in four dimensions.} from $xyz$;

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

\item Choose a good hyperplane by randomized search;

\item Derive from this hyperplane a partition for $(A,xyz)$;

\item Use the structure of $A$ to optimize the final solution.
\end{enumerate}
\end{quotation}
}

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

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

\item {\em Exploiting both Geometric and Combinatorial Structures}:
The geometric structure of the mesh not only ensures the approximation
quality, 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 search can be performed efficiently.  Then the
combinatorial structure of the mesh is used to derive and optimize the
final solution.
\end{itemize}

We have experimented with various examples.  The numerical results are
very encouraging. With the help of some heuristics to speed up the
geometric transformation and the local optimization, the program is
very 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 very competitive with such previous methods as those
based on an expensive eigenvector computation \cite{PSL89}.

