Extension of the fast multipole method for the rectangular cells with an anisotropic partition tree structure

The fast multipole method (FMM) is an order N method for the numerically rigorous calculation of the electrostatic interactions among point charges in a system of interest. The FMM is utilized for massively parallelized software for molecular dynamics (MD) calculations. However, an inconvenient limitation is imposed on the implementation of the FMM: In three-dimensional case, a cubic MD unit cell is hierarchically divided by the octree partitioning under isotropic periodic boundary conditions along three axes. Here, we extended the FMM algorithm adaptive to a rectangular MD unit cell with different periodicity along the axes by applying an anisotropic hierarchical partitioning. The algorithm was implemented into the parallelized general-purpose MD calculation software designed for a system with uniform distribution of point charges in the unit cell. The partition tree can be a mixture of binary and ternary branches, the branches being chosen arbitrarily with respect to the coordinate axes at any levels. Errors in the calculated electrostatic interactions are discussed in detail for a selected partition tree structure. The extension enables us to execute MD calculations under more general conditions for the shape of the unit cell, partition tree, and boundary conditions, keeping the accuracy of the calculated electrostatic interactions as high as that with the conventional FMM. An extension of the present FMM algorithm to other prime number branches, such as 5 and 7, is straightforward.     

Extension of adaptive tree code and fast multipole methods to high angular momentum particle charge densities

The development and implementation of a tree code (TC) and fast multipole method (FMM) for the efficient, linear-scaling calculation of long-range electrostatic interactions of particle distributions with variable shape and multipole character are described. The target application of these methods are stochastic boundary molecular simulations with polarizable force fields and/or combined quantum mechanical/molecular mechanical potentials. Linear-scaling is accomplished through the adaptive decomposition of the system into a hierarchy of interacting particle sets. Two methods for effecting this decomposition are evaluated: fluc-splitting and box-splitting, for which the latter is demonstrated to be generally more accurate. In addition, a generalized termination criterion is developed that delivers optimal performance at fixed error tolerance that, in the case of quadrupole-represented Drude water, effects a speed-up by a factor of 2-3 relative to a multipole-independent termination criteria. The FMM is shown to be approximately 2-3 times faster than the TC, independent of the system size and multipole order of the particles. The TC and FMM are tested for a variety of static and polarizable water systems, and for the the 70S ribosome functional complex containing an assembly of transfer and messenger RNAs.     

Midpoint cell method for hybrid (MPI+OpenMP) parallelization of molecular dynamics simulations

We have developed a new hybrid (MPI+OpenMP) parallelization scheme for molecular dynamics (MD) simulations by combining a cell‐wise version of the midpoint method with pair‐wise Verlet lists. In this scheme, which we call the midpoint cell method, simulation space is divided into subdomains, each of which is assigned to a MPI processor. Each subdomain is further divided into small cells. The interaction between two particles existing in different cells is computed in the subdomain containing the midpoint cell of the two cells where the particles reside. In each MPI processor, cell pairs are distributed over OpenMP threads for shared memory parallelization. The midpoint cell method keeps the advantages of the original midpoint method, while filtering out unnecessary calculations of midpoint checking for all the particle pairs by single midpoint cell determination prior to MD simulations. Distributing cell pairs over OpenMP threads allows for more efficient shared memory parallelization compared with distributing atom indices over threads. Furthermore, cell grouping of particle data makes better memory access, reducing the number of cache misses. The parallel performance of the midpoint cell method on the K computer showed scalability up to 512 and 32,768 cores for systems of 20,000 and 1 million atoms, respectively. One MD time step for long‐range interactions could be calculated within 4.5 ms even for a 1 million atoms system with particle‐mesh Ewald electrostatics. © 2014 Wiley Periodicals, Inc.     

Efficient lookup table using a linear function of inverse distance squared

The major bottleneck in molecular dynamics (MD) simulations of biomolecules exist in the calculation of pairwise nonbonded interactions like Lennard‐Jones and long‐range electrostatic interactions. Particle‐mesh Ewald (PME) method is able to evaluate long‐range electrostatic interactions accurately and quickly during MD simulation. However, the evaluation of energy and gradient includes time‐consuming inverse square roots and complementary error functions. To avoid such time‐consuming operations while keeping accuracy, we propose a new lookup table for short‐range interaction in PME by defining energy and gradient as a linear function of inverse distance squared. In our lookup table approach, densities of table points are inversely proportional to squared pair distances, enabling accurate evaluation of energy and gradient at small pair distances. Regardless of the inverse operation here, the new lookup table scheme allows fast pairwise nonbonded calculations owing to efficient usage of cache memory. © 2013 Wiley Periodicals, Inc.     

