Sparse diagonal forms for translation operators for the Helmholtz equation in two dimensions (Q1379977)

For the numerical solution of fast multipole methods (FMM) a crucial step is the diagonalization of translation operators for the Helmholtz equation. These operators have analytically simple, phsically transparent, and numerically stable diagonal forms. It has been observed that the diagonal forms are not unique. It is shown that there exist diagonal forms leading to single-stage FMM algorithms with CPU time requirements of order \(O(n^{4/3})\). By numerical experiments it is indicated that it is within a factor of two of being optimal.