ABSTRACT
Conventional multipole operations, M2M, M2L, and L2L exhibit O(N 4) scaling with respect to size, N of multipole expansion. The scaling profile improves to O(N 3) upon performing origin translation of multipole expansion along the z-axis. Generally, only a fraction of boxes in FMM happen to be aligned along the z-axis. Flexibility in the choice of coordinate system provides the mechanism to achieve the required parallel alignment. Implementation of this idea turns the general multipole translation into a three-step operation known as rotation-based multipole translation. In the first step, the local coordinate system of the multipole expansion to be translated is rotated to align its z-axis with the line connecting the centers of the donor and recipient boxes. The second step performs a multipole translation along the z-axis. Finally, in the third step, the local coordinate system of the translated expansion is rotated to match that of the recipient box. Rotation of the coordinate system of multipole expansion involves computation of the Wigner matrix. Significant reduction in the cost of rotation occurs when choosing the bar-scaled m-set and the tilde scaled k-set of recurrence relations for computation of Wigner d-matrix. The chapter concludes by providing computer implementation of rotation-based multipole operations.
