Improving Radial Basis Function Interpolation via Random SVD Preconditioners and Fast Multipole Methods
| dc.contributor.advisor | Duraiswami, Ramani | en_US |
| dc.contributor.author | Cheng, Kerry | en_US |
| dc.contributor.department | Computer Science | en_US |
| dc.contributor.publisher | Digital Repository at the University of Maryland | en_US |
| dc.contributor.publisher | University of Maryland (College Park, Md.) | en_US |
| dc.date.accessioned | 2014-10-11T05:30:17Z | |
| dc.date.available | 2014-10-11T05:30:17Z | |
| dc.date.issued | 2013 | en_US |
| dc.description.abstract | Recent research in fast-multipole algorithms for the Helmholtz equation has yielded approximation algorithms that compute matrix vector products of specific matrices to any specified accuracy in linear time. A first purpose of this thesis is to combine this with recent research in randomized algorithms that has developed fast ways to compute rank-<italic>k</italic> SVDs of an <italic>M</italic> × <italic>N</italic> matrix. This combination yields an approximate SVD in O(<italic>k</italic> max(<italic>M,N</italic>)) time. We demonstrate this and explore its use in developing a novel scattered-data interpolation algorithm in three dimensions. Sinc functions are widely used in one dimension, especially in signal processing. We explore the use of these functions in three dimensions. A first exploration is their ability to accurately interpolate some standard functions. We find that the width parameter plays an important role in this regard, and suggest a prescription for its selection. As with other RBF interpolation algorithms, interpolating <italic>N</italic> points requires the solution of a dense linear system, which has O(<italic>N</italic><super>3</super>) cost. We explore two uses of the fast randomized SVD to reduce this cost. First, we use the approximate randomized SVD to come up with a solution to the linear system. Next, we use a preconditioned Krylov iterative method (GMRES) with a low rank SVD as a preconditioner. Results are presented, and the method is found promising. | en_US |
| dc.identifier | https://doi.org/10.13016/M2DW23 | |
| dc.identifier.uri | http://hdl.handle.net/1903/15660 | |
| dc.language.iso | en | en_US |
| dc.subject.pqcontrolled | Computer science | en_US |
| dc.subject.pquncontrolled | fmm | en_US |
| dc.subject.pquncontrolled | interpolation | en_US |
| dc.subject.pquncontrolled | preconditioning | en_US |
| dc.subject.pquncontrolled | random svd | en_US |
| dc.title | Improving Radial Basis Function Interpolation via Random SVD Preconditioners and Fast Multipole Methods | en_US |
| dc.type | Thesis | en_US |
Files
Original bundle
1 - 1 of 1