Linear system with sum of Kronecker products

Question

Here and here, specific ways to address the equation in $x$, for $N=2$, are given:

$$\sum_{i=1}^N (A_i\otimes B_i)x=c$$

Is anything know about the case $N>2$?

I am looking in fact for an efficient solution to the above type of linear system. Such structure may arise from space-time algorithms applied to parabolic, non-linear problems.

---

In fact, the system I am interested in has the following structure:

$\sum_{j,l,a,b}M_{j,a}^iT_{l,b}^k\nu^1_{a,b}x^1_{j,l}+\sum_{j,l,a,b,o}S_{j,a}^iD_{l,b,o,j}^k\nu^2_{a,b} x^2_{j,l}=f^{i,k}$

As you can see, the $\nu$ factors prevent me from writing the system as in the link I posted. Also, the matrix $D$ contains the index $j$, which gives further problems. My idea was to decompose $\nu$ as a sum of Kronecker products (approximately, and carry out a similar procedure for $D$, I won't go into details), hoping to obtain a better structure.

By doing so, we see that we obtain the original system I decsribed above. So, to answer to @Nathaniel, $N$ should be large so that the approximation of e.g. $\nu$ in terms of a sum of Kronecker product, is good. I don't have a specific number in mind.

As for the size of $A_i, B_i$, they are square, of side $1e4$, $1e3$ respectively. I suppose then that $N$ will be much smaller than these numbers.

Answer 1

The recent state of the art is described in section 7.2 of Simoncini, V. "Computational methods for linear matrix equations." SIAM Rev. 58, 377 (2016), https://doi.org/10.1137/130912839. Your equation is equivalent to equation (2) in that reference. A lightly reformatted quote from there:

Equation (2) is very difficult to analyze in its full generality, and necessary and sufficient conditions for the existence and uniqueness of the solution explicitly based on $\{A_i\}$, $\{B_i\}$ are hard to find, except for some very special cases.