Abstract. After motivating the interest and the role of Toeplitz matrices by means of several examples of applications, we focus our interest on the solution of block banded block Toeplitz systems endowed with a two-level structure. In particular we consider block tridiagonal block Toeplitz systems where the blocks are Toeplitz themselves or have a Kronecker product structure, or are Frobenius-like matrices. We introduce some computational tools like the orthogonal displacement representation and the concept of approximate displacement rank and combine them with other well known tools for the design of effective algorithms for the solution of structured problems. Applications to polynomial factorization, solution of queueing models, and image restoration are shown. Finally the concept of approximate displacement rank is used for the design of effective algorithms for Toeplitz-like matrix inversion based on Newton's iteration.

 <dvi>  <postscript>  files of the paper