A clustering algorithm for multilevel fast multipole methods

The multilevel fast multipole method (MLFMM) speeds up the matrix-vector multiplication in the iterative solution of the matrix equation arising in the boundary-element method. It makes use of a spatial hierarchy of the elements; elements are arranged into groups, and those groups are arranged into higher level groups, and so on. Ideally, the groups should be widely separated clusters. If the clustering is not adequate, the MLFMM may perform no better than direct matrix-vector multiplication. An efficient clustering algorithm is proposed. It is applied to scattering of electromagnetic waves from buildings at cell-phone frequencies.