文档库 最新最全的文档下载
当前位置:文档库 › Computation of Scattering Clusters of Spheres Using the Fast Multipole Method

Computation of Scattering Clusters of Spheres Using the Fast Multipole Method

Computation of Scattering Clusters of Spheres Using the Fast Multipole Method
Nail A. Gumerov Ramani Duraiswami Institute for Advanced Computer Studies University of Maryland at College Park https://www.wendangku.net/doc/b613909128.html,/~gumerov https://www.wendangku.net/doc/b613909128.html,/~ramani This study has been supported by NSF
Outline
Introduction Problem Formulation Method of Solution
Multipole Reexpansion (T-matrix) Method Iterative Methods Fast Multipole Method
Results of Computations Conclusion

Introduction
Introduction
Multiple Scattering Problems
Sound propagation in disperse media (particles, bubbles, etc.) Modeling of scattering from environment (humans, animals, fish, etc.) Electromagnetic scattering problems (microwaves, optics, etc.) Efficient parametrization in inverse problems (tomography, etc.)

Introduction
Why Multipole Methods?
Scattering computation with BEM for a single object BEM Mesh
5402 nodes 10800 elements Discretization # Dn=30
Can be used to compute the field only for ka < 25 (for human head < 16.5 kHz)
Formal Requirement: ka << Dn Run Time for one frequency on Dual Processor 1 GHz Pentium III ~ 1 day. Required Maximum Frequency to Compare with Experimental HRIR (22 or 44 kHz), 200 frequencies
Introduction
Why Multipole Methods?
Multipole Methods
Meshless for spherical scatterers Fast
BEM
Needs Mesh Relatively Slow

Problem Formulation
Formulation
Equations and Boundary Conditions
Helmholtz Equation Impedance Boundary Conditions Fourier Transform Wave Equation
3
Field Decomposition Sommerfield Radiation Condition
1 2 Incident Wave
4
5
6

Multipole Reexpansion (T-Matrix) Method
T-Matrix Method
Scattered Field Decomposition
Singular Basis Functions
Hankel Functions
Expansion Coefficients
Spherical Harmonics
Vector Form: dot product

T-Matrix Method
Incident Field Decomposition and T-matrix for a Single Sphere
Regular Basis Functions Bessel Functions
Analytical Solution of the Problem:
T-matrix
Isosurfaces For Regular Basis Functions
n
m

Isosurfaces For Singular Basis Functions
n
m
T-Matrix Method
Solution of Multiple Scattering Problem
“Effective” Incident Field
Coupled System of Equations:
3 1 2 Incident Wave 4 5 Scattered Wave 6
(S|R)-Translation Matrix

T-Matrix Method
Reexpansions/Translations
M rq r q r’pq r’q O r’p rp p
T-matrix Method
Two Spheres: Convergence with Respect to Truncation Number
10
0 HRTF (dB)
1
5
10 20
ka1=30
-10 Two spheres, o o θ1 = 60 , φ1 = 0 , rmin/a1 = 2.3253.
-20
-30 0 10 20 30 40 50 Truncation Number

T-matrix Method
Three Spheres Comparisons of BEM & MultisphereHelmholtz
12 9
60
o
BEM MultisphereHelmholtz θ1 = 0o 30
o
6 HRTF (dB) 3 0 -3 -6 -9 -12 -180
120o 90
o o
30o 60o 90o
180
120o
150o 150o Three Spheres, ka1 =3.0255.
-90
0 Angle φ1 (deg)
90
180
BEM: 5184 triangular elements MH: Ntrunc = 9 (100 coefficients for each sphere)
T-matrix Method
Conclusions on T-matrix Method
We used recursive computation of translation matrices (Chew, 1992; Gumerov & Duraiswami, 2001). In some cases speed up of computations 103-104 times compared to BEM. But… Computational Complexity is O(N3P3)= O(N3 p6), where P= p2 is the total length of the vector of expansion coefficients. Method is not suitable for large N and ka. Details can be found in our paper JASA 112(6), 2002, 2688-2701.

Iterative Methods
Iterative Methods
Reflection Method & Krylov Subspace Method (GMRES)
Reflection (Simple Iteration) Method:
General Formulation (used in GMRES)

