A fast method of computing radial basis function (RBF) coefficients for uniformly sampled data with the fast Fourier transform (FFT) is proposed. A periodic RBF network which is characterized by a set of periodic RBF coefficients is first introduced. The periodic RBF coefficients are then computed by using the FFT in O(NlogN) computation time, where N is the number of observed data. The original RBF coefficients are approximately computed from the periodic RBF coefficients by using a sparse matrix transform in O(N) computation time. The approximation accuracy is theoretically investigated. The method for 1-D inputs is extended to 2-D by a successive computation of 1-D RBF coefficients.