Conference abstracts

Session B7 - Numerical Linear Algebra

July 14, 17:30 ~ 18:00

On the solution of quadratic matrix equations with infinite-dimensional structured coefficients

Beatrice Meini

University of Pisa, Italy   -

Matrix equations of the kind $A_{-1}+A_0 X+A_1 X^2=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 nonnegative quasi-Toeplitz matrices, are encountered in certain Quasi-Birth-Death (QBD) stochastic processes, as the tandem Jackson queue or the reflecting random walk in the quarter plane. We provide a numerical framework for approximating the minimal nonnegative solution of these equations which relies on semi-infinite quasi-Toeplitz matrix arithmetic. This arithmetic does not perform any finite size truncation, instead it approximates the infinite matrices through the sum of a banded Toeplitz matrix and a compact correction. 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 which is comparable to that of the finite case. This way, we may compute a finite approximation of the sought solution, as well as of the invariant probability measure of the associated QBD process, within a given accuracy. Numerical experiments, performed on a collection of benchmarks, confirm the theoretical analysis.

Joint work with D.A. Bini (University of Pisa), S. Massei (Scuola Normale Superiore, Pisa) and L. Robol (CNR, Pisa).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.