Fast solvers for charge distribution models on shared memory platforms. (English) Zbl 1431.65026

Summary: Including atom polarizability in molecular dynamics (MD) simulations is important for high-fidelity simulations. Linear solvers for charge models that are used to dynamically determine atom polarizations constitute significant bottlenecks in terms of time-to-solution and the overall scalability of polarizable and reactive force fields. We present properly customized preconditioning techniques to accelerate the iterative solvers used for several charge models and develop their efficient shared memory parallel implementations in the open source PuReMD (Purdue Reactive Molecular Dynamics) software package. With these goals in mind, special attention has been paid to minimizing the mean combined preconditioner construction and solver time. Detailed analysis of how different preconditioning techniques affect solver convergence rate and the overall performance is presented. Incomplete LU/Cholesky and sparse approximate inverse (SAI) based schemes that produce good quality factors with a relatively low number of nonzeros have been observed to yield significant speedups over a baseline Jacobi preconditioner. These results are significant as they can enable efficient simulations of small to moderate-sized systems on multicore computers, but, more importantly, they serve as a basis for distributed memory solvers.


65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices


Full Text: DOI


[1] H. M. Aktulga, J. C. Fogarty, S. A. Pandit, and A. Y. Grama, Parallel reactive molecular dynamics: Numerical methods and algorithmic techniques, Parallel Comput., 38 (2012), pp. 245-259.
[2] H. M. Aktulga, S. A. Pandit, A. C. T. Van Duin, and A. Y. Grama, Reactive molecular dynamics: Numerical methods and algorithmic techniques, SIAM J. Sci. Comput., 34 (2012), pp. C1-C23, https://doi.org/10.1137/100808599. · Zbl 1387.65128
[3] H. M. Aktulga, C. Knight, P. Coffman, K. A. O’Hearn, T.-R. Shan, and W. Jiang, Optimizing the performance of reactive molecular dynamics simulations for many-core architectures, Int. J. High Performance Comput. Appl., 33 (2019), pp. 304-321, https://doi.org/10.1177/1094342017746221.
[4] J. R. Allwright, R. Bordawekar, P. D. Coddington, K. Dincer, and C. L. Martin, A Comparison of Parallel Graph Coloring Algorithms, Technical report SCCS-666, Northeast Parallel Architecture Center, Syracuse University, 1995.
[5] M. Benzi and M. Tuma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput., 19 (1998), pp. 968-994, https://doi.org/10.1137/S1064827595294691. · Zbl 0930.65027
[6] M. Benzi and M. Tûma, A comparative study of sparse approximate inverse preconditioners, Appl. Numer. Math., 30 (1999), pp. 305-340, https://doi.org/10.1016/S0168-9274(98)00118-4. · Zbl 0949.65043
[7] E. F. F. Botta and A. van der Ploeg, Renumbering strategies based on multi-level techniques combined with ILU-decompositions, Zh. Vychisl. Mat. Mat. Fiz., 37 (1997), pp. 1294-1300 (in Russian); translation in Comput. Math. Math. Phys., 37 (1997), pp. 1252-1258. · Zbl 0946.65019
[8] B. Carpentieri and M. Bollhöfer, Symmetric inverse-based multilevel ILU preconditioning for solving dense complex non-Hermitian systems in electromagnetics, Progr. Electromagn. Res., 128 (2012), pp. 55-74, https://doi.org/10.2528/PIER12041006.
[9] Ü. V. Çataly\"urek, J. Feo, A. H. Gebremedhin, M. Halappanavar, and A. Pothen, Graph coloring algorithms for multi-core and massively multithreaded architectures, Parallel Comput., 38 (2012), pp. 576-594, https://doi.org/10.1016/j.parco.2012.07.001.
[10] E. Chow and A. Patel, Fine-grained parallel incomplete LU factorization, SIAM J. Sci. Comput., 37 (2015), pp. C169-C193, https://doi.org/10.1137/140968896. · Zbl 1320.65048
[11] W. D. Cornell, P. Cieplak, C. I. Bayly, I. R. Gould, K. M. Merz, D. M. Ferguson, D. C. Spellmeyer, et al., A second generation force field for the simulation of proteins, nucleic acids, and organic molecules, J. Am. Chem. Soc., 117 (1995), pp. 5179-5197.
[12] M. Grote and T. Huckle, Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18 (1997), pp. 838-853, https://doi.org/10.1137/S1064827594276552. · Zbl 0872.65031
[13] T. A. Halgren and W. Damm, Polarizable force fields, Current Opinion in Structural Biology, 11 (2001), pp. 236-242.
[14] P. Hénon and Y. Saad, A parallel multistage ILU factorization based on a hierarchical graph decomposition, SIAM J. Sci. Comput., 28 (2006), pp. 2266-2293, https://doi.org/10.1137/040608258. · Zbl 1126.65028
[15] P. Li and K. M. Merz, Jr., Metal ion modeling using classical mechanics, Chem. Rev., 117 (2017), pp. 1564-1686, https://doi.org/10.1021/acs.chemrev.6b00440.
[16] A. D. MacKerell, Jr., D. Bashford, M. Bellott, R. L. Dunbrack, J. D. Evanseck, M. J. Field, S. Fischer, et al., All-atom empirical potential for molecular modeling and dynamics studies of proteins, J. Phys. Chem. B, 102 (1998), pp. 3586-3616.
[17] W. J. Mortier, S. K. Ghosh, and S. Shankar, Electronegativity-equalization method for the calculation of atomic charges in molecules, J. Am. Chem. Soc., 108 (1986), pp. 4315-4320.
[18] W. J. Mortier, K. Van Genechten, and J. Gasteiger, Electronegativity equalization: Application and parametrization, J. Am. Chem. Soc., 107 (1985), pp. 829-835, https://doi.org/10.1021/ja00290a017.
[19] A. Nakano, Parallel multilevel preconditioned conjugate-gradient approach to variable-charge molecular dynamics, Comput. Phys. Comm., 104 (1997), pp. 59-69.
[20] M. Naumov, Parallel Incomplete-LU and Cholesky Factorization in the Preconditioned Iterative Methods on the GPU, Technical report NVR-2012-003, NVIDA, 2012.
[21] M. Naumov, P. Castonguay, and J. Cohen, Parallel Graph Coloring with Applications to the Incomplete-LU Factorization on the GPU, Technical report NVR-2015-001, NVIDA, 2015.
[22] R. A. Nistor, J. G. Polihronov, M. H. Müser, and N. J. Mosey, A generalization of the charge equilibration method for nonmetallic materials, J. Chem. Phys., 125 (2006), 094108.
[23] K. O’Hearn and H. Aktulga, Towards fast scalable solvers for charge equilibration in molecular dynamics applications, in Proceeding of the 2016 7th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA), IEEE, 2017, pp. 9-16, https://doi.org/10.1109/ScalA.2016.006.
[24] X.-M. Pan and X.-Q. Sheng, Sparse approximate inverse preconditioner for multiscale dynamic electromagnetic problems, Radio Sci., 49 (2014), pp. 1041-1051, https://doi.org/10.1002/2014RS005387.
[25] S. Patel and C. L. Brooks III, Fluctuating charge force fields: Recent developments and applications from small molecules to macromolecular biological systems, Mol. Simul., 32 (2006), pp. 231-249. · Zbl 1173.81357
[26] S. Plimpton, Fast parallel algorithms for short-range molecular dynamics, J. Comput. Phys., 117 (1995), pp. 1-19. · Zbl 0830.65120
[27] A. K. Rappé, C. J. Casewit, K. S. Colwell, W. A. Goddard III, and W. M. Skiff, UFF, a full periodic table force field for molecular mechanics and molecular dynamics simulations, J. Am. Chem. Soc., 114 (1992), pp. 10024-10035.
[28] A. K. Rappe and W. A. Goddard III, Charge equilibration for molecular dynamics simulations, J. Phys. Chem., 95 (1991), pp. 3358-3363, https://doi.org/10.1021/j100161a070.
[29] S. W. Rick and S. J. Stuart, Potentials and algorithms for incorporating polarizability in computer simulations, Rev. Comput. Chem., 18 (2002), pp. 89-146.
[30] Y. Saad, ILUT: A dual threshold incomplete LU factorization, Numer. Linear Algebra Appl., 1 (1994), pp. 387-402. · Zbl 0838.65026
[31] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003 https://doi.org/10.1137/1.9780898718003. · Zbl 1031.65046
[32] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, 7 (1986), pp. 856-869, https://doi.org/10.1137/0907058. · Zbl 0599.65018
[33] T. P. Senftle, S. Hong, M. M. Islam, S. B. Kylasa, Y. Zheng, Y. K. Shin, C. Junkermeier, et al., The ReaxFF reactive force-field: Development, applications and future directions, Nature NPJ Computational Materials, 2 (2016), 15011.
[34] A. C. T. van Duin, S. Dasgupta, F. Lorant, and W. A. Goddard, ReaxFF: A reactive force field for hydrocarbons, J. Phys. Chem. A, 105 (2001), pp. 9396-9409.
[35] T. Verstraelen, P. W. Ayers, V. Van Speybroeck, and M. Waroquier, ACKS2: Atom-condensed Kohn-Sham DFT approximated to second order, J. Chem. Phys., 138 (2013), 074108, https://doi.org/10.1063/1.4791569.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.