Iterative Methods
Convergence of Reflection Iteration Method
Exponential Convergence
Iterative Methods
Conclusions on Iterative Methods
Both the Reflection Method (RM) and the GMRES converge well, while the RM is simpler and faster; Some problems in convergence were found for larger ka and regular spacing of the scatterers; In iterative methods fast translation algorithms can be used (we used O(p3)=O(P3/2) fast translation based on sparse matrix decomposition of translation operators). This cost potentially can be reduced further (we are working on O(PlogP) methods). Complexity of Iterative Methods in this case O(N2Niter p3); Savings in complexity compared to straightforward T-matrix are O(p3 N/Niter) For N~200, Niter~20, p~10 (P~100) this yields of order 104 times savings.

Fast Multipole Method
FMM
Some Facts on the Fast Multipole Methods (FMM)
Introduced by Rokhlin & Greengard (1987,1988) for computation of 2D and 3D fields for Laplace Equation; Reduces complexity of matrix-vector product from O(N2) to O(N) or O(NlogN) (depends on data structure); Hundreds of publications for various 1D, 2D, and 3D problems (Laplace, Helmholtz, Maxwell, Yukawa Potentials, etc.); Application to acoustical scattering problems (Koc & Chew, 1998; JASA); We taught the first in the country course on FMM fundamentals & application at the University of Maryland (2002,2003); Some technical reports are available online; A book on the FMM for the 3D Helmholtz equation submitted to Academic Press.

FMM
Far and Near Fields
Neighborhood (Near Field)
Far Field
Max Level of Space Subdivision

FMM
Translations
R|R
+t) ?r1(x*? R 2 y x xx+t * *2 r1 t R (R|R) x*1 * ?r(x*) ? 1 r
S|S
?r1(x*+t) ?r(x*) S S y
S|R
?r1(x*+t) x*+tr1 y (S|R) S tS x* (S|S)*1 x*2 r ?1
?2 r1
t x* r (S|S)*1 x*2 x*+t ?1 xi
xi
Problem:
For the Helmholtz equation absolute and uniform convergence can be achieved only for p > ka. For large ka the FMM with constant p is
very expensive (comparable with straightforward methods); inaccurate (since keeps much larger number of terms than required, which causes numerical instabilities).
D a 2a=31/2D Expansion Domain

Model of Truncation Number Behavior for Fixed Error
p In the multilevel FMM we associate its own pl with each level l:
“Breakdown level”
p*
0
ka*
ka
Box size at level l
Complexity of Single Translation
Translation exponent

Spatially Uniform Data Distributions
Constant!
Complexity of the Optimized FMM for Fixed kD0 and Variable N
1E+12 1E+11
Straightforward, y=x
2
N=M
Number of Multiplications
1E+10 1E+09 1E+08 1E+07
y=ax
1000000
3D Spatially Uniform Random Distribution
nu=1, lb=2 nu=1.5, lb=2 nu=2, lb=2 nu=1, lb=5 nu=1.5, lb=5 nu=2, lb=5 100000 1000000
100000 1000
10000
Number of Sources

Optimum Level for Low Frequencies
100 Number of Multiplications, x10e11 10 1
Total
N=M=1000000
3D Spatially Uniform Random Distribution 2 1.5
0.1 0.01 0.001 0.0001 0.00001 2 3 4 5 6
2 1.5 Translation nu=1
1
Direct Summation
7
Max Level of Space Subdivision
Volume Element Methods
D0 = D0 k/(2π) wavelengths = N1/3 sources Critical Translation Exponent!
Ns
wavelength computational domain

What Happens if Truncation Number is Constant for All Levels?
“Catastrophic Disaster of the FMM”
Source Expansion Errors
r rs 0 b a 0 a rs r b

Approximation of the Error
O(p3) Translation Methods

Rotation - Coaxial Translation Decomposition (Complexity O(p3))
From the group theory follows that general translation can be reduced to
10
z z x p3 y x
0.01 10
kt=86
y=ax4
p4 y x p3 z y
y
CPU Time (s)
p3 z x
1
Full Matrix Translation
y=bx
3
0.1
Rotational-Coaxial Translation Decomposition
100 Truncation Number, p
Sparse Matrix Decomposition
Matrix-vector products with these matrices computed recursively

相关文档
相关文档 最新文档