1CMSC 858M/AMSC 698RFast Multipole MethodsNail A. Gumerov & Ramani DuraiswamiLecture(s) 3(4)Outline• Factorization – One of key parts of the FMM– Extensions of our trick for fast summation– “Middleman” scheme– Singular and regular fields– Far field and near field • Local Expansions (or R-expansions)– Local expansions of regular and singular potentials– Power series– Taylor series• Far Field Expansions (or S-expansions)– Far field expansions of regular and singular potentials– Asymptotic series2Matrix-Vector MultiplicationWhy Rd ?• d = 1– Scalar functions, interpolation, etc.• d = 2,3– Physical problems in 2 and 3 dimensional space• d = 4– 3D Space + time, 3D grayscale images• d = 5– Color 2D images, Motion of 3D grayscale images• d = 6– Color 3D images• d = 7– Motion of 3D color images• d = arbitrary– d-parametric spaces, statistics, database search procedures3Fields (Potentials)Field (Potential) of a single(ith) unit sourceField (Potential) of the setof sources of intensities {ui} Fields are continuous! (Almost everywhere)Examples of Fields• There can be vector or scalar fields (we focus mostly on scalar fields)• Fields can be regular or singular(singular at y = xi)(singular at y = xi)(regular everywhere)Scalar Fields:Vector Field:(singular at y = xi)4Straightforward Computational Complexity:O(MN)Error: 0 (“machine” precision)The Fast Multipole Methods look for computation of the same problem with complexity o(MN) and error < prescribed error.In the case when the error of the FMM does not exceed the machine precision error (for given number of bits) there is no difference between the “exact” and “approximate” solution. Factorization“Middleman Method”5Global FactorizationExpansion coefficientsBasis functionsExpansion centerTruncation numberFactorization Trick6Reduction of ComplexityStraightforward (nested loops):Complexity: O(MN)Factorized:Complexity: O(pN+pM)If p << min(M,N) then complexity reduces! Middleman SchemeComplexity: O(pN+pM)N MNMStraightforwardMiddlemanN MNMStraightforwardMiddlemanSet of coefficients {cm}7Far Field and Near FieldNear FieldrcxiyFar FieldRcxiyWhat are these rc and Rc?depends on the potential + some conventions for the terminologyLocal (Regular) Expansionr*x*yDo not confuse with the Near Field!We also call this R-expansion,since basis functions Rm should be regularBasis FunctionsExpansionCoefficients8Local Expansion of a Regular Potentialr*x*yxir*x*yxiCan be like this:…or like this:|y - x*| < r*< |xi - x*| r*> |y - x*| > |xi - x*| r*x*yxi…or like this:r*> |xi - x*| > |y - x*|Local Expansion of a Regular Potential (Example)Valid for any r* < , and xi.9Local Expansion of a Regular Potential (The same kernel, Example 2)Local Expansion of a Singular Potentialr*x*yxir*x*yxiCan be like this:…or like this:|y - x*| < r* |xi - x*| r*> |y - x*| > |xi - x*| r*x*yxi…or like this:r*> |xi - x*| > |y - x*|Like this only!Never ever!Because xi is a singular point!10Local Expansion of a Singular Potential (Example)Valid for any |xi.-x*| > |y-x*|Power and Taylor Series• Power and Taylor Series– Power Series in 1D– Taylor Series in 1D• Multidimensional Taylor Series • Factorization of Scalar Products in Rd• Compression of Factorized Series• Factorization of Scalar Products in Rd (compression)– Factorization in 2D. – Factorization in 3D.– Factorization in dD.– Multinomial Coefficients.– Complexity of Fast Summation. • General Forms of Factorization for Fast Summation11Power SeriesProperties of Power Series1) For any power series there exists r*,, such that the seriesconverges absolutely at |y - x*| < r* , and diverges at |y-x*| > r* .The number r* , is called the convergence radius of the series,0  r* .For any number q, such that 0 < q < r*, the power series uniformly converges at |y - x*| < q.122) Convergent power series can be summed, multiplied by a scalar, or multiplied according to the Cauchy rule. For |y-x*|< r*, the sum of the series is a continuous and infinitely differentiable function of y.The power series can be differentiated term by term at |y-x*|< r*and integrated over any closed interval included in |y-x*|< r*.Differentiated or integrated series (if integration is taken from x*to y-x*) have the same convergence radius r*.Properties of Power SeriesCauchy’s rule3) Uniqueness. If there exists such positive r that at any y satisfying |y-x*|< r two power series have the same sum, then the coefficients of these series are the same.Properties of Power Series13For those who love proofsProve the above properties!(Not the course formal requirement, but a good exercise)Taylor Series (Finite)14Taylor Series (Infinite)Local 1D Taylor Expansion15Local 1D Taylor Expansion (Example)Multidimensional Taylor Series16Multidimensional Taylor Series(using some vector algebra)Example17Is That a Factorization?Scalar Product in d-Dimensional Space?complex conjugate18Properties of Scalar ProductFactorization of Scalar Product Powers19Is That a Factorization?1) Truncation:2) Fast summation:Yes! It is!Example (Let’s Try To Get Explicit Forms in 2D)The length of anis 2n!This is not factorial!In d dimensions the length of anis even dnWhat to do in practical problems?20Use Compression!Compression operator:Required Property:Consider R2:Let us define:The length is only (n +1), not 2nExample of Fast Computation21Compression Can be Performed for any Dimensionality (Example for 3D):The length of anis (n+1)+n+…+1= (n+1)(n+2)/2Compression Can be Performed for any Dimensionality (General Case):Multinomialcoefficients22What are multinomial coefficients?1d 32…d boxesn objectsn1n2n3nd n1+ n2 + … + nd = n(n ; n1,n2,…,nd) is thenumber of ways of putting n different objects into ddifferent boxes withnkin the k-th boxThe length of the compressed vector23Example of Fast Computation(in 2D case!)Complexity of Fast