Automatic synthesis of high performance translation operators and execution plans for the fast multipole method

The Fast Multipole Method (FMM) is the leading approach for attaining linear complexity in the evaluation of long-range (e.g. Coulomb) many-body interactions. The intricacies of implementing a high performant FMM for different potentials are a major barrier to the widespread use of the FMM. In the application of the Fast Multipole Method to the computation of potentials for elliptic PDEs and systems thereof, I present methods that, given various small amounts of user-supplied problem knowledge automatically exploit this knowledge to optimize evaluating the potentials. The first part of the thesis is devoted to the automatic synthesis of translation operators (e.g. multipole-to-local, point-to-multipole, etc.) for arbitrary kernels. I describe the asymptotic cost of variants of our algorithm available given certain pieces of information, as well as the methods by which they are attained. I present theoretical cost bounds as well as numerical evidence that our algorithms attain them. The second part of the thesis describes my work in extending the first to a system of PDEs. I introduce algorithms to automatically synthesize execution plans for expressions of potential operators involving multiple inputs and outputs, multiple different kernels, as well as source and target derivatives. Given a symbolic description of such an operator, the system outputs a sequence of operations that realizes cost savings through an algebraic procedure based on syzygies. Finally, I describe the work of using the above algorithms to generate fast code for graphical processing units (GPUs) that achieve near peak performance and explaining the performance characteristics of the different operations in the FMM using a performance model.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Fernando, Isuru Dilanka

Contributors dc:contributor

• Klöckner, Andreas
• Olson, Luke
• Fischer, Paul
• Askham, Travis

• Scientific Computing
• Fast Multipole Method
• Gpu

Statement dc:rights

• © 2023 Isuru Fernando

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121351

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121351