A compressed cyclic reduction for QBDs with low rank upper and lower transitions

In this chapter we consider quasi-birth and death processes with low rank downward and upward transitions. We show how such structure can be exploited to reduce the computational cost of the cyclic reduction iteration. The proposed algorithm saves computation by performing ultiplications and inversions of matrices of small size (equal to the rank instead of to the phase space dimension) and inherits the stability property of the customary cyclic reduction. Numerical experiments show the gain of the new algorithm in terms of computational cost.