Regularized symmetric positive definite matrix factorizations for linear systems arising from RBF interpolation and differentiation. (English) Zbl 1297.65032
Summary: Scattered data interpolation using Radial Basis Functions involves solving an ill-conditioned symmetric positive definite (SPD) linear system (with appropriate selection of basis function) when the direct method is used to evaluate the problem. The standard algorithm for solving a SPD system is a Cholesky factorization. Severely ill-conditioned theoretically SPD matrices may not be numerically SPD (NSPD) in which case a Cholesky factorization fails. An alternative symmetric matrix factorization, the square root free Cholesky factorization, has the same flop count as a Cholesky factorization and is successful even when a matrix ceases to be NSPD. A regularization method can be used to prevent the failure of the Cholesky factorization and to improve the accuracy of both SPD matrix factorizations when the matrices are severely ill-conditioned. The specification of the regularization parameter is discussed as well as convergence/stopping criteria for the algorithm. The formation of differentiation matrices with the regularized SPD factorizations is demonstrated to improve eigenvalue stability properties of RBF methods for hyperbolic PDEs.
MSC:
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 65N35 | Spectral, collocation and related methods for boundary value problems involving PDEs |
| 65N22 | Numerical solution of discretized equations for boundary value problems involving PDEs |
Keywords:
radial basis functions; numerical PDEs; scattered data interpolation; regularization techniques; eigenvalue stabilityReferences:
| [3] | Buhmann, M. D., Radial basis functions (2003), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 1038.41001 |
| [4] | Cervantes Cabrera, D. A.; Gonzlez-Casanova, P.; Gout, C.; Hctor Jurez, L.; Rafael Resdiz, L., Vector field approximation using radial basis functions, J Comput Appl Math, 163-173 (2013) · Zbl 1255.65217 |
| [5] | Emdadi, A.; Kansa, E. J.; Ali Libre, N.; Rahimian, M.; Shekarchi, M., Stable PDE solution methods for large multiquadric shape parameters, Comput Model Eng Sci, 25, 1, 23-42 (2008) · Zbl 1232.65154 |
| [6] | Fasshauer, G. E., Meshfree approximation methods with Matlab (2007), World Scientific: World Scientific Hackensack, NJ, USA · Zbl 1123.65001 |
| [7] | Fasshauer, G. E., Tutorial on meshfree approximation methods with Matlab, Dolomit Res Notes Approx, 1 (2008) |
| [8] | Fasshauer, G. E.; McCourt, M., Stable evaluation of Gaussian RBF interpolants, SIAM J Sci Comput, 34, 2, 737-762 (2012) · Zbl 1252.65028 |
| [9] | Fornberg, B.; Lehto, E., Stabilization of RBF-generated finite difference methods for convective PDEs, J Comput Phys, 230, 2270-2285 (2011) · Zbl 1210.65154 |
| [10] | Fornberg, B.; Lehto, E.; Powell, C., Stable calculation of Gaussian-based RBF-FD stencils, Comput Math Appl, 65, 627-637 (2013) · Zbl 1319.65011 |
| [11] | Fornberg, B.; Piret, C., A stable algorithm for flat radial basis functions on a sphere, SIAM J Sci Comput, 30, 60-80 (2007) · Zbl 1159.65307 |
| [12] | Fornberg, B.; Wright, G., Stable computation of multiquadric interpolants for all values of the shape parameter, Comput Math Appl, 48, 853-867 (2004) · Zbl 1072.41001 |
| [13] | Fornberg, B.; Zuev, J., The Runge phenomenon and spatially variable shape parameters in RBF interpolation, Comput Math Appl, 54, 379-398 (2007) · Zbl 1128.41001 |
| [14] | Franke, R., Scattered data interpolationTests of some methods, Math Comput, 181-200 (1982) · Zbl 0476.65005 |
| [15] | Golub, G.; Van Loan, C., Matrix computations (1996), Johns Hopkins Press: Johns Hopkins Press Baltimore, MD, USA · Zbl 0865.65009 |
| [16] | Guttman, L., Enlargement methods for computing the matrix inverse, Ann Math Stat, 17, 3, 336-343 (1946) · Zbl 0061.27203 |
| [17] | Hansen, P. C., The truncated SVD as a method for regularization, BIT Numer Math, 27, 4, 534-553 (1987) · Zbl 0633.65041 |
| [18] | Henderson, H. V.; Searle, S. R., On deriving the inverse of a sum of matrices, SIAM Rev, 23, 2, 53-60 (1981) · Zbl 0451.15005 |
| [19] | Higham, N., Accuracy and stability of numerical algorithms (2002), SIAM: SIAM Philadelphia, PA, USA · Zbl 1011.65010 |
| [20] | Huang, C.-S.; Leeb, C.-F.; Cheng, A. H.-D., Error estimate, optimal shape factor, and high precision computation of multiquadric collocation method, Eng Anal Bound Elem, 31, 614-623 (2007) · Zbl 1195.65176 |
| [23] | Kansa, E. J., Multiquadrics—a scattered data approximation scheme with applications to computational fluid dynamics. Isurface approximations and partial derivative estimates, Comput Math Appl, 19, 8/9, 127-145 (1990) · Zbl 0692.76003 |
| [24] | Larsson, E.; Hehto, E., Stable computation of differentiation matrices and scattered node stencils based on Gaussian radial basis functions, SIAM J Sci Comput, 35, A2096-A2119 (2013) · Zbl 1362.65026 |
| [25] | Li, S.; Boyd, J. P., Symmetrizing grids, radial basis functions, and Chebyshev and Zernike polynomials for the d4 symmetry group; interpolation within a squircle, part I, J Comput Phys, 258, 931-947 (2014) · Zbl 1349.65056 |
| [26] | Ali Libre, N.; Emdadi, A.; Kansa, E. J.; Rahimian, M.; Shekarchi, M., A stabilized RBF collocation scheme for Neumann type boundary value problems, Comput Model Eng Sci, 24, 1, 61-80 (2008) · Zbl 1232.65156 |
| [29] | Piegorsch, W.; Casella, G., The early use of matrix diagonal increments in statistical problems, SIAM Rev, 31, 428-434 (1989) · Zbl 0686.65013 |
| [30] | Platte, R., How fast do radial basis function interpolants of analytic functions converge?, IMA J Numer Anal, 31, 4, 1578-1597 (2010) · Zbl 1232.41003 |
| [31] | Platte, R.; Driscoll, T., Polynomials and potential theory for Gaussian radial basis function interpolation, SIAM J Numer Anal, 43, 2, 750-766 (2005) · Zbl 1088.65009 |
| [32] | Platte, R.; Driscoll, T., Eigenvalue stability of radial basis functions discretizations for time-dependent problems, Comput Math Appl, 51, 1251-1268 (2006) · Zbl 1152.41311 |
| [33] | Riley, J. D., Solving systems of linear equations with a positive definite, symmetric, but possibly ill-conditioned matrix, Math Tables Other Aids Comput, 9, 51, 96-101 (1955) · Zbl 0066.10102 |
| [34] | Sarra, S. A., A numerical study of the accuracy and stability of symmetric and asymmetric RBF collocation methods for hyperbolic PDEs, Numer Methods Partial Differ Equ, 24, 2, 670-686 (2008) · Zbl 1135.65386 |
| [35] | Sarra, S. A., Radial basis function approximation methods with extended precision floating point arithmetic, Eng Anal Bound Elem, 35, 1, 68-76 (2011) · Zbl 1259.65173 |
| [37] | Sarra, S. A.; Kansa, E. J., Multiquadric radial basis function approximation methods for the numerical solution of partial differential equations, Adv Comput Mech, 2 (2009) |
| [38] | Sarra, S. A.; Sturgill, D., A random variable shape parameter strategy for radial basis function approximation methods, Eng Anal Bound Elem, 33, 1239-1245 (2009) · Zbl 1244.65192 |
| [39] | Schaback, R., Error estimates and condition numbers for radial basis function interpolation, Adv Comput Math, 3, 251-264 (1995) · Zbl 0861.65007 |
| [40] | Trefethen, L. N.; Bau, D., Numerical linear algebra (1997), SIAM: SIAM Philadelphia, PA, USA · Zbl 0874.65013 |
| [41] | Volokh, K.; Vilnay, O., Pin-pointing solution of ill-conditioned square systems of linear equations, Appl Math Lett, 13, 119-124 (2000) · Zbl 0955.65031 |
| [42] | Wendland, H., Scattered data approximation (2005), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1075.65021 |
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.
