Back to search

Michigan State University

Efficient parallelization of non-uniform fast multipole algorithms

Abstract

dc:description

Many applications of the $N$-body problem today involve distributions of bodies that are (i) very large and (ii) highly non-uniform. A variety of fast multipole algorithms have been devised to reduce the cost from \mathcal{O}(N2) to $\mathcal{O}(N \log N)$ or $\mathcal{O}(N)$ for oscillatory and non-oscillatory problems, respectively. The issue of non-uniformity, however, presents significant challenges in parallelization, requiring a much more nuanced approach. Compounding this challenge, oscillatory $N$-body problems arising from wave physics (electromagnetics, acoustics, etc.) are burdened with capturing both phase and amplitude information as opposed to just the amplitude; non-uniformity even further complicates things. As a result, the algorithm and underlying data structures become extremely complicated, and parallelization becomes quite difficult.This thesis aims to develop novel parallel fast multipole methods for both oscillatory and non-oscillatory problems that (i) are controllably accurate to arbitrary precision, (ii) are capable of efficiently handling highly non-uniform distributions, and (iii) scale well up to extremely large problem sizes and numbers of CPU cores. The accelerated Cartesian expansion (ACE) method and wideband multilevel fast multipole algorithm (MLFMA) are modified to accurately and efficiently accommodate non-uniform, and in the case of MLFMA extremely large, distributions in parallel. Several parallel algorithms for efficiently building the distributed non-uniform tree data structures are developed. Effective, novel algorithms are introduced to reduce load imbalances arising from non-uniformity and certain idiosyncrasies of the parallel wideband MLFMA which hamper scalability. The algorithms presented here meet each of the stated goals, enabling computations involving several hundred million degrees of freedom on 2048 cores for an electromagnetics problem and several billion particles on 16,384 cores for non-oscillatory problems.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hughey, Stephen Michael
Contributors dc:contributor
  • Balasubramaniam, Shanker
  • Aktulga, Hasan M.
  • Rothwell, Edward J.
  • Chahal, Prem J.
  • Wei, Guowei

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • In Copyright
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
etd:16396
isbn:9780355895520
isbn:0355895528
oclc:1047957206
umi:10811598
local:Hughey_grad.msu_0128D_16002

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Hughey, Stephen Michael. Efficient parallelization of non-uniform fast multipole algorithms. 2018.