A new parallel kernel-independent fast multipole method

Lexing Ying, George Biros, Denis Zorin, Harper Langston

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2003 ACM/IEEE Conference on Supercomputing, SC 2003
StatePublished - 2003
Event2003 ACM/IEEE Conference on Supercomputing, SC 2003 - Phoenix, AZ, United States
Duration: Nov 15 2003Nov 21 2003

Publication series

NameProceedings of the 2003 ACM/IEEE Conference on Supercomputing, SC 2003


Other2003 ACM/IEEE Conference on Supercomputing, SC 2003
Country/TerritoryUnited States
CityPhoenix, AZ


  • Fast multipole methods
  • N-body problems
  • adaptive algorithms
  • boundary integral equations
  • massively parallel computing
  • viscous flows

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'A new parallel kernel-independent fast multipole method'. Together they form a unique fingerprint.

Cite this