Let $X\in\mathbb{C}^{m\times n}$ be a matrix that satisfies the Sylvester equation $$AX-XB = F,\qquad A\in\mathbb{C}^{m\times m}, \quad B\in\mathbb{C}^{n\times n},$$ where $F\in\mathbb{C}^{m\times n}$ is of low rank. In special cases as shown in http://math.mit.edu/~plamen/files/mds.pdf there are known algorithms for a fast matrix-vector product, i.e., computing $X\underline{v}$ in quasilinear complexity. These special cases include Toeplitz-like, Hankel-like, Cauchy-like, and Vandermonde-like matrices.
Now, consider the case where $X$ is somewhat close to a Toeplitz-like matrix but instead satisfies $$Z_1D_1X - XZ_{-1}D_2 = F,$$ where $F$ is of low rank, $D_1$ and $D_2$ are general diagonal matrices, and $$Z_\phi = \begin{bmatrix} &&&\phi\\1\\&\ddots\\&&1&0\end{bmatrix}.$$ Is there a fast (quasilinear complexity) algorithm for computing the matrix-vector product, i.e., $X\underline{v}$?
More generally, I am confused what conditions on $A$ and $B$ are needed for the matrix $X$ in $AX-XB = F$ to have a fast matrix-vector product?
Thank you for your consideration in advance.
