Fast multipole accelerated boundary element methods for room acoustics.

Direct and indirect boundary element methods, accelerated via the fast multipole method, are applied to numerical simulation of room acoustics for rooms of volume ∼150 m3 and frequencies up to 5 kHz on a workstation. As the parameter kD (wavenumber times room diameter) is large, stabilization of the previously developed fast algorithms is required for accuracy. A stabilization scheme is one of the key contributions of this paper. The computations are validated using well-known image source solutions for shoebox shaped rooms. Computations for L-shaped rooms are performed to illustrate the ability to capture diffractions. The ability to model in-room baffles and boundary openings (doors/windows) is also demonstrated. The largest case has kD > 1100 with a discretization of size 6 × 106 elements. The performance of different boundary integral formulations was compared, and their rates of convergence using a preconditioned flexible generalized minimal residual method were found to be substantially different. These promising results suggest a path to efficient simulations of room acoustics via high performance boundary element methods.

Modes of self-organization of diluted bubbly liquids in acoustic fields: One-dimensional theory.

The paper is dedicated to mathematical modeling of self-organization of bubbly liquids in acoustic fields. A continuum model describing the two-way interaction of diluted polydisperse bubbly liquids and acoustic fields in weakly-nonlinear approximation is studied analytically and numerically in the one-dimensional case. It is shown that the regimes of self-organization of monodisperse bubbly liquids can be controlled by only a few dimensionless parameters. Two basic modes, clustering and propagating shock waves of void fraction (acoustically induced transparency), are identified and criteria for their realization in the space of parameters are proposed. A numerical method for solving of one-dimensional self-organization problems is developed. Computational results for mono- and polydisperse systems are discussed.

Semi-analytical computation of acoustic scattering by spheroids and disks.

Analytical solutions to acoustic scattering problems involving spheroids and disks have long been known and have many applications. However, these solutions require special functions that are not easily computable. Therefore, their asymptotic forms are typically used instead since they are more readily available. In this paper, these solutions are explored, and computational software is provided for calculating their nonasymptotic forms, which are accurate over a wide range of frequencies and distances. This software, which runs in MATLAB, computes the solutions to acoustic scattering problems involving spheroids and disks by semi-analytical means, and is freely available from the authors' webpage.

Hierarchical O(N) computation of small-angle scattering profiles and their associated derivatives.

The need for fast approximate algorithms for Debye summation arises in computations performed in crystallography, small/wide-angle X-ray scattering and small-angle neutron scattering. When integrated into structure refinement protocols these algorithms can provide significant speed up over direct all-atom-to-all-atom computation. However, these protocols often employ an iterative gradient-based optimization procedure, which then requires derivatives of the profile with respect to atomic coordinates. This article presents an accurate, O(N) cost algorithm for the computation of scattering profile derivatives. The results reported here show orders of magnitude improvement in computational efficiency, while maintaining the prescribed accuracy. This opens the possibility to efficiently integrate small-angle scattering data into the structure determination and refinement of macromolecular systems.

A hierarchical algorithm for fast Debye summation with applications to small angle scattering.

Debye summation, which involves the summation of sinc functions of distances between all pair of atoms in three-dimensional space, arises in computations performed in crystallography, small/wide angle X-ray scattering (SAXS/WAXS), and small angle neutron scattering (SANS). Direct evaluation of Debye summation has quadratic complexity, which results in computational bottleneck when determining crystal properties, or running structure refinement protocols that involve SAXS or SANS, even for moderately sized molecules. We present a fast approximation algorithm that efficiently computes the summation to any prescribed accuracy ε in linear time. The algorithm is similar to the fast multipole method (FMM), and is based on a hierarchical spatial decomposition of the molecule coupled with local harmonic expansions and translation of these expansions. An even more efficient implementation is possible when the scattering profile is all that is required, as in small angle scattering reconstruction (SAS) of macromolecules. We examine the relationship of the proposed algorithm to existing approximate methods for profile computations, and show that these methods may result in inaccurate profile computations, unless an error-bound derived in this article is used. Our theoretical and computational results show orders of magnitude improvement in computation complexity over existing methods, while maintaining prescribed accuracy.

Computation of the head-related transfer function via the fast multipole accelerated boundary element method and its spherical harmonic representation.

The head-related transfer function (HRTF) is computed using the fast multipole accelerated boundary element method. For efficiency, the HRTF is computed using the reciprocity principle by placing a source at the ear and computing its field. Analysis is presented to modify the boundary value problem accordingly. To compute the HRTF corresponding to different ranges via a single computation, a compact and accurate representation of the HRTF, termed the spherical spectrum, is developed. Computations are reduced to a two stage process, the computation of the spherical spectrum and a subsequent evaluation of the HRTF. This representation allows easy interpolation and range extrapolation of HRTFs. HRTF computations are performed for the range of audible frequencies up to 20 kHz for several models including a sphere, human head models [the Neumann KU-100 ("Fritz") and the Knowles KEMAR ("Kemar") manikins], and head-and-torso model (the Kemar manikin). Comparisons between the different cases are provided. Comparisons with the computational data of other authors and available experimental data are conducted and show satisfactory agreement for the frequencies for which reliable experimental data are available. Results show that, given a good mesh, it is feasible to compute the HRTF over the full audible range on a regular personal computer.

