×

A treecode based on barycentric Hermite interpolation for electrostatic particle interactions. (English) Zbl 1439.78003

Summary: A particle-cluster treecode based on barycentric Hermite interpolation is presented for fast summation of electrostatic particle interactions in 3D. The interpolation nodes are Chebyshev points of the 2nd kind in each cluster. It is noted that barycentric Hermite interpolation is scale-invariant in a certain sense that promotes the treecode’s efficiency. Numerical results for the Coulomb and screened Coulomb potentials show that the treecode run time scales like \(O(N\) log \(N)\), where \(N\) is the number of particles in the system. The advantage of the barycentric Hermite treecode is demonstrated in comparison with treecodes based on Taylor approximation and barycentric Lagrange interpolation.

MSC:

78A30 Electro- and magnetostatics
78A35 Motion of charged particles
65D05 Numerical interpolation
65Z05 Applications to the sciences
78A99 General topics in optics and electromagnetic theory

Software:

TABI; tabipb
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.E. Barnes, P. Hut, A hierarchical O(N log N) force-calculation algorithm, Nature 324 (1986), 446-449.
[2] E. Berriochoa, A. Cachafeiro, J. Díaz, J. Illán, Algorithms and convergence for Hermite interpolation based on extended Chebyshev nodal systems, Appl. Math. Comput. 234 (2014), 223-236. · Zbl 1303.65004
[3] J.-P. Berrut, L.N. Trefethen, Barycentric Lagrange interpolation, SIAM Rev. 46 (2004), 501-517. · Zbl 1061.65006
[4] G.A. Cisneros, M. Karttunen, P. Ren, C. Sagui, Classical electrostatics for biomolecular simulations, Chem. Rev. 114 (2014), 779-814.
[5] R. Cortez, The method of regularized Stokeslets, SIAM J. Sci. Comput., 23 (2001), 1204-1225. · Zbl 1064.76080
[6] R. Cortez, L. Fauci, A. Medovikov, The method of regularized Stokeslets in three dimensions: Analysis, validation, and application to helical swimming, Phys. Fluids 17 (2005), 031504. · Zbl 1187.76105
[7] M.E. Davis, J.A. McCammon, Electrostatics in biomolecular structure and dynamics, Chem. Rev. 90 (1990), 509-521.
[8] U. Essmann, L. Perera, M. Berkowitz, T. Darden, H. Lee, L. Pedersen, A smooth particle mesh Ewald method, J. Chem. Phys. 103 (1995), 8577-8593.
[9] W. Fong, E. Darve, The black-box fast multipole method, J. Comput. Phys. 228 (2009), 8712-8725. · Zbl 1177.65009
[10] W.-H. Geng, R. Krasny, A treecode-accelerated boundary integral Poisson-Boltzmann solver for solvated biomolecules, J. Comput. Phys. 247 (2013), 62-78. · Zbl 1349.78084
[11] L. Greengard, V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys. 73 (1987), 325-348. · Zbl 0629.65005
[12] W. Hackbusch, Z.P. Nowak, On the fast matrix multiplication in the boundary element method by panel clustering, Numer. Math. 54 (1989), 463-491. · Zbl 0641.65038
[13] D.J. Hardy, Z. Wu, J.C. Phillips, J.E. Stone, R.D. Skeel, K. Schulten, Multilevel summation method for electrostatic force evaluation, J. Chem. Theory Comput. 11 (2015), 766-779.
[14] N.J. Higham, The numerical stability of barycentric Lagrange interpolation, IMA J. Numer. Anal. 24 (2004), 547-556. · Zbl 1067.65016
[15] R.W. Hockney, J.W. Eastwood, Computer Simulation Using Particles, Taylor Francis, Bristol (1988). · Zbl 0662.76002
[16] B. Honig, A. Nicholls, Classical electrostatics in biology and chemistry, Science 268 (1995), 1144-1149.
[17] E. Jurrus, D. Engel, K. Star, K. Monson, J. Brandi, L.E. Felberg, D.H. Brookes, L. Wilson, J. Chen, K. Liles, M. Chun, P. Li, D.W. Gohara, T. Dolinsky, R. Konecny, D.R. Koes, J.E. Nielsen, T. Head-Gordon, W.H. Geng, R. Krasny, G.-W. Wei, M.J. Holst, J.A. McCammon, N.A. Baker, Improvements to the APBS biomolecular solvation software suite, Protein Science 27 (2018) 112-128.
[18] P. Li, H. Johnston, R. Krasny, A Cartesian treecode for screened Coulomb interactions, J. Comput. Phys. 228 (2009), 3858-3868. · Zbl 1165.78304
[19] J. Makino, Yet another fast multipole method without multipoles - Pseudoparticle multipole method, J. Comput. Phys. 151 (1999), 910-920. · Zbl 0934.65145
[20] M.W. Rostami, S.D. Olson, Kernel-independent fast multipole method within the framework of regularized Stokeslets, J. Fluid Struct. 67 (2016), 60-84.
[21] B. Sadiq, D. Viswanath, Barycentric Hermite interpolation, SIAM J. Sci. Comput. 35 (2013), A1254-A1270. · Zbl 1275.65010
[22] H.E. Salzer, Lagrangian interpolation at the Chebyshev points x_n,v = cos(vπ/n), v =0 (1) n; some unnoted advantages, Comput. J. 15 (1972), 156-159. · Zbl 0242.65007
[23] T. Schlick, Molecular Modeling and Simulation: An Interdisciplinary Guide, Springer, New York (2010), 2nd edition. · Zbl 1320.92007
[24] C. Schneider, W. Werner, Hermite interpolation: The Barycentric approach, Computing 46 (1991), 35-51. · Zbl 0726.65007
[25] L.N. Trefethen, Approximation Theory and Approximation Practice, SIAM, Philadelphia (2013). · Zbl 1264.41001
[26] N. Vaughn, L. Wilson, L.Wang, R. Krasny, GPU-accelerated barycentric treecodes, in preparation · Zbl 07695386
[27] L. Wang, R. Krasny, S. Tlupova, A kernel-independent treecode based on barycentric Lagrange interpolation, arXiv:1902.02250 · Zbl 1473.65025
[28] L. Ying, G. Biros, D. Zorin, A kernel-independent adaptive fast multipole algorithm in two and three dimensions, J. Comput. Phys. 196 (2004), 591-626. · Zbl 1053.65095
[29] L. Ying, A kernel independent fast multipole algorithm for radial basis functions, J. Comput. Phys. 213 (2006), 451-457. · Zbl 1089.65018
[30] Z. Zhang, S, Witham, E. Alexov, On the role of electrostatics in protein-protein interactions, Phys. Biol. 8 (2011), 035001.
[31] H.-X. Zhou, X. Pang, Electrostatic interactions in protein structure, folding, binding, and condensation, Chem. Rev. 118 (2018), 1691-1741.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.