Parallel implementation of efficient charge–charge interaction evaluation scheme in periodic divide‐and‐conquer density‐functional tight‐binding calculations

A low‐computational‐cost algorithm and its parallel implementation for periodic divide‐and‐conquer density‐functional tight‐binding (DC‐DFTB) calculations are presented. The developed algorithm enables rapid computation of the interaction between atomic partial charges, which is the bottleneck for applications to large systems, by means of multipole‐ and interpolation‐based approaches for long‐ and short‐range contributions. The numerical errors of energy and forces with respect to the conventional Ewald‐based technique can be under the control of the multipole expansion order, level of unit cell replication, and interpolation grid size. The parallel performance of four different evaluation schemes combining previous approaches and the proposed one are assessed using test calculations of a cubic water box on the K computer. The largest benchmark system consisted of 3,295,500 atoms. DC‐DFTB energy and forces for this system were obtained in only a few minutes when the proposed algorithm was activated and parallelized over 16,000 nodes in the K computer. The high performance using a single node workstation was also confirmed. In addition to liquid water systems, the feasibility of the present method was examined by testing solid systems such as diamond form of carbon, face‐centered cubic form of copper, and rock salt form of sodium chloride. © 2017 Wiley Periodicals, Inc.     

Efficient implementation of the fast multipole method

A number of computational techniques are described that reduce the effort related to the continuous fast multipole method, used for the evaluation of Coulomb matrix elements as needed in Hartree-Fock and density functional theories. A new extent definition for Gaussian charge distributions is proposed, as well as a new way of dividing distributions into branches. Also, a new approach for estimating the error caused by truncation of multipole expansions is presented. It is found that the use of dynamically truncated multipole expansions gives a speedup of a factor of 10 in the work required for multipole interactions, compared to the case when all interactions are computed using a fixed multipole expansion order. Results of benchmark calculations on three-dimensional systems are reported, demonstrating the usefulness of our present implementation of the fast multipole method.     

A long-range electrostatic potential based on the Wolf method charge-neutral condition

Molecular simulations rely heavily on a long range electrostatic Coulomb interaction. The Coulomb potential decays inversely with distance, indicating infinite effective range. In practice, molecular simulations do not directly take into account such an infinite interaction. Therefore, the Ewald, fast multipole, and cutoff methods are frequently used. Although cutoff methods are implemented easily and the calculations are fast, it has been pointed out that they produce serious artifacts. Wolf and coworkers recently discovered one source of the artifacts. They found that when the total charge in a cutoff sphere disappeared, the cutoff error is dramatically suppressed. The Wolf method uses the charge-neutral principle combined with a potential damping that is realized using a complementary error function. To date, many molecular simulation studies have demonstrated the accuracy and reliability of the Wolf method. We propose a novel long-range potential that is constructed only from the charge-neutral condition of the Wolf method without potential damping. We also show that three simulation systems, in which involve liquid sodium-chloride, TIP3P water, and a charged protein in explicit waters with neutralized ions using the new potential, provide accurate statistical and dielectric properties when compared with the particle mesh Ewald method.     

Ewald mesh method for quantum mechanical calculations

The Fourier transform Coulomb (FTC) method has been shown to be effective for the fast and accurate calculation of long-range Coulomb interactions between diffuse (low-energy cutoff) densities in quantum mechanical (QM) systems. In this work, we split the potential of a compact (high-energy cutoff) density into short-range and long-range components, similarly to how point charges are handled in the Ewald mesh methods in molecular mechanics simulations. With this linear scaling QM Ewald mesh method, the long-range potential of compact densities can be represented on the same grid as the diffuse densities that are treated by the FTC method. The new method is accurate and significantly reduces the amount of computational time on short-range interactions, especially when it is compared to the continuous fast multipole method.     

Performance of fast multipole methods for calculating electrostatic interactions in biomacromolecular simulations

