Submitted: Inexact Krylov iterations and relaxation strategies with fast-multipole boundary element method
The boundary element method reduces to an N-body problem that can be accelerated by the fast multipole method.
Submitted: 19 June 2015
This paper presents a method to algorithmically accelerate boundary element methods. The fast multipole method (FMM) is already used in this context to obtain O(N) computational complexity while solving a dense linear system. Using relaxed-accuracy matrix-vector multiplications in a Krylov solver, we can achieve speed-ups in the order of 4x for applications in Stokes flow. The relaxation strategy uses variable FMM expansion orders as the iterations progress to convergence.
- "Inexact GMRES iterations and relaxation strategies with fast-multipole boundary element method", Tingyu Wang, Simon K. Layton, Lorena A. Barba. Advances in Computational Mathematics, 38:32 (2022). 10.1007/s10444-022-09932-8 // Preprint arXiv:1506.05957 // Code repository // Manuscript source files
Preprint v1: June 2015 (first submission); v2: Nov. 2016 (second submission); v3: July 2021 (third submission). Accepted: Feb. 2022. Published online: 10 May 2022.
Abstract
Boundary element methods produce dense linear systems that can be accelerated via multipole expansions. Solved with Krylov methods, this implies computing the matrix-vector products within each iteration with some error, at an accuracy controlled by the order of the expansion, p. We take advantage of a unique property of Krylov iterations that allow lower accuracy of the matrix-vector products as convergence proceeds, and propose a relaxation strategy based on progressively decreasing p. Via extensive numerical tests, we show that the relaxed Krylov iterations converge with speed-ups of between 2x and 4x for Laplace problems and between 3.5x and 4.5x for Stokes problems. We include an application to Stokes flow around red blood cells, computing with up to 64 cells and problem size up to 131k boundary elements and nearly 400k unknowns. The study was done with an in-house multi-threaded C++ code, on a quad-core CPU.
Acknowledgement
This work was partially supported by the National Science Foundation under grant ACI-1149784.