A New Parallel Kernel-Independent Fast Multipole Method

ABSTRACT

We present a new adaptive fast multipole algorithm and its parallel implementation. The algorithm is kernel-independent in the sense that the evaluation of pairwise interactions does not rely on any analytic expansions, but only utilizes kernel evaluations. The new method provides the enabling technology for many important problems in computational science and engineering. Examples include viscous flows, fracture mechanics and screened Coulombic interactions. Our MPI-based parallel implementation logically separates the computation and communication phases to avoid synchronization in the upward and downward computation passes, and thus allows us to fully exploit computation and communication overlapping. We measure isogranular and fixed-size scalability for a variety of kernels on the Pittsburgh Supercomputing Center's TCS-1 Alphaserver on up to 3000 processors. We have solved viscous flow problems with up to 2.1 billion unknowns and we have achieved 1.6 Tflops/s peak performance and 1.13 Tflops/s sustained performance.

REFERENCES

• 1: Christopher R. Anderson, An implementation of the fast multipole method without multipoles, SIAM Journal on Scientific and Statistical Computing, v.13 n.4, p.923-947, July 1992 [doi>10.1137/0913055]
• 2: [2] Satish Balay, Kris Buschelman, William D. Gropp, Dinesh Kaushik, Lois Curfman McInnes, and Barry F. Smith. PETSc home page. http://www.mcs.anl.gov/petsc, 2001.
• 3: [3] Guy Blelloch and Girija Narlikar. A practical comparison of n-body algorithms. In Parallel Algorithms, Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1997.
• 4: H. Cheng , L. Greengard , V. Rokhlin, A fast adaptive multipole algorithm in three dimensions, Journal of Computational Physics, v.155 n.2, p.468-498, Nov. 1, 1999 [doi>10.1006/jcph.1999.6355]
• 5: [5] Matteo Frigo and Steven G. Johnson. FFTW home page. http://www.fftw.org, 2000.
• 6: [6] Yuhong Fu et al. A fast solution for three-dimensional many-particle problems of linear elasticity. International Journal for Numerical Methods in Engineering, 42:1215-1229, 1998.
• 7: [7] Leslie Greengard. The Rapid Evaluation of Potential Fields in Particle Systems. MIT Press, Cambridge, MA, 1988.
• 8: Leslie F. Greengard , Jingfang Huang, A new version of the fast multipole method for screened Coulomb interactions in three dimensions, Journal of Computational Physics, v.180 n.2, p.642-658, August 10, 2002 [doi>10.1006/jcph.2002.7110]
• 9: [9] Leslie Greengard and Vladimir Rokhlin. A new version of the fast multipole method for the Laplace equation in three dimensions. Acta Numerica, pages 229-269, 1997.
• 10: Bhanu Hariharan , Srinivas Aluru , Balasubramaniam Shanker, A scalable parallel fast multipole method for analysis of scattering from perfect electrically conducting surfaces, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-17, November 16, 2002, Baltimore, Maryland
• 11: Yu Hu , S. Lennart Johnsson, A data-parallel implementation of O(N) hierarchical N-body methods, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.2-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369033]
• 12: [12] Rainer Kress. Linear Integral Equations. Applied Mathematical Sciences. Springer, 1999.
• 13: K. Nabors , F. T. Korsmeyer , F. T. Leighton , J. White, Preconditioned, adaptive, multipole-accelerated iterative methods for three-dimensional first-kind integral equations of potential theory, SIAM Journal on Scientific Computing, v.15 n.3, p.713-735, May 1994 [doi>10.1137/0915046]
• 14: [14] Aiichiro Nakano. Parallel multilevel preconditioned conjugate-gradient approach to variable-charge molecular dynamics. Computer Physics Communications, 104:59-69, 1997.
• 15: Aiichiro Nakano , Rajiv K. Kalia , Priya Vashishta , Timothy J. Campbell , Shuji Ogata , Fuyuki Shimojo , Subhash Saini, Scalable atomistic simulation algorithms for materials research, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.1-1, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582035]
• 16: John J. Ottusch , Mark A. Stalzer , John L. Visher , Stephen M. Wandzura, Scalable electromagnetic scattering calculations on the SGI Origin 2000, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.54-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331586]
• 17: [17] Nhan Phan-Thien, Ka Yan Lee, and David Tullock. Large scale simulation of suspensions with PVM. In Proceedings of SC97, The SCxy Conference series, San Jose, CA, November 1997. ACM/IEEE.
• 18: James C. Phillips , Gengbin Zheng , Sameer Kumar , Laxmikant V. Kalé, NAMD: biomolecular simulation on thousands of processors, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-18, November 16, 2002, Baltimore, Maryland
• 19: [19] V. Popov and Henry Power. An O(N) taylor sereis multipole boundary element method for three-dimensional elasticity problems. Engineering Analysis with Boundary Elements, 25:7-18, 2001.
• 20: Faith E. Sevilgen , Srinivas Aluru, A unifying data structure for hierarchical methods, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.24-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331556]
• 21: J. P. Singh , C. Holt , J. L. Hennessy , A. Gupta, A parallel adaptive fast multipole method, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.54-65, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169651]
• 22: Shang-Hua Teng, Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation, SIAM Journal on Scientific Computing, v.19 n.2, p.635-656, March 1998 [doi>10.1137/S1064827595288942]
• 23: M. S. Warren , J. K. Salmon, Astrophysical N-body simulations using hierarchical tree data structures, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.570-576, November 16-20, 1992, Minneapolis, Minnesota, United States
• 24: M. S. Warren , J. K. Salmon, A parallel hashed Oct-Tree N-body algorithm, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.12-21, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169640]
• 25: [25] Lexing Ying, George Biros, and Denis Zorin. A kernel-independent fast multipole algorithm. Technical Report TR2003-839, Courant Institute, New York University, 2003. http://www.cs.nyu.edu/csweb/Research/TechReports/TR2003-839/TR2003- 839.pdf.
• 26: [26] Kenichi Yoshida, Naoshi Nishimura, and Shoichi Kobayashi. Application of fast multipole Galerkin boundary integral equation method to elastostatic crack problems in 3D. International Journal for Numerical Methods in Engineering, 50(3):525.

INDEX TERMS

Keywords:
Fast multipole methods, adaptive algorithms, massively parallel computing, boundary integralequations, N-body problems, viscous flows