A new method for solving symmetric circulant tridiagonal systems of linear equations (Q1173903)

The author presents a method for solving a tridiagonal system with circulant matrix \(B\) whose diagonal entries are all \(\lambda>2\) and whose off-diagonal entries are all \(-1\) (or which can be scaled to such a matrix). This matrix is related to the tridiagonal matrix \(C\) whose upper right entry is \(\mu\), whose other diagonal entries are \(\lambda\) and whose off-diagonal entries are \(-1\). \(\mu\) satisfies the expression \(\mu+1/\mu=\lambda\). The two matrices are related by the expression \(B^{-1}=C^{-1}-\mu^{-1}C^{-1}e_ 1(1+\mu^{-1}e^ T_ 1C^{- 1}e_ 1)^{-1}e^ T_ 1C^{-1}\) where \(e_ 1\) is the column vector with 1 in first position, 0 elsewhere. The expression and its block generalization can be used to generate efficient solution algorithms for circulant and block circulant matrices.