  Radial basis functions provide highly useful and flexible interpolants to
multivariate functions. Further, they are beginning to be used in the numerical
solution of partial differential equations. Unfortunately, their construction
requires the solution of a dense linear system. Therefore much attention has
been given to iterative methods. In this paper, we present a highly efficient
preconditioner for the conjugate gradient solution of the interpolation
equations generated by gridded data. Thus our method applies to the
corresponding Toeplitz matrices. The number of iterations required to achieve a
given tolerance is independent of the number of variables.
