Solution to generalized Sylvester equation

Question

I am interested in solving generalized Sylvester equations (for $X$) of the form:

$$ \sum_{j=1}^k A_j X B_j^T = F, $$

where $A_j,B_j,X,F\in\mathbb{C}^{n\times n}$ and $k$, $n$ are integers. I will assume that there is a unique solution matrix $X$.

In the case $k=1$ the matrix equation can be solved in $\mathcal{O}(n^3)$ operations by Gaussian elimination. For $k=2$, it can be solved in $\mathcal{O}(n^3)$ operations by the generalized Bartels-Stewart algorithm (for example).

For $k\geq3$ the fastest algorithm I know is the naive $\mathcal{O}(n^6)$ approach, where the matrix equation is written out as a dense $n^2\times n^2$ linear system.

In the case $k=3$ is there a faster known algorithm? Or, perhaps, there is a paper proving that one cannot do better than $\mathcal{O}(n^6)$ in general. Anything along these lines would be wonderful.

Thank you very much in advance.

Answer 1

Not an expert in this problem, but I try to suggest something nevertheless. A practical algorithm could be an iterative method like GMRES. Each step requires a matrix-vector product which costs $O(kn^3)$; convergence holds in exact arithmetic in $n^2$ steps, and you may get a good approximation with much less than that. You could get a decent preconditioner by dropping all but two terms of the sum.

Even if you are just interested in a theoretical big-O cost, this strategy should beat a Strassen-like fast multiplication method on the Kronecker product form ($O(n^{4+\omega})$ rather than $O(n^{4+2\omega})$).