Abstract. The concept of displacement rank is used to devise an algorithm for the inversion of an $n\times n$ block Toeplitz matrix in block Hessenberg form $H_n$ having $m \times m$ block entries. This kind of matrices arises in many important problems in queueing theory. We explicitly relate the first and the last block rows and block columns of $H_n^{-1}$ with the corresponding ones of $H_{n\over 2}^{-1}$. These block vectors fully define all the entries of $H_n^{-1}$ by means of a Gohberg-Semencul-like formula. In this way we obtain a doubling algorithm for the computation of $H_{2^i}^{-1}$, $i=0,1,\ldots,q$, $n=2^q$, where at each stage of the doubling procedure only few convolutions of block vectors must be computed. The overall cost of this computation is $O(m^2 n\log n+m^3 n)$ arithmetic operations with a moderate overhead constant. The same technique can be used for solving the linear system $H_n\B x=\B b$ within the same computational cost. The case where $H_n$ is in addition a scalar Toeplitz matrix is analyzed as well. An application to queueing problems is presented and comparisons with existing algorithms are performed showing the higher efficiency and reliability of this approach.

 <dvi>  <postscript>  files of the paper