Highly Accurate Latouche-Ramaswami Logarithmic Reduction Algorithm for Quasi-Birth-and-Death Process

Abstract

This paper is concerned with the quadratic matrix equation $A_0+A_1X+A_2X^2$ $=X$ where $I-A_0-A_1-A_2$ is a regular $M$-matrix, i.e., there exists an entrywise positive vector u such that $(I-A_0-A_1-A_2)$u $\ge 0$ entrywise. It broadly includes those originally arising from the quasi-birth-and-death (QBD) process as a special case where $I-A_0-A_1-A_2$  is an irreducible singular $M$-matrix and $(A_0+A_1+A_2)$1=1 with 1 being the vector of all ones. A highly accurate implementation of Latouche-Ramaswami logarithmic reduction algorithm [Journal of Applied Probability, 30(3):650-674, 1993] is proposed to compute the unique minimal nonnegative solution of the matrix equation with high entrywise relative accuracy as it deserves. Numerical examples are presented to demonstrate the effectiveness of the proposed implementation.