A recursive algorithm for the inversion of matrices with circulant blocks

We investigate the recursive inversion of matrices with circulant blocks. Matrices of this type appear in several applications of Computational Electromagnetics and in the numerical solution of integral equations with the boundary-element method. The inversion is based on the diagonalization of each circulant block by means of the discrete Fourier transform and the application of a recursive algorithm for the inversion of the matrix with diagonal blocks, determined by the eigenvalues of each block. The efficiency of the recursive inversion is exhibited by determining its computational complexity. An implementation of the algorithm in MATLAB is given and numerical results are presented to demonstrate the efficiency in terms of CPU time of our approach.