The fast multipole method proposed by Greengard and Rokhlin (GR) is applied to large biomacromolecular systems. In this method, the system is divided into a hierarchy of cells, and electric field exerted on a particle is decomposed into two parts. The first part is a rapidly varying field due to nearby cells, so that it needs rigorous pairwise calculations. The second part is a slowly varying local field due to distant cells; hence, it allows rapid calculations through a multipole expansion technique. In this work, two additional possibilities for improving the performance are numerically examined. The first is an improvement of the convergence of the expansion by increasing the number of nearby cells, without including higher-order multipole moments. The second is an acceleration of the calculations by the particle–particle and particle–mesh/multipole expansion (PPPM/MPE) method, which uses fast Fourier transform instead of the hierarchy. For this purpose, the PPPM/MPE method originally developed by the authors for a periodic system is extended to a nonperiodic isolated system. The advantages and disadvantages of the GR and PPPM/MPE methods are discussed for both periodic and isolated systems. It is numerically shown that these methods with reasonable costs can reduce the error in potential felt by each particle to 0.1–1 kcal/mol, much smaller than the 30-kcal/mol error involved in conventional simple truncations. © 1994 by 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     

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.     

Evaluation of atomic pressure in the multiple time‐step integration algorithm

In molecular dynamics (MD) calculations, reduction in calculation time per MD loop is essential. A multiple time‐step (MTS) integration algorithm, the RESPA (Tuckerman and Berne, J. Chem. Phys. 1992, 97, 1990–2001), enables reductions in calculation time by decreasing the frequency of time‐consuming long‐range interaction calculations. However, the RESPA MTS algorithm involves uncertainties in evaluating the atomic interaction‐based pressure (i.e., atomic pressure) of systems with and without holonomic constraints. It is not clear which intermediate forces and constraint forces in the MTS integration procedure should be used to calculate the atomic pressure. In this article, we propose a series of equations to evaluate the atomic pressure in the RESPA MTS integration procedure on the basis of its equivalence to the Velocity‐Verlet integration procedure with a single time step (STS). The equations guarantee time‐reversibility even for the system with holonomic constrants. Furthermore, we generalize the equations to both (i) arbitrary number of inner time steps and (ii) arbitrary number of force components (RESPA levels). The atomic pressure calculated by our equations with the MTS integration shows excellent agreement with the reference value with the STS, whereas pressures calculated using the conventional ad hoc equations deviated from it. Our equations can be extended straightforwardly to the MTS integration algorithm for the isothermal NVT and isothermal–isobaric NPT ensembles. © 2017 Wiley Periodicals, Inc.     

Gaussian split Ewald: A fast Ewald mesh method for molecular simulation

Gaussian split Ewald (GSE) is a versatile Ewald mesh method that is fast and accurate when used with both real-space and k-space Poisson solvers. While real-space methods are known to be asymptotically superior to k-space methods in terms of both computational cost and parallelization efficiency, k-space methods such as smooth particle-mesh Ewald (SPME) have thus far remained dominant because they have been more efficient than existing real-space methods for simulations of typical systems in the size range of current practical interest. Real-space GSE, however, is approximately a factor of 2 faster than previously described real-space Ewald methods for the level of force accuracy typically required in biomolecular simulations, and is competitive with leading k-space methods even for systems of moderate size. Alternatively, GSE may be combined with a k-space Poisson solver, providing a conveniently tunable k-space method that performs comparably to SPME. The GSE method follows naturally from a uniform framework that we introduce to concisely describe the differences between existing Ewald mesh methods.     

Pressure tensor for electrostatic interaction calculated by fast multipole method with periodic boundary condition

A microscopic expression of the pressure tensor using the fast multipole method (FMM) with periodic boundary conditions has been derived. The pressure tensor calculated using this expression has been compared with that obtained using the Ewald method with high accuracy. The precision of the pressure tensor can be controlled as a function of expansion order p of FMM. Using the calculated pressure tensor, the constant pressure molecular dynamics calculation with fully fluctuating cell can be performed for anisotropic systems such as crystals, metals, liquid crystals, glasses, polymers, lipid bilayers, and interfacial regions between two phases. © 2018 Wiley Periodicals, Inc.     

The ENUF method—Ewald summation based on nonuniform fast Fourier transform: Implementation,parallelization, and application

