11/30/2011 1 CMSC 858M/AMSC 698R Fast Multipole Methods Nail A. Gumerov & Ramani Duraiswami Lecture 22 Outline • Problems related to the Laplace and Helmholtz equations • Direct factorization of Green’s functions - Biharmonic equation - Stokes equations • Representations via multiple scalar functions • Conversion operators • Examples – Biharmonic equation – Polyharmonic equations – Constrained vector Laplace equation – Maxwell equations – Stokes equations11/30/2011 2 Problems related to the Laplace and Helmholtz equations Biharmonic equation (elasticity, Stokes flows, RBF interpolation) Polyharmonic equation (RBF interpolation, function approximation) Constrained vector Laplace equation (vortical flows, vector potentials) Stokes equations (incompressible fluid dynamics at low Reynolds numbers) Time harmonic Maxwell equations (electromagnetism) Direct factorization of Green’s functions • Many problems can be reduced to summation of singularities, such as Green’s functions (monopoles) and their derivatives (multipoles) • Examples: Boundary element methods, singularity methods, RBF interpolation • Green’s functions for some complex equations can be factored, so the problem may reduce to several summations with Laplacian or other known kernels.11/30/2011 3 Example 1: Biharmonic equation 1 FMM 3 FMMs 1 FMM Complexity = 5 runs of the FMM for the Laplace equation Fu & Rodin (2000) Example 1: Biharmonic equation In fact, complexity < 5 FMMs, since direct summation Can be performed just one time Assume well balanced FMM for the Laplace kernel: Cost of dense matrix-vector product = Cost of sparse matrix vector product = ½ of total FMM cost. Then the total cost is 5 Dense products + 1 Sparse product = 3 FMMs11/30/2011 4 Example 2: Stokes equations Stokeslets Stresslets Example 2: Stokes equations Stokeslet summation (Similarly, stresslet summation, see the paper) 3 FMMs 1 FMM Tornberg, Greengard (2008)11/30/2011 5 Representations via multiple scalar functions Scalar function Vector function Independent solution of Laplace, Helmholtz, or other equation, for which FMM is available Translation Representations in the reference frame centered at 0. Look for representation in the form Conversion operator (linear!) Example 1: Biharmonic equation It is very convenient to consider the RCR-decomposition: Rotation does not affect basic decomposition, translation should be only along the z-axis11/30/2011 6 Example 1: Biharmonic equation Similarly for S-expansions. See Gumerov, Duraiswami (2006). Representation of the conversion operator in the space of R-expansion coefficients Very sparse matrix! Only 2 FMMs are needed! Performance of 3D FMM for biharmonic kernel 1.E-021.E-011.E+001.E+011.E+021.E+031.E+03 1.E+04 1.E+05 1.E+06 1.E+07Number of Sources, NCPU Time (s)Directp=4p=9p=19y=axy=bx2DirectFMMp=4919(3.2 GHz Intel Xeon, 3.5 GB RAM) Fast Multipole Method11/30/2011 7 Example 2: Polyharmonic equation Recursive reduction to the biharmonic case. Example 3: Constrained vector Laplace equation11/30/2011 8 Example 3: Constrained vector Laplace equation Generic vector identities for harmonic functions Since an arbitrary constant can be added to potential Example 3: Constrained vector Laplace equation These operators can be represented via sparse matrices in the space of expansion coefficients Finally Invertable (diagonal) operators 2 FMMs are needed for this equation!11/30/2011 9 Example 4: Time harmonic Maxwell equations 2 FMMs are needed for these equations! Gumerov & Duraiswami (2007) Example 5: Stokes equations • Paper under preparation, but idea is similar (3 FMMs are