Accelerating molecular dynamic simulation on the cell processor and Playstation 3

Implementation of molecular dynamics (MD) calculations on novel architectures will vastly increase its power to calculate the physical properties of complex systems. Herein, we detail algorithmic advances developed to accelerate MD simulations on the Cell processor, a commodity processor found in PlayStation 3 (PS3). In particular, we discuss issues regarding memory access versus computation and the types of calculations which are best suited for streaming processors such as the Cell, focusing on implicit solvation models. We conclude with a comparison of improved performance on the PS3's Cell processor over more traditional processors.     

An adaptive treecode for computing nonbonded potential energy in classical molecular systems

A treecode algorithm is presented for rapid computation of the nonbonded potential energy in classical molecular systems. The algorithm treats a general form of pairwise particle interaction with the Coulomb and London dispersion potentials as special cases. The energy is computed as a sum of group–group interactions using a variant of Appel's recursive strategy. Several adaptive techniques are employed to reduce the execution time. These include an adaptive tree with nonuniform rectangular cells, variable order multipole approximation, and a run‐time choice between direct summation and multipole approximation for each group–group interaction. The multipole approximation is derived by Taylor expansion in Cartesian coordinates, and the necessary coefficients are computed using a recurrence relation. An error bound is derived and used to select the order of approximation. Test results are presented for a variety of systems. © 2000 John Wiley & Sons, Inc. J Comput Chem 22: 184–195, 2001     

Linear-scaling multipole-accelerated Gaussian and finite-element Coulomb method

A linear-scaling implementation of the Gaussian and finite-element Coulomb (GFC) method is presented for the rapid computation of the electronic Coulomb potential. The current work utilizes the fast multipole method (FMM) for the evaluation of the Poisson equation boundary condition. The FMM affords significant savings for small- and medium-sized systems and overcomes the bottleneck in the GFC method for very large systems. Compared to an exact analytical treatment of the boundary, more than 100-fold speedups are observed for systems with more than 1000 basis functions without any significant loss of accuracy. We present CPU times to demonstrate the effectiveness of the linear-scaling GFC method for both one-dimensional polyalanine chains and the challenging case of three-dimensional diamond fragments.     

Fast multipole method for three-dimensional systems with periodic boundary condition in two directions

We derived a new expression for the electrostatic interaction of three-dimensional charge-neutral systems with two-dimensional periodic boundary conditions (slab geometry) using a fast multipole method (FMM). Contributions from all the image cells are expressed as a sum of real and reciprocal space terms, and a self-interaction term. The reciprocal space contribution consists of two parts: zero and nonzero terms of the absolute value of the reciprocal lattice vector. To test the new expressions, electrostatic interactions were calculated for a randomly placed charge distribution in a cubic box and liquid water produced by molecular dynamics calculation. The accuracy could be controlled by the degree of expansion of the FMM. In the present expression, the computational complexity of the electrostatic interaction of N-particle systems is order N, which is superior to that of the conventional two-dimensional periodic Ewald method for a slab geometry and the particle mesh Ewald method with a large empty space at an interface of the unit cell. © 2020 Wiley Periodicals, Inc.     

Free energy of solvation of a small Lennard–Jones particle

In molecular dynamics (MD) and Monte Carlo (MC) free energy calculations, the choices of the thermodynamic paths from state a to state b affect the accuracy of the result and the efficiency of the programs. Most of the problems occur at the initial stages of growing in a new particle into a solvent. Based on statistical mechanical perturbation theory, an accurate and efficient direct calculation of inserting a small Lennard–Jones particle into solvent is derived. This eliminates the need for calculation of the initial stages of growing in a new particle by MD or MC simulation. Examples are given to show the utility of direct calculation. The recommended procedure is to use direct calculation for a small Lennard–Jones particle and then use MD or MC simulations to calculate the ΔG of changing the small Lennard–Jones particle into the target molecule. © 1994 by John Wiley & Sons, Inc.     

The midpoint method for parallelization of particle simulations

