Fast RBF Algorithms
Utilizing fast RBF algorithms to solve linear systems and evaluate summations efficiently. The methods involve Krylov Subspace algorithms, properties, and implementing known coefficients with Multipole techniques.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Main tasks performed Solving the linear system Evaluating the summation
Evaluating the coefficients Possible to obtain 2 sets of linear systems in and . Cost of solving : O(n3) Need for fast algorithm
Algo 1: The Krylov Subspace based algorithm (Beatson-Faul-Goodsell- Powell algorithm) S : space of functions satisfying interpolation conditions S(k): Krylov subspace of S formed on kth iteration Inner product : where s and t belong to S and t is given by
Krylov Subspace properties Norm defined accordingly Property of norm : Norm of error decreases with each iteration -> Algo converges.
Algorithm Initial guess s0employed Method of progress analogous to conjugate gradient method using linear operator A where kis defined to make dk s orthogonal kchosen to minimize the square of the norm of the error.
Preliminaries of implementation, Results Choose Lj, the set of q indices xlwhich minimizes ||xj- xl||2 Choose q, calculate jl. Computational complexity : O(n2) or O(n log(n)) (for multipole summation)
Algo 2: Multipole methods (Beatson and Greengard) Objective : To evaluate the summation s(x) assuming known coefficients
Multiquadric RBF in 1D Considering simple multiquadric RBF in 1D given by Can be written as Laurent series expansion about panel center t.
Far-field expansion Truncation of Laurent series expansion for large values of |x - t|, leading to quick evaluation. Far-field expansion chosen according to panels
Breaking domain into panels Domain can be broken into binary panels s(x) can be evaluated in the panel [0,1/8] (for example as
Discrete Gauss Transform Can also be used instead of Laurent series for Far-field expansions
Bottomline Paneling and far-field expansions used for coarsening the effect of faraway points Computational complexity goes from O(N) to O(mp), where m is the bottom panel number and p is the summation truncation.
Algo 3: Tree-based algorithms (Deng & Driscoll) Advanced variant of multipole methods Aim : Evaluate the summation s(x)
Tree Consider a domain in Rd. Nodes of tree : cell in Rd. Branch of tree : made by dividing the domain in each dimension by 2 Number of children of each cell : 2d
Taylor expansion Taylor expansion of RBF (and hence s(x)) in cell C : Ti : Set of cells C which interact with cell containing xi
Tree algorithm s(xi) is evaluated as where H(xi) is the hierarchy of cells along the tree containing xi. sC can be evaluated using a Taylor expansion as in previous slide Multipole Acceptance Criterion : used to test cell for far-field expansion
Bottomline Computational complexity of crude method : O(MN)*order of RBF evaluation Computational complexity with tree algo : O((M+N)log(M))
References R. K. Beatson and L. Greengard, A short course on fast multipole methods, inWavelets,Multilevel Methods and Elliptic PDEs (M. Ainsworth, J. Levesley, W. A. Light, and M. Marletta, eds.), Oxford University Press, Oxford, UK, 1997, pp. 1 37. Q.Deng and T. A. Driscoll, A fast treecode for multiquadric interpolation with varying shape parameters, SIAM J. Sci. Comput. 34 (2012), A1126 A1140. G. Roussos and B. J. C. Baxter, Rapid evaluation of radial basis functions, J. Comput. Appl. Math. 180 (2005), 51 70 A. C. Faul andM. J.D. Powell, Krylov subspacemethods for radial basis function interpolation, in Proceedings of the International Conference on Numerical Analysis (Dundee), August 1999. A. C. Faul, G. Goodsell, and M. J. D. Powell, A Krylov subspace alogrithm for multiquadric interpolation in many dimensions, IMAJ.Numer.Anal. 25 (2005), 1 24.
