# Implicit solution to Sylvester equation

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!

• If you have a quick way to evaluate Ux where U is the matrix of eigenvectors of A (or B), then you can use the representation of M in terms of eigenvectors of A,B (math.stackexchange.com/questions/3354913/…) Nov 21, 2020 at 1:43

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.
• Interesting! I'll take a look at this review. If I specifically only care about the product $Mx$ for a fixed vector $x$ rather than approximating $M$ well more generally, is there anything I can do? Dec 1, 2017 at 3:25
• @JustinSolomon Not that I know (apart from lucky cases, such as when $x$ is an eigenvector of $B$). Dec 1, 2017 at 7:38