ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/group/trunk/langevinHull/langevinHull.tex
(Generate patch)

Comparing trunk/langevinHull/langevinHull.tex (file contents):
Revision 3665 by gezelter, Wed Oct 27 18:48:34 2010 UTC vs.
Revision 3678 by gezelter, Mon Nov 8 20:11:36 2010 UTC

# Line 18 | Line 18
18   \setlength{\belowcaptionskip}{30 pt}
19  
20   \bibpunct{[}{]}{,}{s}{}{;}
21 < \bibliographystyle{aip}
21 > \bibliographystyle{achemso}
22  
23   \begin{document}
24  
# Line 66 | Line 66 | of an isobaric-isothermal (NPT) ensemble maintain a ta
66   \section{Introduction}
67  
68   The most common molecular dynamics methods for sampling configurations
69 < of an isobaric-isothermal (NPT) ensemble maintain a target pressure in
70 < a simulation by coupling the volume of the system to a {\it barostat},
71 < which is an extra degree of freedom propagated along with the particle
72 < coordinates.  These methods require periodic boundary conditions,
73 < because when the instantaneous pressure in the system differs from the
74 < target pressure, the volume is reduced or expanded using {\it affine
75 <  transforms} of the system geometry. An affine transform scales the
76 < size and shape of the periodic box as well as the particle positions
77 < within the box (but not the sizes of the particles). The most common
78 < constant pressure methods, including the Melchionna
79 < modification\cite{Melchionna1993} to the Nos\'e-Hoover-Andersen
80 < equations of motion,\cite{Hoover85,ANDERSEN:1980vn,Sturgeon:2000kx}
81 < the Berendsen pressure bath,\cite{ISI:A1984TQ73500045} and the
82 < Langevin Piston,\cite{FELLER:1995fk,Jakobsen:2005uq} all utilize
69 > from an isobaric-isothermal (NPT) ensemble maintain a target pressure
70 > in a simulation by coupling the volume of the system to a {\it
71 >  barostat}, which is an extra degree of freedom propagated along with
72 > the particle coordinates.  These methods require periodic boundary
73 > conditions, because when the instantaneous pressure in the system
74 > differs from the target pressure, the volume is reduced or expanded
75 > using {\it affine transforms} of the system geometry. An affine
76 > transform scales the size and shape of the periodic box as well as the
77 > particle positions within the box (but not the sizes of the
78 > particles). The most common constant pressure methods, including the
79 > Melchionna modification\cite{Melchionna1993} to the
80 > Nos\'e-Hoover-Andersen equations of
81 > motion,\cite{Hoover85,ANDERSEN:1980vn,Sturgeon:2000kx} the Berendsen
82 > pressure bath,\cite{ISI:A1984TQ73500045} and the Langevin
83 > Piston,\cite{FELLER:1995fk,Jakobsen:2005uq} all utilize scaled
84   coordinate transformation to adjust the box volume.  As long as the
85 < material in the simulation box is essentially a bulk-like liquid which
86 < has a relatively uniform compressibility, the standard affine
87 < transform approach provides an excellent way of adjusting the volume
88 < of the system and applying pressure directly via the interactions
88 < between atomic sites.
85 > material in the simulation box has a relatively uniform
86 > compressibility, the standard affine transform approach provides an
87 > excellent way of adjusting the volume of the system and applying
88 > pressure directly via the interactions between atomic sites.
89  
90   One problem with this approach appears when the system being simulated
91   is an inhomogeneous mixture in which portions of the simulation box
# Line 100 | Line 100 | slow enough to avoid the instabilities in the incompre
100  
101   \begin{figure}
102   \includegraphics[width=\linewidth]{AffineScale2}
103 < \caption{Affine Scaling constant pressure methods use box-length
104 <  scaling to adjust the volume to adjust to under- or over-pressure
105 <  conditions. In a system with a uniform compressibility (e.g. bulk
106 <  fluids) these methods can work well.  In systems containing
107 <  heterogeneous mixtures, the affine scaling moves required to adjust
108 <  the pressure in the high-compressibility regions can cause molecules
109 <  in low compressibility regions to collide.}
103 > \caption{Affine scaling methods use box-length scaling to adjust the
104 >  volume to adjust to under- or over-pressure conditions. In a system
105 >  with a uniform compressibility (e.g. bulk fluids) these methods can
106 >  work well.  In systems containing heterogeneous mixtures, the affine
107 >  scaling moves required to adjust the pressure in the
108 >  high-compressibility regions can cause molecules in low
109 >  compressibility regions to collide.}
110   \label{affineScale}
111   \end{figure}
112  
# Line 121 | Line 121 | There have been a number of other approaches to explic
121   SIMULATIONS]
122  
123   \subsection*{Boundary Methods}
124 < There have been a number of other approaches to explicit
125 < non-periodicity that focus on constant or nearly-constant {\it volume}
126 < conditions while maintaining bulk-like behavior.  Berkowitz and
127 < McCammon introduced a stochastic (Langevin) boundary layer inside a
128 < region of fixed molecules which effectively enforces constant
129 < temperature and volume (NVT) conditions.\cite{Berkowitz1982} In this
130 < approach, the stochastic and fixed regions were defined relative to a
131 < central atom.  Brooks and Karplus extended this method to include
132 < deformable stochastic boundaries.\cite{iii:6312} The stochastic
133 < boundary approach has been used widely for protein
134 < simulations. [CITATIONS NEEDED]
124 > There have been a number of approaches to handle simulations of
125 > explicitly non-periodic systems that focus on constant or
126 > nearly-constant {\it volume} conditions while maintaining bulk-like
127 > behavior.  Berkowitz and McCammon introduced a stochastic (Langevin)
128 > boundary layer inside a region of fixed molecules which effectively
129 > enforces constant temperature and volume (NVT)
130 > conditions.\cite{Berkowitz1982} In this approach, the stochastic and
131 > fixed regions were defined relative to a central atom.  Brooks and
132 > Karplus extended this method to include deformable stochastic
133 > boundaries.\cite{iii:6312} The stochastic boundary approach has been
134 > used widely for protein simulations. [CITATIONS NEEDED]
135  
136   The electrostatic and dispersive behavior near the boundary has long
137   been a cause for concern when performing simulations of explicitly
# Line 202 | Line 202 | random forces on the facets of the {\it hull itself} i
202   In the following sections, we extend and generalize the approach of
203   Kohanoff, Caro, and Finnis. The new method, which we are calling the
204   ``Langevin Hull'' applies the external pressure, Langevin drag, and
205 < random forces on the facets of the {\it hull itself} instead of the
206 < atomic sites comprising the vertices of the hull.  This allows us to
207 < decouple the external pressure contribution from the drag and random
208 < force.  The methodology is introduced in section \ref{sec:meth}, tests
209 < on crystalline nanoparticles, liquid clusters, and heterogeneous
210 < mixtures are detailed in section \ref{sec:tests}.  Section
211 < \ref{sec:discussion} summarizes our findings.
205 > random forces on the {\it facets of the hull} instead of the atomic
206 > sites comprising the vertices of the hull.  This allows us to decouple
207 > the external pressure contribution from the drag and random force.
208 > The methodology is introduced in section \ref{sec:meth}, tests on
209 > crystalline nanoparticles, liquid clusters, and heterogeneous mixtures
210 > are detailed in section \ref{sec:tests}.  Section \ref{sec:discussion}
211 > summarizes our findings.
212  
213   \section{Methodology}
214   \label{sec:meth}
# Line 241 | Line 241 | simulation.
241   \includegraphics[width=\linewidth]{hullSample}
242   \caption{The external temperature and pressure bath interacts only
243    with those atoms on the convex hull (grey surface).  The hull is
244 <  computed dynamically at each time step, and molecules dynamically
245 <  move between the interior (Newtonian) region and the Langevin hull.}
244 >  computed dynamically at each time step, and molecules can move
245 >  between the interior (Newtonian) region and the Langevin hull.}
246   \label{fig:hullSample}
247   \end{figure}
248  
# Line 363 | Line 363 | Note that this treatment explicitly ignores rotations
363   \begin{equation}
364   \Xi_f(t) =\left[\sum_{i=1}^3 T_{if}\right]^{-1}.
365   \end{equation}
366 < Note that this treatment explicitly ignores rotations (and
366 > Note that this treatment ignores rotations (and
367   translational-rotational coupling) of the facet.  In compact systems,
368   the facets stay relatively fixed in orientation between
369   configurations, so this appears to be a reasonably good approximation.
# Line 373 | Line 373 | molecular dynamics time step, the following process is
373   molecular dynamics time step, the following process is carried out:
374   \begin{enumerate}
375   \item The standard inter-atomic forces ($\nabla_iU$) are computed.
376 < \item Delaunay triangulation is done using the current atomic
376 > \item Delaunay triangulation is carried out using the current atomic
377    configuration.
378   \item The convex hull is computed and facets are identified.
379   \item For each facet:
# Line 447 | Line 447 | atoms and the SPC/E water molecules.\cite{ISI:00016776
447   Spohr potential was adopted in depicting the interaction between metal
448   atoms and the SPC/E water molecules.\cite{ISI:000167766600035}
449  
450 < \subsection{Bulk modulus of gold nanoparticles}
450 > \subsection{Compressibility of gold nanoparticles}
451  
452 < The compressibility is well-known for gold, and it provides a good first
453 < test of how the method compares to other similar methods.  
452 > The compressibility (and its inverse, the bulk modulus) is well-known
453 > for gold, and is captured well by the embedded atom method
454 > (EAM)~\cite{PhysRevB.33.7983} potential
455 > and related multi-body force fields.  In particular, the quantum
456 > Sutton-Chen potential gets nearly quantitative agreement with the
457 > experimental bulk modulus values, and makes a good first test of how
458 > the Langevin Hull will perform at large applied pressures.
459  
460 < \begin{figure}
461 < \includegraphics[width=\linewidth]{P_T_combined}
462 < \caption{Pressure and temperature response of an 18 \AA\ gold
463 <  nanoparticle initially when first placed in the Langevin Hull
464 <  ($T_\mathrm{bath}$ = 300K, $P_\mathrm{bath}$ = 4 GPa) and starting
460 > The Sutton-Chen (SC) potentials are based on a model of a metal which
461 > treats the nuclei and core electrons as pseudo-atoms embedded in the
462 > electron density due to the valence electrons on all of the other
463 > atoms in the system.\cite{Chen90} The SC potential has a simple form that closely
464 > resembles the Lennard Jones potential,
465 > \begin{equation}
466 > \label{eq:SCP1}
467 > U_{tot}=\sum _{i}\left[ \frac{1}{2}\sum _{j\neq i}D_{ij}V^{pair}_{ij}(r_{ij})-c_{i}D_{ii}\sqrt{\rho_{i}}\right] ,
468 > \end{equation}
469 > where $V^{pair}_{ij}$ and $\rho_{i}$ are given by
470 > \begin{equation}
471 > \label{eq:SCP2}
472 > V^{pair}_{ij}(r)=\left( \frac{\alpha_{ij}}{r_{ij}}\right)^{n_{ij}}, \rho_{i}=\sum_{j\neq i}\left( \frac{\alpha_{ij}}{r_{ij}}\right) ^{m_{ij}}.
473 > \end{equation}
474 > $V^{pair}_{ij}$ is a repulsive pairwise potential that accounts for
475 > interactions between the pseudoatom cores. The $\sqrt{\rho_i}$ term in
476 > Eq. (\ref{eq:SCP1}) is an attractive many-body potential that models
477 > the interactions between the valence electrons and the cores of the
478 > pseudo-atoms. $D_{ij}$, $D_{ii}$ set the appropriate overall energy
479 > scale, $c_i$ scales the attractive portion of the potential relative
480 > to the repulsive interaction and $\alpha_{ij}$ is a length parameter
481 > that assures a dimensionless form for $\rho$. These parameters are
482 > tuned to various experimental properties such as the density, cohesive
483 > energy, and elastic moduli for FCC transition metals. The quantum
484 > Sutton-Chen (QSC) formulation matches these properties while including
485 > zero-point quantum corrections for different transition
486 > metals.\cite{PhysRevB.59.3527}
487 >
488 > In bulk gold, the experimentally-measured value for the bulk modulus
489 > is 180.32 GPa, while previous calculations on the QSC potential in
490 > periodic-boundary simulations of the bulk have yielded values of
491 > 175.53 GPa.\cite{XXX} Using the same force field, we have performed a
492 > series of relatively short (200 ps) simulations on 40 \r{A} radius
493 > nanoparticles under the Langevin Hull at a variety of applied
494 > pressures ranging from 0 GPa to XXX.  We obtain a value of 177.547 GPa
495 > for the bulk modulus for gold using this echnique.
496 >
497 > \begin{figure}
498 > \includegraphics[width=\linewidth]{stacked}
499 > \caption{The response of the internal pressure and temperature of gold
500 >  nanoparticles when first placed in the Langevin Hull
501 >  ($T_\mathrm{bath}$ = 300K, $P_\mathrm{bath}$ = 4 GPa), starting
502    from initial conditions that were far from the bath pressure and
503 <  temperature.  The pressure response is rapid, and the thermal
462 <  equilibration depends on both total surface area and the viscosity
463 <  of the bath.}
503 >  temperature.  The pressure response is rapid (after the breathing mode oscillations in the nanoparticle die out), and the rate of thermal equilibration depends on both exposed surface area (top panel) and the viscosity of the bath (middle panel).}
504   \label{pressureResponse}
505   \end{figure}
506  
# Line 469 | Line 509 | test of how the method compares to other similar metho
509      P}\right)
510   \end{equation}
511  
472 \begin{figure}
473 \includegraphics[width=\linewidth]{compress_tb}
474 \caption{Isothermal Compressibility (18 \AA gold nanoparticle)}
475 \label{temperatureResponse}
476 \end{figure}
477
512   \subsection{Compressibility of SPC/E water clusters}
513  
514   Prior molecular dynamics simulations on SPC/E water (both in
# Line 522 | Line 556 | bulk modulus.
556   and the hull geometries are much more compact.  Because of the
557   liquid-vapor effect on the convex hull, the regional number density
558   approach (Eq. \ref{eq:BMN}) provides more reliable estimates of the
559 < bulk modulus.
559 > compressibility.
560  
561   In both the traditional compressibility formula (Eq. \ref{eq:BM}) and
562   the number density version (Eq. \ref{eq:BMN}), multiple simulations at
# Line 543 | Line 577 | magnitude larger than the reference values.  Any compr
577   Thus, the compressibility of each simulation can be calculated
578   entirely independently from all other trajectories. However, the
579   resulting compressibilities were still as much as an order of
580 < magnitude larger than the reference values.  Any compressibility
580 > magnitude larger than the reference values. However, compressibility
581   calculation that relies on the hull volume will suffer these effects.
582   WE NEED MORE HERE.
583  
# Line 551 | Line 585 | to replicate the properties of the bulk.  Naturally, t
585  
586   In order for non-periodic boundary conditions to be widely applicable,
587   they must be constructed in such a way that they allow a finite system
588 < to replicate the properties of the bulk.  Naturally, this requirement
589 < has spawned many methods for fixing and characterizing the effects of
590 < artifical boundaries. Of particular interest regarding the Langevin
591 < Hull is the orientation of water molecules that are part of the
592 < geometric hull.  Ideally, all molecules in the cluster will have the
593 < same orientational distribution as bulk water.
588 > to replicate the properties of the bulk.  Early non-periodic
589 > simulation methods (e.g. hydrophobic boundary potentials) induced
590 > spurious orientational correlations deep within the simulated
591 > system.\cite{Lee1984,Belch1985} This behavior spawned many methods for
592 > fixing and characterizing the effects of artifical boundaries
593 > including methods which fix the orientations of a set of edge
594 > molecules.\cite{Warshel1978,King1989}
595  
596 < The orientation of molecules at the edges of a simulated cluster has
597 < long been a concern when performing simulations of explicitly
598 < non-periodic systems. Early work led to the surface constrained soft
599 < sphere dipole model (SCSSD) \cite{Warshel1978} in which the surface
600 < molecules are fixed in a random orientation representative of the bulk
601 < solvent structural properties. Belch, et al \cite{Belch1985} simulated
602 < clusters of TIPS2 water surrounded by a hydrophobic bounding
603 < potential. The spherical hydrophobic boundary induced dangling
604 < hydrogen bonds at the surface that propagated deep into the cluster,
605 < affecting 70\% of the 100 molecules in the simulation. This result
606 < echoes an earlier study which showed that an extended planar
572 < hydrophobic surface caused orientational preference at the surface
573 < which extended 7 \r{A} into the liquid simulation cell
574 < \cite{Lee1984}. The surface constrained all-atom solvent (SCAAS) model
575 < \cite{King1989} improved upon its SCSSD predecessor. The SCAAS model
576 < utilizes a polarization constraint which is applied to the surface
577 < molecules to maintain bulk-like structure at the cluster surface. A
578 < radial constraint is used to maintain the desired bulk density of the
579 < liquid. Both constraint forces are applied only to a pre-determined
580 < number of the outermost molecules.
596 > As described above, the Langevin Hull does not require that the
597 > orientation of molecules be fixed, nor does it utilize an explicitly
598 > hydrophobic boundary, orientational constraint or radial constraint.
599 > Therefore, the orientational correlations of the molecules in a water
600 > cluster are of particular interest in testing this method.  Ideally,
601 > the water molecules on the surface of the cluster will have enough
602 > mobility into and out of the center of the cluster to maintain a
603 > bulk-like orientational distribution in the absence of orientational
604 > and radial constraints.  However, since the number of hydrogen bonding
605 > partners available to molecules on the exterior are limited, it is
606 > likely that there will be some effective hydrophobicity of the hull.
607  
608 < In contrast, the Langevin Hull does not require that the orientation
609 < of molecules be fixed, nor does it utilize an explicitly hydrophobic
610 < boundary, orientational constraint or radial constraint. The number
611 < and identity of the molecules included on the convex hull are dynamic
586 < properties, thus avoiding the formation of an artificial solvent
587 < boundary layer. The hope is that the water molecules on the surface of
588 < the cluster, if left to their own devices in the absence of
589 < orientational and radial constraints, will maintain a bulk-like
590 < orientational distribution.
591 <
592 < To determine the extent of these effects demonstrated by the Langevin Hull, we examined the orientations exhibited by SPC/E water in a cluster of 1372 molecules at 300 K and at pressures ranging from 1 - 1000 atm.
593 <
594 < The orientation of a water molecule is described by
595 <
608 > To determine the extent of these effects demonstrated by the Langevin
609 > Hull, we examined the orientationations exhibited by SPC/E water in a
610 > cluster of 1372 molecules at 300 K and at pressures ranging from 1 -
611 > 1000 atm.  The orientational angle of a water molecule is described
612   \begin{equation}
613   \cos{\theta}=\frac{\vec{r}_i\cdot\vec{\mu}_i}{|\vec{r}_i||\vec{\mu}_i|}
614   \end{equation}
615 + where $\vec{r}_{i}$ is the vector between molecule {\it i}'s center of
616 + mass and the cluster center of mass and $\vec{\mu}_{i}$ is the vector
617 + bisecting the H-O-H angle of molecule {\it i} Bulk-like distributions
618 + will result in $\langle \cos \theta \rangle$ values close to zero.  If
619 + the hull exhibits an overabundance of externally-oriented oxygen sites
620 + the average orientation will be negative, while dangling hydrogen
621 + sites will result in positive average orientations.
622  
623 < where $\vec{r}_{i}$ is the vector between molecule {\it i}'s center of mass and the cluster center of mass and $\vec{\mu}_{i}$ is the vector bisecting the H-O-H angle of molecule {\it i}.
624 <
623 > Fig. \ref{fig:pAngle} shows the distribution of $\cos{\theta}$ values
624 > for molecules in the interior of the cluster (squares) and for
625 > molecules included in the convex hull (circles).
626   \begin{figure}
603 \includegraphics[width=\linewidth]{g_r_theta}
604 \caption{Definition of coordinates}
605 \label{coords}
606 \end{figure}
607
608 Fig. 7 shows the probability of each value of $\cos{\theta}$ for molecules in the interior of the cluster (squares) and for molecules included in the convex hull (circles).
609
610 \begin{figure}
627   \includegraphics[width=\linewidth]{pAngle}
628 < \caption{SPC/E water clusters: only minor dewetting at the boundary}
629 < \label{pAngle}
628 > \caption{Distribution of $\cos{\theta}$ values for molecules on the
629 >  interior of the cluster (squares) and for those participating in the
630 >  convex hull (circles) at a variety of pressures.  The Langevin hull
631 >  exhibits minor dewetting behavior with exposed oxygen sites on the
632 >  hull water molecules.  The orientational preference for exposed
633 >  oxygen appears to be independent of applied pressure. }
634 > \label{fig:pAngle}
635   \end{figure}
636  
637 < As expected, interior molecules (those not included in the convex hull) maintain a bulk-like structure with a uniform distribution of orientations. Molecules included in the convex hull show a slight preference for values of $\cos{\theta} < 0.$ These values correspond to molecules with a hydrogen directed toward the exterior of the cluster, forming a dangling hydrogen bond.
637 > As expected, interior molecules (those not included in the convex
638 > hull) maintain a bulk-like structure with a uniform distribution of
639 > orientations. Molecules included in the convex hull show a slight
640 > preference for values of $\cos{\theta} < 0.$ These values correspond
641 > to molecules with oxygen directed toward the exterior of the cluster,
642 > forming a dangling hydrogen bond acceptor site.
643  
644 < In the absence of an electrostatic contribution from the exterior bath, the orientational distribution of water molecules included in the Langevin Hull will slightly resemble the distribution at a neat water liquid/vapor interface. Previous molecular dynamics simulations of SPC/E water \cite{Taylor1996} have shown that molecules at the liquid/vapor interface favor an orientation where one hydrogen protrudes from the liquid phase. This behavior is demonstrated by experiments \cite{Du1994} \cite{Scatena2001} showing that approximately one-quarter of water molecules at the liquid/vapor interface form dangling hydrogen bonds. The negligible preference shown in these cluster simulations could be removed through the introduction of an implicit solvent model, which would provide the missing electrostatic interactions between the cluster molecules and the surrounding temperature/pressure bath.
644 > In the absence of an electrostatic contribution from the exterior
645 > bath, the orientational distribution of water molecules included in
646 > the Langevin Hull will slightly resemble the distribution at a neat
647 > water liquid/vapor interface.  Previous molecular dynamics simulations
648 > of SPC/E water \cite{Taylor1996} have shown that molecules at the
649 > liquid/vapor interface favor an orientation where one hydrogen
650 > protrudes from the liquid phase. This behavior is demonstrated by
651 > experiments \cite{Du1994} \cite{Scatena2001} showing that
652 > approximately one-quarter of water molecules at the liquid/vapor
653 > interface form dangling hydrogen bonds. The negligible preference
654 > shown in these cluster simulations could be removed through the
655 > introduction of an implicit solvent model, which would provide the
656 > missing electrostatic interactions between the cluster molecules and
657 > the surrounding temperature/pressure bath.
658  
659 < The orientational preference exhibited by hull molecules is significantly weaker than the preference caused by an explicit hydrophobic bounding potential. Additionally, the Langevin Hull does not require that the orientation of any molecules be fixed in order to maintain bulk-like structure, even at the cluster surface.
659 > The orientational preference exhibited by hull molecules in the
660 > Langevin hull is significantly weaker than the preference caused by an
661 > explicit hydrophobic bounding potential.  Additionally, the Langevin
662 > Hull does not require that the orientation of any molecules be fixed
663 > in order to maintain bulk-like structure, even at the cluster surface.
664  
665   \subsection{Heterogeneous nanoparticle / water mixtures}
666  
667   \section{Discussion}
668   \label{sec:discussion}
669  
670 + The Langevin Hull samples the isobaric-isothermal ensemble for
671 + non-periodic systems by coupling the system to an bath characterized
672 + by pressure, temperature, and solvent viscosity.  This enables the
673 + study of heterogeneous systems composed of materials of significantly
674 + different compressibilities.  Because the boundary is dynamically
675 + determined during the simulation and the molecules interacting with
676 + the boundary can change, the method and has minimal perturbations on
677 + the behavior of molecules at the edges of the simulation.  Further
678 + work on this method will involve implicit electrostatics at the
679 + boundary (which is missing in the current implementation) as well as
680 + more sophisticated treatments of the surface geometry (alpha
681 + shapes\cite{EDELSBRUNNER:1994oq,EDELSBRUNNER:1995cj} and Tight
682 + Cocone\cite{Dey:2003ts}). The non-convex hull geometries are
683 + significantly more expensive ($\mathcal{O}(N^2)$) than the convex hull
684 + ($\mathcal{O}(N \log N)$), but would enable the use of hull volumes
685 + directly in computing the compressibility of the sample.
686 +
687   \section*{Appendix A: Computing Convex Hulls on Parallel Computers}
688  
689 + In order to use the Langevin Hull for simulations on parallel
690 + computers, one of the more difficult tasks is to compute the bounding
691 + surface, facets, and resistance tensors when the processors have
692 + incomplete information about the entire system's topology.  Most
693 + parallel decomposition methods assign primary responsibility for the
694 + motion of an atomic site to a single processor, and we can exploit
695 + this to efficiently compute the convex hull for the entire system.
696 +
697 + The basic idea involves splitting the point cloud into
698 + spatially-overlapping subsets and computing the convex hulls for each
699 + of the subsets.  The points on the convex hull of the entire system
700 + are all present on at least one of the subset hulls. The algorithm
701 + works as follows:
702 + \begin{enumerate}
703 + \item Each processor computes the convex hull for its own atomic sites
704 +  (left panel in Fig. \ref{fig:parallel}).
705 + \item The Hull vertices from each processor are passed out to all of
706 +  the processors, and each processor assembles a complete list of hull
707 +  sites (this is much smaller than the original number of points in
708 +  the point cloud).
709 + \item Each processor computes the global convex hull (right panel in
710 +  Fig. \ref{fig:parallel}) using only those points that are the union
711 +  of sites gathered from all of the subset hulls.  Delaunay
712 +  triangulation is then done to obtain the facets of the global hull.
713 + \end{enumerate}
714 +
715 + \begin{figure}
716 + \includegraphics[width=\linewidth]{parallel}
717 + \caption{When the sites are distributed among many nodes for parallel
718 +  computation, the processors first compute the convex hulls for their
719 +  own sites (dashed lines in left panel). The positions of the sites
720 +  that make up the subset hulls are then communicated to all
721 +  processors (middle panel).  The convex hull of the system (solid line in right panel) is the convex hull of the points on the union of the subset hulls.}
722 + \label{fig:parallel}
723 + \end{figure}
724 +
725 + The individual hull operations scale with
726 + $\mathcal{O}(\frac{n}{p}\log\frac{n}{p})$ where $n$ is the total
727 + number of sites, and $p$ is the number of processors.  These local
728 + hull operations create a set of $p$ hulls each with approximately
729 + $\frac{n}{3pr}$ sites (for a cluster of radius $r$). The worst-case
730 + communication cost for using a ``gather'' operation to distribute this
731 + information to all processors is $\mathcal{O}( \alpha (p-1) + \frac{n
732 +  \beta (p-1)}{3 r p^2})$, while the final computation of the system
733 + hull scales as $\mathcal{O}(\frac{n}{3r}\log\frac{n}{3r})$.
734 +
735 + For a large number of atoms on a moderately parallel machine, the
736 + total costs are dominated by the computations of the individual hulls,
737 + and communication of these hulls to so the Langevin hull sees roughly
738 + linear speed-up with increasing processor counts.
739 +
740   \section*{Acknowledgments}
741   Support for this project was provided by the
742   National Science Foundation under grant CHE-0848243. Computational

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines