0

I have a Sylvester equation $AX+XB=C$ with a unique solution. I don't actually need $X$, but rather the matrix-vector product $Xv$ (for some known $v$). It seems most literature concerns itself with finding $X$, but I was hoping, much like philosophically how $\exp(A)v$ can be evaluated without first finding $\exp(A)$, that there may be efficient (Krylov?), general strategies for this sub-problem. (Suppose I have $A,B,C$ implemented in a matrix-free fashion, and the full storage of $X$ would exceed all memory.)

I emphasize general because it isn't hard to show that if $$\lim_{k\to\infty} \|A^{-k-1}CB^k\| \to 0,$$ then $$X=\sum_{k=0}^\infty (-1)^k A^{-k-1} C B^k,$$ so the product $Xv$ can be evaluated by computing and summing $A^{-k-1}CB^k v$. However, I don't believe my matrices $A,B$ satisfy this requirement. If it is helpful, my $C$ is also rank 1, i.e. $C=ab^T$.

Jason
  • 1,518
  • There are methods which will allow you to obtain an explicit approximation of $X$. Can you be more specific about the matrices $A$ and $B$. In particular, are A and B stable as is frequently the case? – Carl Christian Feb 02 '16 at 15:12
  • Sure, in fact I actually have $\Lambda X + X \Lambda = a b^T$, where $\Lambda$ is weakly (but irreducibly) diagonally dominant and I ultimately need to find $b^T X a$.

    As far as I can tell from the literature, it seems the most effective matrix-free strategies are computing low-rank approximations to $X$ itself (via whatever mechanism, e.g. http://www.sciencedirect.com/science/article/pii/S0898122114001278). I was hoping for (though not necessarily expecting) a cute linear algebra trick to compute the scalar $b^T X a$ without first forming $X$.

     – Jason Feb 02 '16 at 20:51

1 Answers1

1

Computing the map of $v \rightarrow Xv$ where $X$ is given only implicitly as the solution of a Sylvester matrix equation \begin{equation} AX + XB = C \end{equation} is currently beyond what is possible and practical. Your best bet is to exploit the structure of your right hand side term $C = ab^T$ and apply either the standard Arnoldi method (Yousef Sadd, Jaimoukha and Kasenally) or the extended Krylov subspace method (Druskin, Knizhnerman, Simoncini). They were originally developed for the special case of the Lyapunov matrix equations, but they extend trivially to the general case. In many cases this will allow you to obtain a good low rank approximation of $X$ with the hassle of obtaining detailing information about the shape of spectra of $A$ and $B$. I expect that you will get the best results with the extended Krylov subspace method.

To the best of my knowledge the is no trick which will allow you to compute in exact arithmetic the (exact) value $b^TX a$ without computing $X$ using say the Bartels-Stewart method. The ability to computing the map $v \rightarrow Xv$ would constitute a major breakthrough in the field, because it would allow us to run the standard subspace iteration and compute the dominant eigenspace for $X$.

Carl Christian
  • 12,583
  • 1
  • 14
  • 37