zbMATH — the first resource for mathematics

Preconditioned conjugate gradients, radial basis functions, and Toeplitz matrices. (English) Zbl 1002.65018
The author presents an efficient preconditioner for the conjugate gradient solution of the interpolation equations generated by gridded data. The method is applied to the corresponding Toeplitz matrices \(A_n=(\varphi(j-k))_{j,k=-n}^n\), where \(n\) is a positive integer and \(\varphi:\mathbb R\rightarrow\mathbb R\) is either a Gaussian (\(\varphi(x)=\exp(-\lambda x^2)\) for some positive contant \(\lambda\)) or a multiquadric (\(\varphi(x)=(x^2+c^2)^{1/2}\) for some real constant \(c\)). Preconditioners are constructed for the dense linear system \(A_nx=f\), \(f\in\mathbb R^{2n+1}\) when \(\varphi\) is a Gaussian, or the dense augmented linear system \(A_nx+ey=f\), \(e^Tx=0\), when \(\varphi\) is a multiquadric. Here \(e=[1, 1,\ldots,1]^T\in\mathbb R^{2n+1}\) and \(y\in \mathbb R\). It is shown that the number of iterations required to achieve a solution of these systems to within a given tolerance is independent of \(n\). The method applies to other functions and in the multidimensional case.

65D05 Numerical interpolation
65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
Full Text: DOI
[1] Franke, C; Schaback, R, Solving partial differential equations by collocation using radial basis functions, Appl. math. comp., 93, 73-82, (1998) · Zbl 0943.65133
[2] Wendland, H, Meshless Galerkin methods using radial basis functions, Math. comp., 68, 1521-1531, (1999) · Zbl 1020.65084
[3] Dyn, N.D; Levin, D; Rippa, S, Numerical procedures for surface Fitting of scattered data by radial functions, SIAM J. sci. stat. comput., 7, 639-659, (1986) · Zbl 0631.65008
[4] A.C. Faul and M.J.D. Powell, Krylov subspace methods for radial basis function interpolation, DAMTP Report 1999/NA11, University of Cambridge. · Zbl 0952.65012
[5] Chan, R; Strang, G, Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. sci. stat. comp., 10, 104-119, (1989) · Zbl 0666.65030
[6] Baxter, B.J.C, The asymptotic cardinal function of the multiquadric ϕ(r) = (r2+c2)\(12\) as c → ∞, Computers math. applic., 24, 12, 1-6, (1992) · Zbl 0764.41016
[7] Baxter, B.J.C, The interpolation theory of radial basis functions, Ph.D. thesis, (1992), University of Cambridge · Zbl 0764.41016
[8] Baxter, B.J.C, Norm estimates for inverses of Toeplitz distance matrices, J. approx. theory, 79, 222-242, (1994) · Zbl 0820.41015
[9] Golub, G.H; Van Loan, C.F, Matrix computations, (1989), The John Hopkins University Press Baltimore, MD
[10] Grenander, U; Szeg″o, G, Toeplitz forms, (1984), Chelsea, New York
[11] Buhmann, M.D; Micchelli, C.A, Multiply monotone functions for cardinal interpolation, Advances in applied mathematics, 12, 358-386, (1991) · Zbl 0756.41002
[12] M.D. Buhmann, (1990).
[13] Rudin, W, Functional analysis, (1973), McGraw Hill New York
[14] C.A. Micchelli, (1986).
[15] Powell, (1990).
[16] Zygmund, (1988).
[17] Powell, M.J.D, The theory of radial basis function approximation in 1990, (), 105-210 · Zbl 0787.65005
[18] Zygmund, A, Trigonometric series, I and II, (1979), Cambridge University Press Cambridge · Zbl 0628.42001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.