FMM as a Compute-bound Preconditioner

​Recent efforts to view the FMM as an elliptic PDE solver have opened the possibility to use it as a preconditioner for even a broader range of applications. The FMM is O(N) but compute bound, hierarchical but asynchorous between levels, and can therefore extract the full potential of future architectures. The FMM can be combined with boundary integral methods to handle boundary conditions.​​

Motivation

  • Algorithms with a large amount of global communication and synchronization will be greatly disadvantaged on future architectures

  • FMM is O(N), compute bound, asynchronous, and highly parallel

​​​Rate of Convergence

 

Related Publications