On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes

D. A. Bini, Stefano Massei, B. Meini, L. Robol

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)


Matrix equations of the kind A1X2+A0X+A−1=X, where both the matrix coefficients and the unknown are semi-infinite matrices belonging to a Banach algebra, are considered. These equations, where coefficients are quasi-Toeplitz matrices, are encountered in certain quasi-birth–death processes as the tandem Jackson queue or in any other processes that can be modeled as a reflecting random walk in the quarter plane. We provide a numerical framework for approximating the minimal nonnegative solution of these equations that relies on semi-infinite quasi-Toeplitz matrix arithmetic. In particular, we show that the algorithm of cyclic reduction can be effectively applied and can approximate the infinite-dimensional solutions with quadratic convergence at a cost that is comparable to that of the finite case. This way, we may compute a finite approximation of the sought solution and of the invariant probability measure of the associated quasi-birth–death process, within a given accuracy. Numerical experiments, performed on a collection of benchmarks, confirm the theoretical analysis.

Original languageEnglish
Article numbere2128
JournalNumerical Linear Algebra with Applications
Issue number6
Publication statusPublished - Dec 2018
Externally publishedYes

Bibliographical note

Publisher Copyright:
Copyright © 2017 John Wiley & Sons, Ltd.

Copyright 2019 Elsevier B.V., All rights reserved.


  • cyclic reduction
  • quadratic matrix equations
  • quasi-birth-and-death processes
  • Toeplitz matrices


Dive into the research topics of 'On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes'. Together they form a unique fingerprint.

Cite this