10/11/2011 1 Improved Fast Gauss Transform Based on work by Changjiang Yang (2003), Vikas Raykar (2005), and Vlad Morariu (2007) Fast Gauss Transform (FGT)  Originally proposed by Greengard and Strain (1991) to efficiently evaluate the weighted sum of Gaussians:  FGT is an important variant of Fast Multipole Method (Greengard & Rokhlin 1987)10/11/2011 2 Fast Gauss Transform (cont’d)  The weighted sum of Gaussians is equivalent to the matrix-vector product:  Direct evaluation of the sum of Gaussians requires O(N2) operations.  Fast Gauss transform reduces the cost to O(N logN) operations. Sources Targets Fast Gauss Transform (cont’d)  Three key components of the FGT:  The factorization or separation of variables  Space subdivision scheme  Error bound analysis10/11/2011 3 Factorization of Gaussian  Factorization is one of the key parts of the FGT.  Factorization breaks the entanglements between the sources and targets.  The contributions of the sources are accumulated at the centers, then distributed to each target. Sources Targets Sources Targets Sources Targets Center Factorization in FGT: Hermite Expansion  The Gaussian kernel is factorized into Hermite functions where Hermite function hn(x) is defined by  Exchange the order of the summations a.k.a. Moment, An10/11/2011 4 The FGT Algorithm  Step 0: Subdivide the space into uniform boxes.  Step 1: Assign sources and targets into boxes.  Step 2: For each pair of source and target boxes, compute the interactions using one of the four possible ways: NB · NF, MC · ML: Direct evaluation NB · NF, MC > ML: Taylor expansion NB > NF, MC · ML: Hermite expansion NB > NF, MC > ML: Hermite expansion --> Taylor expansion  Step 3: Loop through boxes evaluating Taylor series for boxes with more than ML targets. NB: # of sources in Box B MC: # of targets in Box C NF: cutoff of Box B ML: cutoff of Box C Too Many Terms in Higher Dimensions  The higher dimensional Hermite expansion is the Kronecker product of d univariate Hermite expansions.  Total number of terms is O(pd), p is the number of truncation terms.  The number of operations in one factorization is O(pd). h0 h1 h2 h0h0 h0h1 h0h2 h1h0 h1h1 h1h2 h2h0 h2h1 h2h2 d=1 d=2 d=3 d>310/11/2011 5 Too Many Boxes in Higher Dimensions  The FGT subdivides the space into uniform boxes and assigns the source points and target points into boxes.  For each box the FGT maintain a neighbor list.  The number of the boxes increases exponentially with the dimensionality. d=1 d=2 d=3 d>3 FGT in Higher Dimensions  The FGT was originally designed to solve the problems in mathematical physics (heat equation, vortex methods, etc), where the dimension is up to 3.  The higher dimensional Hermite expansion is the product of univariate Hermite expansion along each dimension. Total number of terms is O(pd).  The space subdivision scheme in the original FGT is uniform boxes. The number of boxes grows exponentially with dimension. Most boxes are empty.  The exponential dependence on the dimension makes the FGT extremely inefficient in higher dimensions.10/11/2011 6 Improved fast Gauss transform (IFGT) Improved Fast Gauss Transform  Multivariate Taylor expansion  Multivariate Horner’s Rule  Space subdivision based on k-center algorithm  Error bound analysis10/11/2011 7 New factorization Multivariate Taylor Expansions  The Taylor expansion of the Gaussian function:  The first two terms can be computed independently.  The Taylor expansion of the last term is: where =(1, , d) is multi-index.  The multivariate Taylor expansion about center x* : where coefficients C are given by10/11/2011 8 Reduction from Taylor Expansions  The idea of Taylor expansion of the factored Gaussian kernel is first introduced in the course CMSC878R.  The number of terms in multivariate Hermite expansion is O(pd).  The number of terms in multivariate Taylor expansion is , asymptotically O(d p), a big reduction for large d. Fix p = 10, vary d = 1:20 Fix d = 10, vary p = 1:20 0 2 4 6 8 10 12 14 16 18 20100102104106108101010121014101610181020dNumber of termsHermite ExpansionTaylor Expansion0 2 4 6 8 10 12 14 16 18 20100102104106108101010121014pNumber of termsHermite ExpansionTaylor ExpansionTruncation order p Number of terms Number of terms Dimension d Global nature of the new expansion10/11/2011 9 Improved Fast Gauss Transform  Multivariate Taylor expansion  Multivariate Horner’s Rule  Space subdivision based on k-center algorithm  Error bound analysis Monomial Orders  Let =(1, , n), =(1, , n), then three standard monomial orders: Lexicographic order, or “dictionary” order:   Álex  iff the leftmost nonzero entry in  -  is negative. Graded lexicographic order (Veronese map, a.k.a, polynomial embedding):   Ágrlex  iff 1 · i · n i < 1 · i · n i or (1 · i · n i = 1 · i · n i and  Álex  ). Graded reverse lexicographic order:   Ágrevlex  iff 1 · i · n i < 1 · i · n i or (1 · i · n i = 1 · i · n i and the rightmost nonzero entry in  -  is positive).  Example:  Let f(x,y,z) = xy5z2 + x2y3z3 + x3, then  w.r.t. lex f is: f(x,y,z) = x3 + x2y3z3 + xy5z2;  w.r.t. grlex f is: f(x,y,z) = x2y3z3 + xy5z2 + x3;  w.r.t. grevlex f is: f(x,y,z) = xy5z2 + x2y3z3 + x3.10/11/2011 10 The Horner’s Rule  The Horner’s rule (W.G.Horner 1819) is to recursively evaluate the polynomial p(x) = an xn +  + a1 x + a0 as: p(x) = (((an x + an-1)x+)x + a0. It costs n multiplications and n additions, no extra storage.  We evaluate the multivariate polynomial iteratively using the graded lexicographic order. It costs n multiplications and n additions, and n storage. x=(a,b,c) x0 x1 x2 x3 An Example of Taylor Expansion  Suppose x = (x1, x2, x3) and y = (y1, y2, y3), then 1 x1 x2 x3 x12 x1 x2 x1 x3 x22 x2x3 x32 x13 x12x2 x12x3 x1x22 x1x2x3 x1x32 x23 x22x3 x2x32 x33 × 1 y1 y2 y3 y12 y1 y2 y1 y3 y22 y2y3 y32 y13 y12y2 y12y3 y1y22 y1y2y3 y1y32 y23 y22y3 y2y32 y33 1 2 2 2 2 4 4 2 4 2 4/3 4 4 4 8 4 4/3 43 4 4/3 × ≈ Constant 19 ops Direct: 29ops 19 ops Direct:29ops 19 ops Direct: 29 ops10/11/2011 11 An Example of Taylor Expansion (Cont’d) 1 x1