Spectral analysis and preconditioning techniques for radial basis function collocation matrices

Meshless collocation methods based on radial basis functions lead to structured linear systems, which, for equispaced grid points, have almost a multilevel Toeplitz structure. In particular, if we consider partial differential equations (PDEs) in two dimensions, then we find almost (up to a low-rank correction given by the boundary conditions) two-level Toeplitz matrices, i.e. block Toeplitz with Toeplitz blocks structures, where both the number of blocks and the block-size grow with the number of collocation points. In Bini et al. (Linear Algebra Appl. 2008; 428:508-519), upper bounds for the condition number of the Toeplitz matrices approximating a one-dimensional model problem were proved. Here, we refine the one-dimensional results, by explaining some numerics reported in the previous paper, and we show a preliminary analysis concerning conditioning, extremal spectral behavior, and global spectral results in the two-dimensional case for the structured part. By exploiting the recent tools in the literature, a global distribution theorem in the sense of Weyl is proved also for the complete matrix-sequence, where the low-rank correction due to the boundary conditions is taken into consideration. The provided spectral analysis is then applied to design effective preconditioning techniques in order to overcome the ill-conditioning of the matrices. A wide numerical experimentation, both in the one- and two-dimensional cases, confirms our analysis and the robustness of the proposed preconditioners. Copyright (C) 2011 John Wiley & Sons, Ltd.