The evaluation of interactions between nearby particles constitutes the majority of the computational workload involved in classical molecular dynamics (MD) simulations. In this paper, we introduce a new method for the parallelization of range-limited particle interactions that proves particularly suitable to MD applications. Because it applies not only to pairwise interactions but also to interactions involving three or more particles, the method can be used for evaluation of both nonbonded and bonded forces in a MD simulation. It requires less interprocessor data transfer than traditional spatial decomposition methods at all but the lowest levels of parallelism. It gains an additional practical advantage in certain commonly used interprocessor communication networks by distributing the communication burden more evenly across network links and by decreasing the associated latency. When used to parallelize MD, it further reduces communication requirements by allowing the computations associated with short-range nonbonded interactions, long-range electrostatics, bonded interactions, and particle migration to use much of the same communicated data. We also introduce certain variants of this method that can significantly improve the balance of computational load across processors.     

Molecular dynamics integration and molecular vibrational theory. II. Simulation of nonlinear molecules

A series of molecular dynamics (MD) simulations of nonlinear molecules has been performed to test the efficiency of newly introduced semianalytical second-order symplectic time-reversible MD integrators that combine MD and the standard theory of molecular vibrations. The simulation results indicate that for the same level of accuracy, the new algorithms allow significantly longer integration time steps than the standard second-order symplectic leap-frog Verlet method. Since the computation cost per integration step using new MD integrators with longer time steps is approximately the same as for the standard method, a significant speed-up in MD simulation is achieved.     

Achieving linear-scaling computational cost for the polarizable continuum model of solvation

This work describes a new and low-scaling implementation of the polarizable continuum model (PCM) for computing the self-consistent solvent reaction field. The PCM approach is both general and accurate. It is applicable in the framework of both quantum and classical calculations, and also to hybrid quantum/classical methods. In order to further extend the range of applicability of PCM we addressed the problem of its computational cost. The generation of the finite-elements molecular cavity has been reviewed and reimplemented, achieving linear scaling for systems containing up to 500 atoms. Linear scaling behavior has been achieved also for the iterative solution of the PCM equations, by exploiting the fast multipole method (FMM) for computing electrostatic interactions. Numerical results for large (both linear and globular) chemical systems are discussed.     

Theoretical studies of molecular conformation. Derivation of an additive procedure for the computation of intramolecular interaction energies. Comparison withab initio SCF computations

An additive procedure (SIBFA) is developed for the rapid computation of conformational energy variations in very large molecules. The macromolecule is built out of constitutive molecular fragments and the intramolecular energy is computed as a sum of interaction energies between the fragments. The electrostatic and the polarization components are calculated using multicenter multipole expansions of theab initio SCF electron density of the fragments. The repulsion component is obtained as a sum of bond and lone pair interactions.Tests of the procedure on a series of model compounds containing ether oxygens and pyridine-like nitrogens are reported and compared with the results of correspondingab initio SCF calculations. The resulting methodology is compatible with the simultaneous computation of intermolecular interactions.     

Development of a parallel molecular dynamics code on SIMD computers: Algorithm for use of pair list criterion

In recent years several implementations of molecular dynamics (MD) codes have been reported on multiple instruction multiple data (MIMD) machines. However, very few implementations of MD codes on single instruction multiple data (SIMD) machines have been reported. The difficulty in using pair lists of nonbonded interactions is the major problem with MD codes for SIMD machines, such that, generally, the full connectivity computation has been used. We present an algorithm, the global cut-off algorithm (GCA), which permits the use of pair lists on SIMD machines. GCA is based on a probabilistic approach and requires the cut-off condition to be simultaneously verified on all nodes of the machine. The MD code used was taken from the GROMOS package; only the routines involved in the pair lists and in the computation of nonbonded interactions were rewritten for a parallel architecture. The remaining calculations were performed on the host computer. The algorithm has been tested on Quadrics computers for configurations of 32, 128, and 512 processors and for systems of 4000, 8000, 15,000, and 30,000 particles. Quadrics was developed by Istituto Nazionale di Fisica Nucleare (INFN) and marketed by Alenia Spazio. © 1998 John Wiley & Sons, Inc. J Comput Chem 19: 685–694, 1998     

A hierarchical algorithm for fast debye summation with applications to small angle scattering

Debye summation, which involves the summation of sinc functions of distances between all pair of atoms in three‐dimensional space, arises in computations performed in crystallography, small/wide angle X‐ray scattering (SAXS/WAXS), and small angle neutron scattering (SANS). Direct evaluation of Debye summation has quadratic complexity, which results in computational bottleneck when determining crystal properties, or running structure refinement protocols that involve SAXS or SANS, even for moderately sized molecules. We present a fast approximation algorithm that efficiently computes the summation to any prescribed accuracy ? in linear time. The algorithm is similar to the fast multipole method (FMM), and is based on a hierarchical spatial decomposition of the molecule coupled with local harmonic expansions and translation of these expansions. An even more efficient implementation is possible when the scattering profile is all that is required, as in small angle scattering reconstruction (SAS) of macromolecules. We examine the relationship of the proposed algorithm to existing approximate methods for profile computations, and show that these methods may result in inaccurate profile computations, unless an error‐bound derived in this article is used. Our theoretical and computational results show orders of magnitude improvement in computation complexity over existing methods, while maintaining prescribed accuracy. © 2012 Wiley Periodicals, Inc.     

