Spectral analysis and preconditioning techniques for radial basis function collocation matrices

被引:9
作者
Cavoretto, R. [2 ]
De Rossi, A. [2 ]
Donatelli, M. [1 ]
Serra-Capizzano, S. [1 ]
机构
[1] Univ Insubria, Dipartimento Fis & Matemat, I-22100 Como, Italy
[2] Univ Turin, Dipartimento Matemat, I-10123 Turin, Italy
关键词
radial basis functions; collocation methods; Toeplitz matrices; preconditioning; ALGEBRA PRECONDITIONERS; TOEPLITZ; CONVERGENCE; APPROXIMATIONS;
D O I
10.1002/nla.774
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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.
引用
收藏
页码:31 / 52
页数:22
相关论文
共 50 条
[1]  
[Anonymous], 1983, Matrix Computations.
[2]  
[Anonymous], 2005, Cambridge Monograph, Applied Comput. Math.
[3]   Preconditioned conjugate gradients, radial basis functions, and Toeplitz matrices [J].
Baxter, BJC .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2002, 43 (3-5) :305-318
[4]   NORM ESTIMATES FOR INVERSES OF TOEPLITZ DISTANCE MATRICES [J].
BAXTER, BJC .
JOURNAL OF APPROXIMATION THEORY, 1994, 79 (02) :222-242
[5]   Fast evaluation of radial basis functions: Methods for two-dimensional polyharmonic splines [J].
Beatson, RK ;
Light, WA .
IMA JOURNAL OF NUMERICAL ANALYSIS, 1997, 17 (03) :343-372
[6]   Superlinear convergence of conjugate gradients [J].
Beckermann, B ;
Kuijlaars, ABJ .
SIAM JOURNAL ON NUMERICAL ANALYSIS, 2001, 39 (01) :300-329
[7]  
Belytschko T., 1996, MECH ENG, V139, P3
[8]  
Bhatia R., 2013, MATRIX ANAL
[9]  
Bhatia R., 2005, FOURIER SERIES
[10]  
BINI D, 1983, LINEAR ALGEBRA APPL, V52-3, P99