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

In this paper we consider QBDs processes with low rank downward andupward transitions. We show how such structure can be exploited toreduce the computational cost of the cyclic reduction iteration.The proposed algorithm saves computation by performingmultiplications and inversions of matrices of small size (equal tothe rank instead of to the phase space dimension) and inherit thestability property of the customary cyclic reduction. Numericalexperiments shows the gain of the new algorithm in terms ofcomputational cost.