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.