Fast electrostatic force calculation on parallel computer clusters

作     者：Kia, Amirali Kim, Daejoong Darve, Eric 

作者机构：Stanford Univ Mech & Computat Div Stanford CA 94305 USA Sogang Univ Seoul 121742 South Korea 

出 版 物：《JOURNAL OF COMPUTATIONAL PHYSICS》 (计算物理学杂志)

年 卷 期：2008年第227卷第19期

页      面：8551-8567页

核心收录：

学科分类：07[理学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0702[理学-物理学] 

基　　金：NSF [CNS-0619926] 

主　　题：fast multipole method particle mesh Ewald plane wave parallel algorithm 

摘      要：The fast multipole method (FMM) and smooth particle mesh Ewald (SPME) are well known fast algorithms to evaluate long range electrostatic interactions in molecular dynamics and other fields. FMM is a multi-scale method which reduces the computation cost by approximating the potential due to a group of particles at a large distance using few multipole functions. This algorithm scales like O(N) for N particles. SPME algorithm is an O(N In N) method which is based on an interpolation of the Fourier space part of the Ewald sum and evaluating the resulting convolutions using fast Fourier transform (FFT). Those algorithms suffer from relatively poor efficiency on large parallel machines especially for mid-size problems around hundreds of thousands of atoms. A variation of the FMM, called PWA, based on plane wave expansions is presented in this paper. A new parallelization strategy for PWA, which takes advantage of the specific form of this expansion, is described. Its parallel efficiency is compared with SPME through detail time measurements on two different computer clusters. (C) 2008 Elsevier Inc. All rights reserved.