The group inverse of circulant matrices with few parameters

The need of solving linear systems with circulant matrices occursin many problems related to the periodicity of that problem. This class ofsystem appears in many applications that range from numerical solution ofpartial differential equations with periodic boundary conditions, until codingtheory, statistics, time series analysis, image processing, or when we approx-imate periodic functions with splines. In spite the problem of computing thegroup inverse of a circulant matrix of order n can be considered solved froma theoretical or algebraic point of view, even for low dimensions the com-putational cost to find the solution could be very high, typically with orderO(n2).Different approches to compute the inverse of a circulant matrix have focusedon special classes of circulant matrices. For structured matrices with threeparameters the application of the FFT, leads to algorithms to solve circulantsystems with orderO(nlog2n) and moreover the proper election of circulantpreconditioners can reduce the computation to orderO(n).In this communication we present our last advances on the computation of thegroup inverse of a family of circulant matrices with four complex parameters.Specifically, we obtain analytical expressions for the coefficients of their groupinverse. This means that by just checking some relations between the fourcoefficients we can explicitly compute the coefficients of the group inverse andthere is no need to apply any numerical method to compute them. Therefore,we improve the computational cost of computing the group inverse of thisclass of matrices that, in the worst case, is now reduced to the evaluationof a polynomial. Moreover our methodology applies to both the invertibleand the singular case, the latter being computationally less expensive. Thetechniques we use are related with the solution of boundary value problemsassociated with first or second order linear difference equations and henceinvolve the evaluation of Chebyshev polynomials.Postprint (published version