The fast multipole method (FMM) by Greengard and Rokhlin, 1987, is a celebrated numerical algorithm for the rapid calculation of all-to-all interactions of certain type, with linear-scaling complexity. It has enabled computational solutions to numerous important scientific and engineering problems that were previously prohibited by the quadratic or cubic hardness. While its potential is expected to be much more tapped in new applications via novel connections or extensions, including big data learning and analysis, the FMM in its adaptive version is still in need of a competitive parallel counterpart.  

We describe in this talk a few obstacles, specific to the adaptive FMM but fundamental to a large class of linear-scaling algorithms, to synergistic utilization of two hierarchies of different nature -- the architectural memory hierarchy on one side and the numerically multi-scale hierarchy on the other side. We present SAKURA, a systematic solution using combinatorial encoding, calculation and optimization, supported by existing parallel systems, and supporting and enhancing employment, development and numerical performance of the adaptive FMM. We demonstrate SAKURA with experimental results.

Nikos Pitsianis' interests are in algorithms and architectures for high performance numerical computing. Prior to Aristotle, he was a research professor at Duke University and a principal of BOPS Inc. He holds a PhD in CS from Cornell University.