High performance BLAS formulation of the multipole-to-local operator in the Fast Multipole Method
Résumé
The multipole-to-local (M2L) operator is the most time-consuming part of the far field computation in the Fast Multipole Method. Its natural expression, though commonly used, does not respect a sharp error bound: we here first prove the correctness of a second but less efficient writing. We then propose the use of BLAS (Basic Linear Algebra Subprograms) to speed up its computation for these two expressions. The more efficient level 3 BLAS are obtained through recopies but this additional cost can be avoided thanks to special data storages. This BLAS version is finally compared, theorically and practically with uniform distributions, to other M2L improvements such as block FFT and rotations. When considering runtime, extra memory storage and numerical stability, the BLAS version appears as the best one.