METT VIII - 8th Workshop on Matrix Equations and Tensor Techniques

Nov 6 – 8, 2019
MPI Magdeburg
Europe/Berlin timezone

Quadratic matrix equations arising in two-dimensional random walks

Nov 7, 2019, 2:20 PM
25m
Prigogine (MPI Magdeburg)

Prigogine

MPI Magdeburg

MPI for Dynamics of Complex Technical Systems Sandtorstr. 1 39106 Magdeburg
Talk Talks

Speaker

Beatrice Meini (University of Pisa)

Description

The treatment of two-dimensional random walks in the quarter plane leads to Markov processes which involve semi-infinite matrices having Toeplitz or block Toeplitz structure plus a low-rank correction. In particular, finding the steady state probability distribution requires computing the minimal nonnegative solution of the quadratic matrix equation $A_1X^2+A_0X+A_{-1}=X$, where the coefficients $A_i$, $i=-1,0,1$, are semi-infinite nonnegative matrices, which are Toeplitz except for a low-rank correction.

We introduce the sets $\mathcal{QT}^d$ and $\mathcal{EQT}$ of semi-infinite matrices with bounded infinity norm [2]. The former is made by matrices representable as a sum of a Toeplitz matrix and a compact correction with columns having entries which decay to zero. The latter is formed by matrices in $\mathcal{QT}^d$ plus a further correction of the kind $ev^T$ for $e^T=(1,1,\ldots)$ and $v=(v_i)_{i\in Z^+}$ such that $\sum_{i=1}^\infty |v_i|<\infty$. We prove that $\mathcal{QT}^d$ and $\mathcal{EQT}$ are Banach algebras, i.e., they are Banach spaces with the infinity norm, closed under matrix multiplication. Moreover, we provide mild conditions under which the minimal nonnegative solution belongs either to $\mathcal{QT}^d$ or to $\mathcal{EQT}$.

These new classes allow to treat random walks with reset, which model queueing systems with breakdowns or restarts. These models cannot be handled by relying on the currently available Banach algebras [1]. Moreover, matrices in both classes can be approximated up to any precision by a finite number of parameters. This allows to introduce a matrix arithmetic and to extend the cqt-toolbox of [3], so that numerical algorithms valid for finite matrices can be applied to solve the quadratic matrix equation. The convergence of various fixed point iterations is analyzed [4].

[1] Bini, D.A., Massei, S., Meini, B.: Semi-infinite quasi-Toeplitz matrices with applications to QBD stochastic processes. Math. Comp. 87(314), 2811-2830 (2018)

[2] Bini, D.A., Massei, S., Meini, B., Robol, L.: A computational framework for two-dimensional random walks with restarts. Submitted for publication. arXiv:1909.11372v1. (2019)

[3] Bini, D.A., Massei, S., Robol, L.: Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox. Numer. Algorithms 81(2), 741-769 (2019)

[4] Bini, D.A., Meini, B., Meng, J.: Solving quadratic matrix equations arising in random walks in the quarter plane. Submitted for publication. arXiv:1907.09796 (2019)

Primary authors

Dario Andrea Bini (University of Pisa) Stefano Massei (EPF Lausanne) Beatrice Meini (University of Pisa) Leonardo Robol (University of Pisa) Jie Meng (Pusan National University)

Presentation materials

There are no materials yet.