A broadband fast multipole accelerated boundary element method for the three dimensional Helmholtz equation.

The development of a fast multipole method (FMM) accelerated iterative solution of the boundary element method (BEM) for the Helmholtz equations in three dimensions is described. The FMM for the Helmholtz equation is significantly different for problems with low and high kD (where k is the wavenumber and D the domain size), and for large problems the method must be switched between levels of the hierarchy. The BEM requires several approximate computations (numerical quadrature, approximations of the boundary shapes using elements), and these errors must be balanced against approximations introduced by the FMM and the convergence criterion for iterative solution. These different errors must all be chosen in a way that, on the one hand, excess work is not done and, on the other, that the error achieved by the overall computation is acceptable. Details of translation operators for low and high kD, choice of representations, and BEM quadrature schemes, all consistent with these approximations, are described. A novel preconditioner using a low accuracy FMM accelerated solver as a right preconditioner is also described. Results of the developed solvers for large boundary value problems with 0.0001 less, similarkD less, similar500 are presented and shown to perform close to theoretical expectations.

Fast head-related transfer function measurement via reciprocity.

An efficient method for head-related transfer function (HRTF) measurement is presented. By applying the acoustical principle of reciprocity, one can swap the speaker and the microphone positions in the traditional (direct) HRTF measurement setup, that is, insert a microspeaker into the subject's ear and position several microphones around the subject, enabling simultaneous HRTF acquisition at all microphone positions. The setup used for reciprocal HRTF measurement is described, and the obtained HRTFs are compared with the analytical solution for a sound-hard sphere and with KEMAR manikin HRTF obtained by the direct method. The reciprocally measured sphere HRTF agrees well with the analytical solution. The reciprocally measured and the directly measured KEMAR HRTFs are not exactly identical but agree well in spectrum shape and feature positions. To evaluate if the observed differences are significant, an auditory localization model based on work by J. C. Middlebrooks [J. Acoust. Soc. Am. 92, 2607-2624 (1992)] was used to predict where a virtual sound source synthesized with the reciprocally measured HRTF would be localized if the directly measured HRTF were used for the localization. It was found that the predicted localization direction generally lies close to the measurement direction, indicating that the HRTFs obtained via the two methods are in good agreement.

Computation of scattering from clusters of spheres using the fast multipole method.

A T-matrix based method of solution of the multiple scattering problem was presented by the authors [J. Acoust Soc. Am. 112, 2688-2701 (2002)]. This method can be applied to the computation of relatively small problems, since the number of operations required grows with the number of spheres N as O(N3), and with the sixth power of the wave number. The use of iterative techniques accelerated using the fast multipole method (FMM) can accelerate this solution, as presented by Koc and Chew [J. Acoust. Soc. Am. 103, 721-734 (1998)] originally. In this study we present a method that combines preconditioned Krylov subspace iterative techniques, FMM accelerated matrix vector products, a novel FMM-based preconditioner, and fast translation techniques that enable us to achieve an overall algorithm in which the cost of the matrix-vector multiplication grows with N as O (N logN) and with the third power of the wave number. We discuss the convergence of the iterative techniques, selection of the truncation number, errors in the solution, and other issues. The results of the solution of test problems obtained with the method for N approximately 10(2)-10(4) for different wave numbers are presented.

Approximating the head-related transfer function using simple geometric models of the head and torso.

The head-related transfer function (HRTF) for distant sources is a complicated function of azimuth, elevation and frequency. This paper presents simple geometric models of the head and torso that provide insight into its low-frequency behavior, especially at low elevations. The head-and-torso models are obtained by adding both spherical and ellipsoidal models of the torso to a classical spherical-head model. Two different numerical techniques--multipole reexpansion and boundary element methods--are used to compute the HRTF of the models in both the frequency domain and the time domain. These computed HRTFs quantify the characteristics of elevation-dependent torso reflections for sources above the torso-shadow cone, and reveal the qualitatively different effects of torso shadow for sources within the torso-shadow cone. These effects include a torso bright spot that is prominent for the spherical torso, and significant attenuation of frequencies above 1 kHz in a range of elevations. Both torso reflections and torso shadow provide potentially significant elevation cues. Comparisons of the model HRTF with acoustic measurements in the horizontal, median, and frontal planes confirm the basic validity of the computational methods and establish that the geometric models provide good approximations of the HRTF for the KEMAR mannequin with its pinnae removed.

Computation of scattering from N spheres using multipole reexpansion.

A computational technique for the solution of problems of wave scattering from multiple spheres is developed. This technique, based on the T-matrix method, uses the theory for the translation and reexpansion of multipole solutions of the Helmholtz equation for fast and exact recursive computation of the matrix elements. The spheres can have prescribed radii, impedances, and locations. Results are validated by comparison with boundary element calculations, and by convergence analyses. The method is much faster than numerical methods based on discretization of space, or of the sphere surfaces. An even faster method is presented for the case when the spheres are aligned coaxially.