Improving Radial Basis Function Interpolation via Random SVD Preconditioners and Fast Multipole Methods

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-k SVDs of an M × N matrix. This combination yields an approximate SVD in O(k max(M,N)) 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 N points requires the solution of a dense linear system, which has O(N3) 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.