INVERTING BLOCK TOEPLITZ-MATRICES IN BLOCK HESSENBERG-FORM BY MEANS OF DISPLACEMENT OPERATORS - APPLICATION TO QUEUING-PROBLEMS

The concept of displacement rank is used to devise an algorithm for th e 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 correspondin g 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 w ith a moderate overhead constant. The same technique can be used for s olving 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 anal yzed as well. An application to queueing problems is presented, and co mparisons with existing algorithms are performed showing the higher ef ficiency and reliability of this approach. (C) 1998 Elsevier Science I nc.