Fast adaptive multipole method for computation of electrostatic energy in simulations of polyelectrolyte DNA

This article presents a fast adaptive method for the computation of long-range electrostatic interactions in computer simulations of polyelectrolyte DNA. Classically, the computation of electrostatic energy involves a direct summation of all pairwise in teractions due to the charged phosphate groups in the molecule. This results in an N-body interaction problem with an asymptotic time complexity of O(N²) which is computationally very expensive and limits the number of phosphate groups that can be used in computer simulations of polyelectrolyte DNA to at most several hundred. We describe an effort to speed up computer simulations of polyelectrolyte DNA with the use of a fast adaptive hierarchical algorithm for the computation of electrostatic energy (i.e., modified Debye–Hückel energy). The asymptotic time complexity is reduced to O(N) with the implementation of the fast hierarchical algorithm on serial computers. This is achieved by grouping phosphate groups into an adaptive hierarchical data structure and computing the interactions between groups using low order multipole and Taylor series expansions expressed in Cartesian coordinates. We first examine the accuracy and speed enhancements of the fast hierarchical method in the computation of the electrostatic energy of circular DNA at zero and high salt concentrations. The fast hierarchical method is further tested in a one-step Monte Carlo (MC) simulated annealing algorithm for closed circular supercoiled DNA. In all cases, we observe order of magnitude reductions in the computation time with negligible loss of numerical accuracy in the electrostatic energy computation. © 1996 by John Wiley & Sons, Inc.     

Efficient calculations of coulombic interactions in biomolecular simulations with periodic boundary conditions

To make improved treatments of electrostatic interactions in biomacromolecular simulations, two possibilities are considered. The first is the famous particle–particle and particle–mesh (PPPM) method developed by Hockney and Eastwood, and the second is a new one developed here in their spirit but by the use of the multipole expansion technique suggested by Ladd. It is then numerically found that the new PPPM method gives more accurate results for a two-particle system at small separation of particles. Preliminary numerical examination of the various computational methods for a single configuration of a model BPTI–water system containing about 24,000 particles indicates that both of the PPPM methods give far more accurate values with reasonable computational cost than do the conventional truncation methods. It is concluded the two PPPM methods are nearly comparable in overall performance for the many-particle systems, although the first method has the drawback that the accuracy in the total electrostatic energy is not high for configurations of charged particles randomly generated. © 1993 John Wiley & Sons, Inc.     

New parallel optimal‐parameter fast multipole method (OPFMM)

The three key translation equations of the fast multipole method (FMM) are deduced from the general polypolar expansions given earlier. Simplifications are introduced for the rotation‐based FMM that lead to a very compact FMM formalism. The optimum‐parameter searching procedure, a stable and efficient way of obtaining the optimum set of FMM parameters, is established with complete control over the tolerable error (ε). This new procedure optimizes the linear scaling with respect to the number of particles for a given ε. In addition, a new parallel FMM algorithm, which requires virtually no internode communication, is suggested that is suitable for the parallel construction of Fock matrices in electronic structure calculations. © 2001 John Wiley & Sons, Inc. J Comput Chem 22: 1484–1501, 2001     

Diffusion and viscosity of liquid tin: Green-Kubo relationship-based calculations from molecular dynamics simulations

Molecular dynamics (MD) simulations of liquid tin between its melting point and 1600 °C have been performed in order to interpret and discuss the ionic structure. The interactions between ions are described by a new accurate pair potential built within the pseudopotential formalism and the linear response theory. The calculated structure factor that reflects the main information on the local atomic order in liquids is compared to diffraction measurements. Having some confidence in the ability of this pair potential to give a good representation of the atomic structure, we then focused our attention on the investigation of the atomic transport properties through the MD computations of the velocity autocorrelation function and stress autocorrelation function. Using the Green-Kubo formula (for the first time to our knowledge for liquid tin) we determine the macroscopic transport properties from the corresponding microscopic time autocorrelation functions. The selfdiffusion coefficient and the shear viscosity as functions of temperature are found to be in good agreement with the experimental data.