×

Block preconditioners for linear systems arising from multiscale collocation with compactly supported RBFs. (English) Zbl 1363.65042

Summary: Symmetric collocation methods with rational basis functions (RBFs) allow approximation of the solution of a partial differential equation, even if the right-hand side is only known at scattered data points, without needing to generate a grid. However, the benefit of a guaranteed symmetric positive definite block system comes at a high computational cost. This cost can be alleviated somewhat by considering compactly supported RBFs and a multiscale technique. But the condition number and sparsity will still deteriorate with the number of data points. Therefore, we study certain block diagonal and triangular preconditioners. We investigate ideal preconditioners and determine the spectra of the preconditioned matrices before proposing more practical preconditioners based on a restricted additive Schwarz method with coarse grid correction. Numerical results verify the effectiveness of the preconditioners.

MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
65N35 Spectral, collocation and related methods for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations

Software:

PetRBF; Matlab
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Iske, Lecture Notes in Computational Science and Engineering, in: Multiresolution Methods in Scattered Data Modelling (2004) · Zbl 1057.65004 · doi:10.1007/978-3-642-18754-4
[2] Wendland, Cambridge Monographs on Applied and Computational Mathematics, in: Scattered Data Approximation (2005)
[3] Buhmann, Cambridge Monographs on Applied and Computational Mathematics, in: Radial Basis Functions: Theory and Implementations (2003) · Zbl 1038.41001 · doi:10.1017/CBO9780511543241
[4] Fasshauer, Interdisciplinary Mathematical Sciences, in: Meshfree Approximation Methods with MATLAB (2007) · Zbl 1123.65001 · doi:10.1142/6437
[5] Madych, Multivariate interpolation and conditionally positive definite functions. II, Mathematics of Computation 54 pp 211– (1990) · Zbl 0859.41004 · doi:10.1090/S0025-5718-1990-0993931-7
[6] Franke, Convergence order estimates of meshless collocation methods using radial basis functions, Advances in Computational Mathematics 8 pp 381– (1998) · Zbl 0909.65088 · doi:10.1023/A:1018916902176
[7] Giesl, Meshless collocation: error estimates with application to dynamical systems, SIAM Journal on Numerical Analysis 45 (4) pp 1723– (2007) · Zbl 1148.65090 · doi:10.1137/060658813
[8] Flyer, Transport schemes on a sphere using radial basis functions, Journal of Computational Physics 226 pp 1059– (2007) · Zbl 1124.65097 · doi:10.1016/j.jcp.2007.05.009
[9] Fornberg, Stabilization of RBF-generated finite difference methods for convective PDEs, Journal of Computational Physics 230 (6) pp 2270– (2011) · Zbl 1210.65154 · doi:10.1016/j.jcp.2010.12.014
[10] Wendland, Divergence-free kernel methods for approximating the Stokes problem, SIAM Journal on Numerical Analysis 47 (4) pp 3158– (2009) · Zbl 1410.76336 · doi:10.1137/080730299
[11] Schräder, A high-order, analytically divergence-free discretization method for Darcy’s problem, Mathematics of Computation 80 (273) pp 263– (2011) · Zbl 1308.76213 · doi:10.1090/S0025-5718-2010-02388-9
[12] Fuselier, Sobolev-type approximation rates for divergence-free and curl-free RBF interpolants, Mathematics of Computation 77 (263) pp 1407– (2008) · Zbl 1196.41003 · doi:10.1090/S0025-5718-07-02096-0
[13] Kansa, Multiquadrics-a scattered data approximation scheme with applications to computational fluid-dynamics-I surface approximations and partial derivative estimates, Computers & Mathematics with Applications 19 (8-9) pp 127– (1990) · Zbl 0692.76003 · doi:10.1016/0898-1221(90)90270-T
[14] Fasshauer, Solving differential equations with radial basis functions: multilevel methods and smoothing, Advances in Computational Mathematics 11 pp 139– (1999) · Zbl 0940.65122 · doi:10.1023/A:1018919824891
[15] Floater, Multistep scattered data interpolation using compactly supported radial basis functions, Journal of Computational and Applied Mathematics 73 pp 65– (1996) · Zbl 0859.65006 · doi:10.1016/0377-0427(96)00035-0
[16] LeGia, Multiscale RBF collocation for solving PDEs on spheres, Numerische Mathematik 121 (1) pp 99– (2012) · Zbl 1246.65222 · doi:10.1007/s00211-011-0428-6
[17] Wendland, Multiscale analysis in Sobolev spaces on bounded domains, Numerische Mathematik 116 (3) pp 493– (2010) · Zbl 1208.65067 · doi:10.1007/s00211-010-0313-8
[18] Farrell, RBF multiscale collocation for second order elliptic boundary value problems, SIAM Journal on Numerical Analysis 51 (4) pp 2403– (2013) · Zbl 1280.65132 · doi:10.1137/120898383
[19] Beatson, Fast solution of the radial basis function interpolation equations: domain decomposition methods, SIAM Journal on Scientific Computing 22 pp 1717– (2000) · Zbl 0982.65015 · doi:10.1137/S1064827599361771
[20] Yokota, PetRBF - a parallel O(N) algorithm for radial basis function interpolation with Gaussians, Computer Methods in Applied Mechanics and Engineering 199 pp 1793– (2010) · Zbl 1231.65026 · doi:10.1016/j.cma.2010.02.008
[21] Deng, A fast treecode with multiquadric interpolation with varying shape parameters, SIAM Journal on Scientific Computing 34 pp A1126– (2012) · Zbl 1253.65012 · doi:10.1137/110836225
[22] Le Gia, Overlapping additive Schwarz preconditioners for elliptic PDEs on the unit sphere, Mathematics of Computation 78 pp 79– (2009) · Zbl 1198.65241 · doi:10.1090/S0025-5718-08-02150-9
[23] Beatson, Fast fitting of radial basis functions: methods based on preconditioned GMRES iteration, Advances in Computational Mathematics 11 pp 253– (1999) · Zbl 0940.65011 · doi:10.1023/A:1018932227617
[24] Ling, A least-squares preconditioner for radial basis functions collocation methods, Advances in Computational Mathematics 23 pp 31– (2005) · Zbl 1067.65136 · doi:10.1007/s10444-004-1809-5
[25] Ling, Preconditioning for radial basis functions with domain decomposition methods, Mathematical and Computer Modelling 40 pp 1413– (2004) · Zbl 1077.41008 · doi:10.1016/j.mcm.2005.01.002
[26] Le Gia, Fast iterative solvers for boundary value problems on a local spherical region, ANZIAM Journal 54 pp C492– (2013) · Zbl 1390.65153 · doi:10.21914/anziamj.v54i0.6303
[27] Chernih, Closed form representations and properties of the generalised Wendland functions, Journal of Approximation Theory 177 pp 17– (2014) · doi:10.1016/j.jat.2013.09.005
[28] Wendland, Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree, Advances in Computational Mathematics 4 (4) pp 389– (1995) · Zbl 0838.41014 · doi:10.1007/BF02123482
[29] Hestenes, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards 49 pp 409– (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044
[30] Saad, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing 7 pp 856– (1986) · Zbl 0599.65018 · doi:10.1137/0907058
[31] Freund, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numerische Mathematik 60 pp 315– (1991) · Zbl 0754.65034 · doi:10.1007/BF01385726
[32] vander Vorst, Bi-CGSTAB: a fast and smoothly converging variant of BiCG for the solution of nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing 13 pp 631– (1992) · Zbl 0761.65023 · doi:10.1137/0913035
[33] Greenbaum, Iterative Methods for Solving Linear Systems (1997) · Zbl 0883.65022 · doi:10.1137/1.9781611970937
[34] Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numerische Mathematik 2 (1) pp 84– (1960) · Zbl 0090.34505 · doi:10.1007/BF01386213
[35] Ipsen, A note on preconditioning nonsymmetric matrices, SIAM Journal on Scientific Computing 23 pp 1050– (2001) · Zbl 0998.65049 · doi:10.1137/S1064827500377435
[36] Kuznetsov, Efficient iterative solvers for elliptic finite element problems on nonmatching grids, Russian Journal of Numerical Analysis and Mathematical Modelling 10 pp 187– (1995) · Zbl 0839.65031 · doi:10.1515/rnam.1995.10.3.187
[37] Murphy, A note on preconditioning for indefinite linear systems, SIAM Journal on Scientific Computing 21 pp 1969– (2000) · Zbl 0959.65063 · doi:10.1137/S1064827599355153
[38] Horn, Matrix Analysis (1990)
[39] Cai, A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM Journal on Scientific Computing 21 pp 792– (1999) · Zbl 0944.65031 · doi:10.1137/S106482759732678X
[40] Frommer, An algebraic convergence theory for restricted additive Schwarz methods using weighted max norms, SIAM Journal on Numerical Analysis 39 pp 463– (2001) · Zbl 1006.65031 · doi:10.1137/S0036142900370824
[41] Feder T Greene D Optimal algorithms for approximate clustering STOC ’88, ACM New York, USA 1988 434 444
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.