1Fast Multipole Methods: Fundamentals & ApplicationsRamani DuraiswamiNail A. GumerovGrade distribution• Homework 35 % of your grade• Projects 25%• Final 25%• Mid-term 15 %Problem Size• As problem size grows, in general fidelity of representation grows• On the other hand – cost of solving the problem – Memory required to store the discrete representationalso grow• Way the cost creases with size is the “memory” or “run time” complexity of an algorithm• Need a language to talk about fast and low memory algorithms• Asymptotic complexityAsymptotic Equivalence1)g()f(lim =∞→nnn• Let n the problem size • Two algorithms with costs f(n)and g(n)are said to be equivalent: f(n) ~ g(n)2Little Oh•Asymptotically smaller:•f(n) = o(g(n))0)g()f(lim =∞→nnnBig Oh•Asymptotic Order of Growth:•f(n) = O(g(n))∞<∞→)g()f(suplimnnnThe Oh’sIf f = o(g) or f ~ g then f = O(g)lim = 0lim = 1 lim < ∞The Oh’sIf f = o(g), then g ≠ O(f)lim = 0lim = ∞fggf3Big Oh•Equivalently,•f(n) = O(g(n))∃c,n0 ≥ 0 ∀n ≥ n0|f(n)| ≤ c·g(n)c·ln cBig Ohf(x) = O(g(x))f(x)g(x)↑logscale↓blue stays below redComplexity• we will specify the function g(N) • The most common complexities are – O(1) - not proportional to any variable number, i.e. a fixed/constant amount of time– O(N) - proportional to the size of N (this includes a loop to N and loops to constant multiples of N such as 0.5N, 2N, 2000N - no matter what that is, if you double N you expect (on average) the program to take twice as long)– O(N2) - proportional to N squared (you double N, you expect it to take four times longer - usually two nested loops both dependent on N).– O(log N) - this is tricker to show - usually the result of binary splitting. – O(N log N) this is usually caused by doing log N splits but also doing N amount of work at each "layer" of splitting.Theta•f(n) = Θ(g(n))f(n) = O(g(n)) and g(n) = O(f(n))Same Order of Growth:4Log complexity• If you half data at each stage then number of stages until you have a single item is given (roughly) by log2N. => binary search takes log2N time to find an item. • All logs grow a constant amount apart (homework) – So we normally just say log N not log2N. • Log N grows very slowly Vectors and Matrices• n×d dimensional matrix M and its transpose Mtd dimensional column vector x and its transpose Matrix vector products1= m11x1+ m12x2+ … + m1dxds2= m21x1+ m22x2+ … + m2dxd…sn= mn1x1+ mn2x2+ … + mndxd• d products and sums per line• N lines• Total Nd products and Nd sums to calculate N entries• If d∼N then matrix multiplication cost is O(N2)• Storage of the matrix entries is also O(N2)• Matrix vector product is identical to a sumsi= ∑j=1dmijxj• So algorithm for fast matrix vector products is also a fast summation algorithm• Introduced by Rokhlin & Greengard in 1987• Called one of the 10 most significant advances in computing of the 20thcentury• Speeds up matrix-vector products (sums) of a particular type• Above sum requires O(MN) operations.• For a given precision ε the FMM achieves the evaluation in O(M+N) operations.Fast Multipole Methods (FMM)5• Can accelerate matrix vector products – Convert O(N2) to O(N log N)• However, can also accelerate linear system solution– Use iterative methods that take k steps and use a matrix vector product at each step– Convert O(N3) to O(kN log N)A very simple algorithm• Not FMM, but has some key ideas• Consider S(xi)=∑j=1Nαj(xi– yj)2i=1, … ,M• Naïve way to evaluate the sum will require MN operations• Instead can write the sum as S(xi)=(∑j=1Nαj)xi2+ (∑j=1Nαjyj2) -2xi(∑j=1Nαjyj) – Can evaluate each bracketed sum over j and evaluate an expression of the typeS(xi)=βxi2+ γ-2xiδ– Requires O(M+N) operations• Key idea – use of analytical manipulation of series to achieve faster summation• Matrix is structured … determined by N+M quantities• Introduced by Rokhlin & Greengard in 1987• Called one of the 10 most significant advances in computing of the 20thcentury• Speeds up matrix-vector products (sums) of a particular type• Above sum requires O(MN) operations.• For a given precision ε the FMM achieves the evaluation in O(M+N) operations.Fast Multipole Methods (FMM)Reduction of ComplexityStraightforward (nested loops):Complexity: O(MN)Factorized:Complexity: O(pN+pM)If p << min(M,N) then complexity reduces! Factorize matrix entries6Approximate evaluation• FMM introduces another key idea or “philosophy”– In scientific computing we almost never seek exact answers– At best, “exact” means to “machine precision”• So instead of solving the problem we can solve a “nearby”problem that gives “almost” the same answer• If this “nearby” problem is much easier to solve, and we can bound the error analytically we are done.• In the case of the FMM– Manipulate series to achieve approximate evaluation– Use analytical expression to bound the error• FFT is exact … FMM can be arbitrarily accurateApproximate evaluation• FMM introduces another key idea or “philosophy”– In scientific computing we almost never seek exact answers– At best, “exact” means to “machine precision”• So instead of solving the problem we can solve a “nearby”problem that gives “almost” the same answer• If this “nearby” problem is much easier to solve, and we can bound the error analytically we are done.• In the case of the FMM– Manipulate series to achieve approximate evaluation– Use analytical expression to bound the error• FFT is exact … FMM can be arbitrarily accurateStructured matrices• Fast algorithms have been found for many dense matrices• Typically the matrices have some “structure”• Definition:– A dense matrix of order N ×N is called structured if its entries depend on only O(N) parameters.• Most famous example – the fast Fourier transform• FMM matrices are also structured– Depend on the N+M pointsFourier Analysis• Def.: mathematical techniques for breaking up a signal into its components (sinusoids)• Jean Baptiste Joseph Fourier (1768-1830)• can represent any continuous periodic signal as a sum of sinusoidal waves=++7NotationFourier transform f(t) -> F[k]F[k] = For f, periodic with period pf (t) e- 2 π i k t/pd t1/p∫0 pInverse Fourier