Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: Application to queueing problems
type: Item
instance of: scholarly article
title: Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: Application to queueing problems
zbMATH Open document ID: 0894.65008
DOI: 10.1016/S0024-3795(97)00273-5
author: Dario A. Bini
author: B. Meini
published in: Linear Algebra and its Applications
publication date: 1998-08-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 60K30
Mathematics Subject Classification ID: 90B10
zbMATH DE Number: 1116059
zbMATH Keywords: matrix inversion
zbMATH Keywords: block Toeplitz matrices
zbMATH Keywords: displacement operators
zbMATH Keywords: algorithm
zbMATH Keywords: block Hessenberg form
zbMATH Keywords: displacement rank
zbMATH Keywords: modeling of metropolitan networks
zbMATH Keywords: numerical experiments
reviewed by: Neli Dimitrova
MaRDI profile type: Publication
cites work: Q5687202
cites work: On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems
cites work: Improved parallel computations with Toeplitz-like and Hankel-like matrices
cites work: Q4314299
cites work: Q3675490
cites work: Q3359644
cites work: Displacement Structure: Theory and Applications
cites work: Inverses of Toeplitz Operators, Innovations, and Orthogonal Polynomials
cites work: Q5687232
cites work: Q3923308
cites work: Q4733209
cites work: On the solution of block Hessenberg systems
Wikidata QID: Q126400499
Recommended article: Fast inversion of Hankel and Toeplitz matrices
Recommended article: Q3980593
Recommended article: Efficient inversion of Toeplitz-block Toeplitz matrix
Recommended article: Inversion of Toeplitz Matrices which are not Strongly Non-singular
Recommended article: Q4244552
Recommended article: Q3349856
Recommended article: Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices
Recommended article: Fast inversion of triangular Toeplitz matrices
Recommended article: On the Toeplitz embedding of an arbitrary matrix
Recommended article: Inverses and determinants of Toeplitz-Hessenberg matrices
description: scientific article; zbMATH DE number 1116059