<p>Below are some examples of linear equations with <span class="math-container">$d\times d$</span> matrices <span class="math-container">$Y,A,B,C,D$</span> which can be solved for unknown <span class="math-container">$d\times d$</span> matrix <span class="math-container">$X$</span> in <span class="math-container">$O(d^3)$</span> time. Repeated indices in each term are summed over:</p>
<p><span class="math-container">\begin{align}
Y_{ik}&amp;=A_{ij}X_{jk}+A_{kj}X_{ji}\\
Y_{ik}&amp;=A_{ij} X_{jk} + A_{jk} X_{ij}\\
Y_{il}&amp;=A_{ij} B_{kl} X_{jk} + C_{ij} D_{kl} X_{kj}\\
Y_{il}&amp;=A_{ij} B_{kl} X_{jk} + C_{ij} D_{kl} X_{kj}+C_{jk}D_{il} X_{jk}\\
Y_{il}&amp;=A_{ij} B_{kl}X_{jk} +C_{jk}D_{il} X_{jk}\\
\end{align}</span></p>
<p>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)</p>
<p>A generic solution for equations above takes <span class="math-container">$O(d^6)$</span> time, while traditional approach for a <span class="math-container">$O(d^3)$</span> algorithm needs some &quot;trick&quot; from numerical linear algebra.</p>
<p>More generally, what can we say about when is the following equation is easy to solve?
<span class="math-container">$$Y=g(x)=\sum_f f(X)$$</span></p>
<p>Here, <span class="math-container">$X$</span> is a tensor, and each <span class="math-container">$f(X)$</span> is a linear function of <span class="math-container">$X$</span> whose inversion is easy, whereas inversion of a general linear function over <span class="math-container">$X$</span> is considered &quot;hard&quot;.</p>
<p>I suspect that one sufficient condition for easy inversion is when formulas for different <span class="math-container">$f$</span>'s involve summations over disjoint indices of <span class="math-container">$X$</span>. However, this is more restrictive than examples above where summation indices overlap between terms.</p>
<p><strong>Edit</strong> 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</p>

CC BY-SA 4.0
2020-11-07T08:09:41.607Z
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.
Joshua Grochow
CC BY-SA 4.0
2020-11-07T16:34:39.960Z
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"
Yaroslav Bulatov
CC BY-SA 4.0
2020-11-17T23:59:30.700Z
A more general class seems to be called "multiterm linear matrix equation" and the complexity of solving it seems not known -- https://pure.mpg.de/rest/items/item_3165974/component/file_3165975/content
Yaroslav Bulatov
CC BY-SA 4.0
2020-11-18T02:47:11.017Z
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: https://www.youtube.com/watch?v=SNtzwM8lDKs. Not *exactly* the same as the others, but still in the same spirit.
Joshua Grochow
CC BY-SA 4.0
2020-11-18T19:02:03.423Z
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
Yaroslav Bulatov
CC BY-SA 4.0
2020-11-18T19:33:23.317Z
I thought I understood but now I'm a bit confused as well. Maybe the stated runtime was for the case of $O(1)$ equations? We could wait for the preprint I guess, or ask James (I might do the latter).
Joshua Grochow
<na.numerical-analysis>
Inverting a sum of easy to invert linear terms?
Yaroslav Bulatov
# Inverting a sum of easy to invert linear terms?

(Asked by: username_0 on 2020-11-07)

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

**Tags:** na.numerical-analysis
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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"  
> **username_0**: A more general class seems to be called "multiterm linear matrix equation" and the complexity of solving it seems not known -- https://pure.mpg.de/rest/items/item_3165974/component/file_3165975/content  
> **username_1**: 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: https://www.youtube.com/watch?v=SNtzwM8lDKs. Not *exactly* the same as the others, but still in the same spirit.  
> **username_0**: 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  
> **username_1**: I thought I understood but now I'm a bit confused as well. Maybe the stated runtime was for the case of $O(1)$ equations? We could wait for the preprint I guess, or ask James (I might do the latter).  

---

## 0 answers

