A symmetric algorithm for Toeplitz systems

AbstractWe derive an algorithm for real symmetric Toeplitz systems with an arbitrary right-hand side. It differs from the Levinson algorithm in that the solution is built up from its middle component(s) outwards, rather than from top to bottom. We then exploit the symmetry of this method by solving separately for the even and odd parts of the right-hand side of the system. On a sequential machine, the complexity of our algorithm for a system of order n is 72n2+O(n) flops, compared to 4n2+O(n) flops for Levinson's algorithm. The algorithm can be extended to nonsymmetric systems, just like Levinson's algorithm