Implicit solution to Sylvester equation

Question

Suppose a matrix $M\in\mathbb{R}^{n\times n}$ is defined as the solution to a Sylvester equation $$AM+MB=C,$$ for some fixed (known) matrices $A,B,C$. In the regime where $n$ is large, we may with not to compute $M$ explicitly. For instance, suppose $A,B,C$ are sparse; it may be the case that $M$ is a dense matrix.

Take a vector $x\in\mathbb{R}^n$. Is there a way to compute the product $Mx$ faster than solving for $M$ explicitly and then multiplying?

My basic inspiration here comes from algorithms like conjugate gradients, which can compute the vector $A^{-1}x$ for positive definite $A$ without finding the matrix $A^{-1}$ explicitly. Generalizations to $M$ defined for Riccati/Lyapunov systems of equations are appreciated as well!

Answer 1

Yes, there is active research on that, especially in the Lyapunov case: it turns out under some conditions $M$ is well approximated by a low-rank or banded matrix. So you can find an implicit representation of the solution $M$ and then use it to compute matrix-vector products, in your case.

A good starting point is Valeria Simoncini's research; for instance, check "Computational methods for linear matrix equations" on SIAM review.