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. (C) 1998 Elsevier Science Inc. [References: 15]