--- trunk/langevinHull/langevinHull.tex	2010/10/27 18:48:34	3665
+++ trunk/langevinHull/langevinHull.tex	2010/10/28 20:30:16	3666
@@ -625,7 +625,57 @@ The orientational preference exhibited by hull molecul
 \label{sec:discussion}
 
 \section*{Appendix A: Computing Convex Hulls on Parallel Computers} 
+
+In order to use the Langevin Hull for simulations on parallel
+computers, one of the more difficult tasks is to compute the bounding
+surface, facets, and resistance tensors when the processors have
+incomplete information about the entire system's topology.  Most
+parallel decomposition methods assign primary responsibility for the
+motion of an atomic site to a single processor, and we can exploit
+this to efficiently compute the convex hull for the entire system.
+
+The basic idea is that if we split the original point cloud into
+spatially-overlapping subsets and compute the convex hulls for each of
+the subsets, the points on the convex hull of the entire system are
+all present on at least one of the subset hulls.  The algorithm works
+as follows:
+\begin{enumerate}
+\item Each processor computes the convex hull for its own atomic sites
+  (dashed lines in Fig. \ref{fig:parallel}).
+\item The Hull vertices from each processor are passed out to all of
+  the processors, and each processor assembles a complete list of hull
+  sites (this is much smaller than the original number of points in
+  the point cloud).
+\item Each processor computes the convex hull of these sites (solid
+  line in Fig. \ref{fig:parallel}) and carries out Delaunay
+  triangulation to obtain the facets of the global hull.
+\end{enumerate}
+
+\begin{figure}
+\begin{centering}
+\includegraphics[width=3in]{parallel}
+\caption{When the sites are distributed among many nodes for parallel
+  computation, the processors first compute the convex hulls for their
+  own sites (dashed lines in upper panel). The positions of the sites
+  that make up the convex hulls are then communicated to all
+  processors.  The convex hull of the system (solid line in lower
+  panel) is the convex hull of the points on the hulls for all
+  processors. }
+\end{centering}
+\label{fig:parallel}
+\end{figure}
 
+The individual hull operations scale with
+$O(\frac{n}{p}\log\frac{n}{p})$ where $n$ is the total number of
+sites, and $p$ is the number of processors.  The hull operations
+create a set of $p$ hulls each with approximately $\frac{n}{3pr}$
+sites (for a cluster of radius $r$).  The communication costs for
+distributing this information to all processors is XXX, while the
+final computation of the system hull is of order
+$O(\frac{n}{3r}\log\frac{n}{3r})$.  Overall, the total costs are
+dominated by the computations of the individual hulls, so the Langevin
+hull sees roughly linear speed-up with increasing processor counts.
+
 \section*{Acknowledgments}
 Support for this project was provided by the
 National Science Foundation under grant CHE-0848243. Computational