Computer simulations of model systems are widely used to explore striking phenomena in promising applications spanning from physics, chemistry, biology, to materials science and engineering. The long range electrostatic interactions between charged particles constitute a prominent factor in determining structures and states of model systems. How to efficiently calculate electrostatic interactions in simulation systems subjected to partial or full periodic boundary conditions has been a grand challenging task. In the past decades, a large variety of computational schemes has been proposed, among which the Ewald summation method is the most reliable route to accurately deal with electrostatic interactions between charged particles in simulation systems. In addition, extensive efforts have been done to improve computational efficiencies of the Ewald summation based methods. Representative examples are approaches based on cutoffs, reaction fields, multi-poles, multi-grids, and particle-mesh schemes. We sketched an ENUF method, an abbreviation for the Ewald summation method based on the nonuniform fast Fourier transform technique, and have implemented this method in particle-based simulation packages to calculate electrostatic energies and forces at micro- and mesoscopic levels. Extensive computational studies of conformational properties of polyelectrolytes, dendrimer-membrane complexes, and ionic fluids demonstrated that the ENUF method and its derivatives conserve both energy and momentum to floating point accuracy, and exhibit a computational complexity of with optimal physical parameters. These ENUF based methods are attractive alternatives in molecular simulations where high accuracy and efficiency of simulation methods are needed to accelerate calculations of electrostatic interactions at extended spatiotemporal scales.     

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.     

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.     

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.     

A smooth‐particle mesh Ewald method for DL_POLY molecular dynamics simulation package on the Fujitsu VPP700

An N⋅ log (N) smooth‐particle mesh Ewald method has been incorporated into the DL_POLY molecular dynamics simulation package. The performance of the new code has been tested on a Fujitsu VPP700 for several DL_POLY‐specific benchmark systems. The new method is highly vectorizable, and makes use of the extremely efficient Fast Fourier Transforms on the Fujitsu vector machine. In calculations of the coulombic forces in periodic systems requiring large reciprocal space vectors, the new code was found to be considerably faster than the conventional Ewald method. © 2000 John Wiley & Sons, Inc. J Comput Chem 21: 1187–1191, 2000     

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.     

Applications of fourier transforms in molecular orbital theory

Fourier transform methods introduced by Harris are applied to the evaluation of Frenkel exciton lattice sums. The slowly-convergent direct lattice sum is converted into a rapidly-convergent reciprocal lattice sum which includes all orders in the multipole expansion. A simple example is discussed, and the calculated exciton energy as a function of wave number is compared with the results of the Ewald method.     

Linear-scaling formation of Kohn-Sham Hamiltonian: application to the calculation of excitation energies and polarizabilities of large molecular systems

We present calculations of excitation energies and polarizabilities in large molecular systems at the local-density and generalized-gradient approximation levels of density-functional theory (DFT). Our results are obtained using a linear-scaling DFT implementation in the program system DALTON for the formation of the Kohn-Sham Hamiltonian. For the Coulomb contribution, we introduce a modification of the fast multipole method to calculations over Gaussian charge distributions. It affords a simpler implementation than the original continuous fast multipole method by partitioning the electrostatic Coulomb interactions into "classical" and "nonclassical" terms which are explicitly evaluated by linear-scaling multipole techniques and a modified two-electron integral code, respectively. As an illustration of the code, we have studied the singlet and triplet excitation energies as well as the static and dynamic polarizabilities of polyethylenes, polyenes, polyynes, and graphite sheets with an emphasis on the trends observed with system size.     

Computation of general multipole moment expansions for N atoms by MAPLE

A program written in the MAPLE symbolic computational language was written to compute analytic and numerical expressions for the long-range multipole moment expansion of the electrostatic (Coulombic) perturbation operator for a system of N atoms in arbitrary orientations in space. These expressions are written in terms of the multipole moment operators on individual interacting atoms. The program was tested on a system consisting of a ground-state hydrogen atom interacting with two protons in three different configurations, and the results were found to be in agreement with manual calculations. This approach can produce, with relative ease, the long-range multipole expansion for systems with large numbers of interacting atoms or ions. © 1997 John Wiley & Sons, Inc. Int J Quant Chem 62 : 343–351, 1997     

Short-time self-diffusion coefficient of a particle in a colloidal suspension bounded by a microchannel: virial expansions and simulation

Self-diffusion of colloidal particles confined to a cylindrical microchannel is considered theoretically and numerically. Virial expansion of the self-diffusion coefficient is performed. Two-body and three-body hydrodynamic interactions are evaluated with high precision using the multipole method. The multipole expansion algorithm is also used to perform numerical simulations of the self-diffusion coefficient, valid for all possible particle packing fractions. Comparison with earlier results shows that the widely used method of reflections is insufficient for calculations of hydrodynamic interactions even for small packing fractions and small particles radii, contrary to the prevalent opinion.