A symmetric algorithm for Toeplitz systems

We derive an algorithm for real symmetric Toeplitz systems with an arbitrar y right-hand side. It differs from the Levinson algorithm in that the solut ion 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 separate ly for the even and odd parts of the right-hand side of the system. On a se quential machine, the complexity of our algorithm for a system of order n i s 7/2n(2) + O(n) flops, compared to 4n(2) + O(n) flops for Levinson's algor ithm. The algorithm can be extended to nonsymmetric systems, just like Levi nson's algorithm. (C) 1999 Elsevier Science Inc. All rights reserved.