2
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 7, 2020 at 8:09
  • 1
    $\begingroup$ 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" $\endgroup$ Nov 7, 2020 at 16:34
  • $\begingroup$ 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/… $\endgroup$ Nov 17, 2020 at 23:59
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 18, 2020 at 2:47
  • $\begingroup$ 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 $\endgroup$ Nov 18, 2020 at 19:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.