Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: Application to queueing problems (Q1379101)

A fast and efficient algorithm for inverting \(n \times n\) block Toeplitz matrices \(H_n\) in block Hessenberg form with \(m \times m\) block entries is proposed. The concept of displacement rank and its invariance under inversion are used in devising and analyzing the algorithm. It is shown that the inverse \(H_{n}^{-1}\) can be explicitly presented in terms of its first and last block rows and its first and last block columns. The latter are explicitly related to the corresponding ones of \(H_{n/2}^{-1}\). Using a Gohberg-Semencul-like formula [cf. \textit{I. C. Gohberg} and \textit{A. A. Semencul}, Mat. Issled. 7, No. 2(24), 201-223 (1972; Zbl 0288.15004)] a doubling algorithm is obtained for the computation of \(H_{2^i}^{-1}\), \(i=0,1,\ldots,n\), \(n=2^{q}\). The overall cost of computations is \(O(m^2n\log n + m^3 n)\). The case when \(H_n\) is a scalar Toeplitz matrix is also considered. Then the doubling algorithm is strongly simplified and the computational costs reduce to \(O(m^2 \log n + mn \log(mn))\) arithmetic operations. The algorithm is applied to a problem arising from the modeling of metropolitan networks. The method is implemented in Fortran 90. Numerical experiments show that the proposed algorithm requires less storage than a similar method developed by \textit{G. W. Stewart} [Numer. Linear Algebra Appl. 2, No. 3, 287-296 (1995; Zbl 0837.65014)] and is faster than the latter by a factor of \(6.8\). These properties allow to deal with larger values of \(n\) and provide more accurate results.