Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: application to queueing problems

The concept of displacement rank is used to devise an algorithm for the inversion of an n x n block Toeplitz matrix in block Hessenberg form H-n having m x m block entries. This kind of matrices arises in many important problems in queueing theory. We explicitly relate the first and last block rows and block columns of H-n(-1) with the corresponding ones of H-n/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-2i(-1), i = 0, 1,..., q, n = 2(q), where at each stage of the doubling procedure only a 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)x = b within the same computational cost. The case where H-n is in addition to 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