Preconditioned conjugate gradients, radial basis functions, and Toeplitz matrices (Q1609097)

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.