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!


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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Justin Solomon Dec 1 '17 at 3:25
  • $\begingroup$ @JustinSolomon Not that I know (apart from lucky cases, such as when $x$ is an eigenvector of $B$). $\endgroup$ – Federico Poloni Dec 1 '17 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.