A least-squares preconditioner for radial basis functions collocation methods

Abstract

Although meshless radial basis function (RBF) methods applied to partial differential equations (PDEs) are not only simple to implement and enjoy exponential convergence rates as compared to standard mesh-based schemes, the system of equations required to find the expansion coefficients are typically badly conditioned and expensive using the global Gaussian elimination (G-GE) method requiring $\mathcal{O}(N^{3})$ flops. We present a simple preconditioning scheme that is based upon constructing least-squares approximate cardinal basis functions (ACBFs) from linear combinations of the RBF-PDE matrix elements. The ACBFs transforms a badly conditioned linear system into one that is very well conditioned, allowing us to solve for the expansion coefficients iteratively so we can reconstruct the unknown solution everywhere on the domain. Our preconditioner requires $\mathcal{O}(mN^{2})$ flops to set up, and $\mathcal{O}(mN)$ storage locations where m is a user define parameter of order of 10. For the 2D MQ-RBF with the shape parameter $c\sim1/\sqrt{N}$ , the number of iterations required for convergence is of order of 10 for large values of N, making this a very attractive approach computationally. As the shape parameter increases, our preconditioner will eventually be affected by the ill conditioning and round-off errors, and thus becomes less effective. We tested our preconditioners on increasingly larger c and N. A more stable construction scheme is available with a higher set up cost.