Abstract. We propose new algorithms for solving $n\times n$ banded Toeplitz systems with bandwidth $m$. If the function associated with the Toeplitz matrix has no zero in the unit circle, then $O(n\log m + m\log ^2 m\log\log \epsilon^{-1})$ arithmetic operations (ops) are sufficient to approximate the solution of the system up to within the error $\epsilon$, otherwise the cost becomes $O(n\log m +m\log^2 m\log {n\over m})$ ops. Here $m=o(n)$, and $n>\log \epsilon^{-1}$. Some applications are presented. The methods can be applied to infinite and bi-infinite systems and to block matrices.

<dvi>  <postscript>  files of the paper