1MAIT 627 Fast Multipole MethodsLecture 21Nail Gumerov & Ramani DuraiswamiHelmholtz EquationReferenceN.A. Gumerov & R. DuraiswamiFast Multipole Methods for Solution of the Helmholtz Equation in Three DimensionsElsevier, Oxford (2004).Content• Helmholtz Equation• Expansions in Spherical Coordinates• Matrix Translations• Complexity and Modifications of the FMM• Fast Translation Methods• Error Bounds• Multiple Scattering ProblemHelmholtz Equation• Wave equation in frequency domain– Acoustics– Electromagneics (Maxwell equations)– Diffusion/heat transfer/boundary layers– Telegraph, and related equations– k can be complex• Quantum mechanics– Klein-Gordon equation– Shroedinger equation• Relativistic gravity (Yukawa potentials, k is purely imaginary)• Molecular dynamics (Yukawa)• Appears in many other modelsBoundary Value ProblemsnS2Green’s Function and IdentitynSΩDistributions of Monopoles and DipolesnSΩExpansions in Spherical CoordinatesSpherical Basis FunctionsxyzOxyzOxyzOθφrririθiφxyzOxyzOxyzOθφrririθiφSpherical CoordinatesRegular Basis FunctionsSingular Basis FunctionsSpherical HarmonicsAssociated Legendre FunctionsSpherical Bessel FunctionsSpherical Hankel Functions of the First KindSpherical HarmonicsnmSpherical Bessel Functions3Isosurfaces For Regular Basis FunctionsnmIsosurfaces For Singular Basis FunctionsnmExpansionsWave vectorMatrix TranslationsReexpansions of Basis FunctionsReexpansion MatricesrtRSOrrtRSOrRecursive Computation of Reexpansion Matrices|m|n’p-1|m*|02p-2-|m*|2p-2p-1n’mm’(n’,m’,m+1)(n’-1,m’-1,m)(n’+1,m’-1,m)|m|n’p-1|m*|02p-2-|m*|2p-2p-1n’mm’n’mm’(n’,m’,m+1)(n’-1,m’-1,m)(n’+1,m’-1,m)nn|m’||m||m||m| |m’||s||m’| < |m||m’| > |m|2p-2-|m|p-1p-12p-2-|m|2p-2-|m’|2p-2-|m’|00p-1-|m|+|m’|p-1-|m’|+|m|n’n(n’,n-1)(n’-1,n)(n’,n+1)(n’+1,n)n(n’,n-1)(n’-1,n)(l,n+1)(n’+1,n)n’n’n’p-1p-1nn|m’||m||m||m| |m’||s||m’| < |m||m’| > |m|2p-2-|m|p-1p-12p-2-|m|2p-2-|m’|2p-2-|m’|00p-1-|m|+|m’|p-1-|m’|+|m|n’n(n’,n-1)(n’-1,n)(n’,n+1)(n’+1,n)n(n’,n-1)(n’-1,n)(l,n+1)(n’+1,n)n’n’n’p-1p-1p4elements of the truncated reexpansion matrices can be computed for O(p4) operations recursivelyGumerov & Duraiswami,SIAM J. Sci. Stat. Comput.25(4), 1344-1381, 2003.4TranslationsΩ1Ω2x*1x*2R(R|R)xRΩr(x*)x*(R|R)yx*+ttrΩr1(x*+t)r1xiΩ1Ω2x*1x*2S(S|S)Sxix*x*+t(S|S)ytΩr1(x*+t)Ωr(x*)rr1xiΩ1x*1x*2S(S|S)Sxix*x*+t(S|R)ytΩr1(x*+t)rr1R|RS|S S|RProblem:• For the Helmholtz equation absolute and uniform convergence can be achieved only forp > 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).aExpansionDomainD2a=31/2DModel of Truncation Number Behavior for Fixed Errorpka0ka*p*In the multilevel FMM we associate its own plwith each level l:“Breakdown level”Box size at level lComplexity of Single TranslationTranslation exponentSpatially Uniform Data DistributionsConstant!Complexity of the Optimized FMM for Fixed kD0and Variable N10000010000001E+071E+081E+091E+101E+111E+121000 10000 100000 1000000Number of SourcesNumber of Multiplicationsnu=1, lb=2nu=1.5, lb=2nu=2, lb=2nu=1, lb=5nu=1.5, lb=5nu=2, lb=5Straightforward, y=x2 3D Spatially Uniform Random DistributionN=My=ax5Optimum Level for Low Frequencies0.000010.00010.0010.010.11101002 3 4 5 6 7Max Level of Space SubdivisionNumber of Multiplications, x10e11N=M=10000003D Spatially Uniform Random DistributionDirect SummationTranslationTotalnu=11.5221.51Volume Element MethodsNswavelengthD0 = D0k/(2π) wavelengths = N1/3sourcesCritical Translation Exponent!computational domainWhat Happens if Truncation Number is Constant for All Levels?“Catastrophic Disaster of the FMM”Surface Data DistributionsCritical Translation Exponent!Boundary Element Methods:Optimum Level of Space Subdivision0123456781000 10000 100000 1000000Number of SourcesOptimum Max Levelnu=1nu=1.5nu=2lb=20123456781000 10000 100000 1000000Number of SourcesOptimum Max Levelnu=1nu=1.5nu=2lb=5lb=2lb=5Performance of the MLFMM for Surface Data Distributions10000010000001E+071E+081E+091E+101E+111E+121000 10000 100000 1000000Number of SourcesNumber of Multiplicationsnu=1, lb=2nu=1.5, lb=2nu=2, lb=2nu=1, lb=5nu=1.5, lb=5nu=2, lb=5Straightforward, y=x2 Uniform Random Distributionover a Sphere SurfaceN=My=ax6Effective Dimensionality of the ProblemComputational domain1 cube8 cubesFast Translation MethodsTranslation Methods• O(p5): Matrix Translation with Computation of Matrix Elements Based on Clebsch-Gordan Coefficients;• O(p4) (Low Asymptotic Constant): Matrix Translation with Recursive Computation of Matrix Elements• O(p3) (Low Asymptotic Constants): – Rotation-Coaxial Translation Decomposition with Recursive Computation of Matrix Elements;– Sparse Matrix Decomposition;• O(p2logβp)– Rotation-Coaxial Translation Decomposition with Structured Matrices for Rotation and Fast Legendre Transform for Coaxial Translation;– Translation Matrix Diagonalization with Fast Spherical Transform;– Asymptotic Methods;– Diagonal Forms of Translation Operators with Spherical Filtering.O(p3) MethodsRotation - Coaxial Translation Decomposition (Complexity O(p3))zyyxxyxzyxzzp4p3p3p3zyyxxyxzyxzyxzzp4p3p3p3From the group theory follows that general translation can be reduced to0.010.111010 100Truncation Number, pCPU Time (s)Full Matrix TranslationRotational-Coaxial Translation Decompositiony=ax4y=bx3kt=86Sparse Matrix DecompositionMatrix-vector products with these matrices computed recursively7O(p2logβp) MethodsFast Rotation TransformEuler anglesDiagonal matricesDiagonal matricesBlock-Toeplitz matricesComplexity: O(p2logp)Fast Coaxial TranslationDiagonal matricesLegendre andtransposed Legendre matricesFast multiplication of the Legendre and transposed Legendre matrices can be performed via the forward and inverse FAST LEGENDRE TRANSFORM (FLT) with complexity O(p2log2p)Healy et al Advances in Computational Mathematics 21: 59-105, 2004.Diagonalization of General Translation OperatorDiagonal matricesMatrices for the forward and inverse and Spherical TransformFAST SPHERICAL TRANSFORM (FST) can be performed with complexity O(p2log2p)Healy et al Advances in Computational Mathematics 21: 59-105, 2004.Method of Signature Function(Diagonal Forms of the Translation