An Algorithm for Solving Circulant Tridiagonal Systems

An algorithm for solving circulant tridiagonal systems is proposed. The algorithm is based on the direct factorization of coefficient matrix. When the system is diagonally dominant, the truncated version of this algorithm provides an approximate solution which equals to the exact solution within machine accuracy and the number of its arithmetic operations is O(8n) -- nearly the same as the number of arithmetic operations for solving a tridiagonal system. The analytic results match closely with the results measured from the numerical experiments.