Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: Application to queueing problems (Q1379101): Difference between revisions
From MaRDI portal
Revision as of 11:04, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: Application to queueing problems |
scientific article |
Statements
Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: Application to queueing problems (English)
0 references
16 August 1998
0 references
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.
0 references
matrix inversion
0 references
block Toeplitz matrices
0 references
displacement operators
0 references
algorithm
0 references
block Hessenberg form
0 references
displacement rank
0 references
modeling of metropolitan networks
0 references
numerical experiments
0 references