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.

  • 1
    $\begingroup$ You can certainly do better than $O(n^6)$, because faster matrix multiplication algorithms (Strassen, Coppersmith-Winograd, Williams, ...) transfer to faster matrix inversion algorithms. $\endgroup$ – Robert Israel Sep 17 '14 at 20:23

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})$).

| cite | improve this answer | |

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.