Abstract. We introduce the concept of $\epsilon$-displacement rank, that allows us to devise a fast algorithm for the approximate solution of BBBT/BTB (Block Banded Block Toeplitz with Banded Toeplitz Blocks) systems by means of cyclic reduction. We also introduce the concept of incomplete displacement block $LU$ factorization of a Toeplitz-like matrix, where the displacement structure is imposed to the blocks of the factors $L$ and $U$. The role of the matrix $LU$ as preconditioner is discussed. Finally we propose another preconditioner obtained by extending a BBBT/BTB matrix to a banded Toeplitz matrix. Some open problems are addressed.

 <dvi>  <postscript>  files of the paper