# Inverting a sum of easy to invert linear terms?

Below are some examples of linear equations with $$d\times d$$ matrices $$Y,A,B,C,D$$ which can be solved for unknown $$d\times d$$ matrix $$X$$ in $$O(d^3)$$ time. Repeated indices in each term are summed over:

\begin{align} Y_{ik}&=A_{ij}X_{jk}+A_{kj}X_{ji}\\ Y_{ik}&=A_{ij} X_{jk} + A_{jk} X_{ij}\\ Y_{il}&=A_{ij} B_{kl} X_{jk} + C_{ij} D_{kl} X_{kj}\\ Y_{il}&=A_{ij} B_{kl} X_{jk} + C_{ij} D_{kl} X_{kj}+C_{jk}D_{il} X_{jk}\\ Y_{il}&=A_{ij} B_{kl}X_{jk} +C_{jk}D_{il} X_{jk}\\ \end{align}

Is there a generic approach for finding fast solvers for these kinds of equations? I'm wondering if there's a generic algorithm for solving sum of factored linear systems analogous to what can be done for sparse linear systems (if sparsity pattern has bounded treewidth, algebraic inversion is easy)

A generic solution for equations above takes $$O(d^6)$$ time, while traditional approach for a $$O(d^3)$$ algorithm needs some "trick" from numerical linear algebra.

More generally, what can we say about when is the following equation is easy to solve? $$Y=g(x)=\sum_f f(X)$$

Here, $$X$$ is a tensor, and each $$f(X)$$ is a linear function of $$X$$ whose inversion is easy, whereas inversion of a general linear function over $$X$$ is considered "hard".

I suspect that one sufficient condition for easy inversion is when formulas for different $$f$$'s involve summations over disjoint indices of $$X$$. However, this is more restrictive than examples above where summation indices overlap between terms.

Edit the examples above are solved (in order) 1) utilize the fact that Y is symmetric 2) lyapunov solver 3) generalized t-sylvester solver 4) generalized t-sylvester + Sherman–Morrison 5) apply vec to both sides, use Sherman–Morrison formula, distribute inverse over Kronecker product

• It'd be nice to incorporate the matrix notation into the question, which, if I've done it right, would be (in order) $Y=AX+X^TA^T$, $Y=AX+XA$, $Y=AXB+CX^TD$, $Y=AXB+CX^TD + Dtr(C^T X)$ (is that really what you meant for that one?), $Y=AXB+Dtr(C^TX)$. Refs for how to do those in $O(d^3)$ would be nice, though I guess several are exercises. Also, what do you mean by "master algorithm for counting structures on graphs"? I couldn't find it by searching. Nov 7, 2020 at 8:09
• Yes, that's the right conversion, I've added references on how to solve them which I originally omitted because they seemed too diverse to suggest a generic algorithm. There seem to be a few "master" algorithms for counting, one example is from the constructive proof of Theorem 14.38 of Flum's "Parameterized Complexity Theory" -- "For every polynomial time decidable class C of structures of bounded tree width, the problem p-#Emb(C) has an fptras" Nov 7, 2020 at 16:34
• A more general class seems to be called "multiterm linear matrix equation" and the complexity of solving it seems not known -- pure.mpg.de/rest/items/item_3165974/component/file_3165975/… Nov 17, 2020 at 23:59
• FYI: Wilson & Maglione solve another type of system of equations (so-called simulateneous Sylvester equations $XA_i - Y B_i = C_i$ for all $i$, where $X,Y,A_i,B_i,C_i$ are $d \times d$ matrices), which normally would take $O(d^6)$ time, in $O(d^{3.5})$ time: youtube.com/watch?v=SNtzwM8lDKs. Not exactly the same as the others, but still in the same spirit. Nov 18, 2020 at 2:47
• Thanks for the reference ... I watched that talk and I'm confused....if we have $n=d$ equations, it takes $O(d^4)$ just to evaluate this system of equations, yet they claim a $O(d^{3.5})$ algorithm to solve it Nov 18, 2020 at 19:02