The picture compares (left) the traditional Boundary Element Method (BEM) with the MLFMM (see larger picture).
The BEM is an important tool used in Acoustics. But the computational effort for traditional BEM, which is O(n2) (n is the number of unknowns), makes the solution of real life problems for high frequencies almost impossible. The combination with the Fast Multipole Method (FMM) reduces this effort to O(n·log2(n)), thus making it possible to also solve problems in the high frequency region.
The Multilevel Fast Multipole Method in combination with the Boundary Element Method is a tool for the simuation of large objects in reasonable time without significant loss of accuracy.
The Fast Multipole Method subdivides the boundary element mesh into different clusters. If two clusters are sufficiently far away from each other (i.e. they are in each others far field), the interaction between these two clusters can be reduced to the interaction of the cluster midpoints with almost no loss of accuracy. For clusters not in the far field, the traditional BEM has to be applied.
The Multilevel Fast Multipole Method introduces different levels of clustering (clusters made out of smaller clusters), exchanges information between the different levels and uses the Multipole expansion only for certain clusters (interaction field) on the same level. This causes an additional speed up in calculation time.
The MLFMM is currently used for the simulation of head related transfer functions (HRTF).
The method developed for the computation of the sound distribution at dummy heads with BEM was applied to “natural” heads. 3D-head-scans of test subjects were made in co-operation with the Vienna University of Technology’s Institute of Discrete Mathematics and Geometry. Each grid contains approximately 65000 to 70000 triangle elements with 30000 to 35000 knots. Such a high resolution of the grid is necessary for calculating the acoustic sound pressure level at high frequencies up to 16000 Hz. The new method enables the determination of computational robust parts of head related transfer functions (HRTF). HRTFs describe the auditory localisation of sound sources in the sagittal planes. The results are used to explore the 3D-localisation of sounds for deaf subjects, equipped with bilateral Cochlear Implants.