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-<italic>k</italic> SVDs of an <italic>M</italic> &times; <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.