  We provide effective algorithms for solving block tridiagonal block Toeplitz
systems with $m\times m$ quasiseparable blocks, as well as quadratic matrix
equations with $m\times m$ quasiseparable coefficients, based on cyclic
reduction and on the technology of rank-structured matrices. The algorithms
rely on the exponential decay of the singular values of the off-diagonal
submatrices generated by cyclic reduction. We provide a formal proof of this
decay in the Markovian framework. The results of the numerical experiments that
we report confirm a significant speed up over the general algorithms, already
starting with the moderately small size $m\approx 10^2$.
