1 CMSC 858M/AMSC 698R Fast Multipole Methods Nail A. Gumerov & Ramani Duraiswami Lecture 15 Outline • Error Bounds of MLFMM – A scheme for error evaluation; • Example problem – S-expansion error; – S|S-translation error; – S|R-translation error; – R|R-translation error. • Error and Neighborhoods2 A scheme for error evaluation (1) (How one source contributes to one evaluation points) MLFMM Source Data Hierarchy N M Evaluation Data Hierarchy Level 2 Level 3 Level 4 Level 5 Level 2 Level 3 Level 4 Level 5 S S|S S|S S|R R|R R|R A scheme for error evaluation (2) MLFMM Source Data Hierarchy N M Evaluation Data Hierarchy Level 2 Level 3 Level 4 Level 5 Level 2 Level 3 Level 4 Level 5 S S|S S|S S|R R|R R|R3 A scheme for error evaluation (3) MLFMM Source Data Hierarchy N M Evaluation Data Hierarchy Level 2 Level 3 Level 4 Level 5 Level 2 Level 3 Level 4 Level 5 S S|S S|S S|R R|R R|R A scheme for error evaluation (4) Consider computation of the final coefficients with p-truncated matrices These truncation operators can be skipped! (Pr2=Pr) So:4 A scheme for error evaluation (5) The error comes only from the truncation operator A scheme for error evaluation (5) For uniformly and absolutely convergent series:5 A scheme for error evaluation (6) For uniformly and absolutely convergent series it is possible to find such emax(p) that for given minimum(maximum) translation distance the max abs difference between two subsequent functions is smaller than emax(p). In this case the total error of FMM does not exceed: Example Problem This example is also good to evaluate 2D problem, by treating x and y as complex numbers!6 We have… R-expansion S-expansion x* xi R S Singular Point is located at the Boundary of regions for the R- and S-expansions! S|R-operator7 S|S-operator Note: this is correct, but usually we use t = x*1 - x*2, in which case we need to change the sign of t. S|S-operator (2) Note: this is correct, but usually we use t = x*1 - x*2, in which case we need to change the sign of t.8 R|R-operator Note: this is correct, but usually we use t = x*1 - x*2, in which case we need to change the sign of t. R|R-operator(2) Note: this is correct, but usually we use t = x*1 - x*2, in which case we need to change the sign of t.9 S-Expansion Error x*1 level L xk y R r S-Expansion Error R r d = 1: r/R=1/3, d = 2: r/R=2/3 <1/2. 10 S|S-Translation Error Translation from level a+ to a: p first coefficients at level a can be exactly computed from p first coefficients at level a+. This is exact translation of first p coefficients! Note: this is correct, but usually we use t = x*1 - x*2, in which case we need to change the sign of t. S|S-Translation Error(2) Translation from level a+ to a: For any level a! This factor shows that we are on level a11 S|S-Translation Error(3) x*1 x*2 y xi In this example S|S-translations do not cause any additional error! S|R-Translation Error Note that in result of S|S-translations, first p coefficients are exact! r r r x*1 x*2 level L xk y12 S|R-Translation Error (2) x*1 x*2 y xi r r r x*1 x*2 level L xk y d = 1: r /r = 2, d = 2: r /r = 2(2 - 2)/2 = 2(2 -1) > 0.8 S|R-Translation Error (3) Long one! continued13 S|R-Translation Error (4) It is really long! continued we used this S|R-Translation Error (5) That’s it! d = 1: r /r = 2, d = 2: r /r = 2(2 - 2)/2 = 2(2 -1) > 0.814 R|R-Translation Error y xi x*1 x*2 R|R-Translation Error(2) This is something, but why?15 R|R-Translation Error(3) Indeed, in our case the regular basis functions are polynomials up to order p-1, which are obviously can be expressed via other polynomial basis up to order p-1 near arbitrary expansion center. Zero error is provided due to domains of validity are includes hierarchically to larger validity domains. Total Error16 Total Error(2) Total Error(3) -17 Total Error(4). 2-Neighborhood. 2-neighborhood x*1 x*2 y xi Total Error(5). 2-Neighborhood.18 Optimization of MLFMM within error bounds In the example considered, the FMM error depends on: • Truncation number, p; • Max level of space subdivision, L; • Size of the neighborhood (1,2, or maybe other); • Number of sources, N; • Problem dimensionality, d. For fixed (given) N and d parameters p,L,and Neighborhood Size can be optimized. Optimum max level (experiment) 1.E-021.E-011.E+001.E+011.E+021.E+033 5 7 9 11 13 15Maximum Level, lmaxCPU Time (s)N=6553632768163848192409620481024Optimum lmaxM = N , q = q (e), p = p (e, lmax)e = 10-6ea= 2 .10-74 .10-82 .10-82 .10-82 .10-82 .10-82 .10-819 Effects of Machine Precision (1) 1.E-151.E-121.E-091.E-061.E-031.E-12 1.E-09 1.E-06 1.E-03Prescribed Max Abs Error, eMax Abs ErrorM = N , q = q (e), p = p (e, lmax)N=16642561024409616384Double Precision Complex ArithmeticsTheoretical Error BoundActual Max Abs ErrorMachine Precision ThresholdsEffects of Machine Error (2) Two different computational problems: 1) Compute with a given prescribed accuracy; 2) Compute with a machine precision for a given type of float numbers.20 Effects of Machine Error (3) 1.E-021.E-011.E+001.E+011.E+021.E+031.E+02 1.E+03 1.E+04 1.E+05 1.E+06 1.E+07Number of Source Points, NCPU Time (s)StraightforwardSetting FFIAData StructureFFIAMax Precision Computatione = 10-4e = 10-6M = N , q = q (e), p = p (e, lmax)y = ax2y = bxFFTMLFMM MLFMM Effects of Machine Error (4) 0 5 10 15 20 25 30 1.E+02 1.E+03 1.E+04 1.E+05 1.E+06 1.E+07 Number of Source Points, N Truncation Number e = 10 -4 e = 10 -6 Max Precision M = N , q = q ( e ) , p = p ( e , l max ).21 Effects of Machine Error (5) If the cost of search is O(1), then for computations with fixed machine precision CostMLFMMopt =