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 lowrank
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.