8
$\begingroup$

I want to find an efficient algorithm for calculating a sum of products with entangled indices. For example, $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} A_{ij}A_{jk}A_{ki}$, where $A_{ij}$ is the a $i$-th row and $j$-th column element of a symmetric matrix A. The above example is equivalent to calculate the trace of the cubic of a symmetric matrix. So this is related to matrix multiplication.

In addition, the products can be extended to have more elements, like $A_{ij}A_{ik}A_{il}A_{jk}A_{jl}A_{kl}$, where all indices are tangled together (like a clique in a graph), and $A$ can be also extend to a symmetric higher-rank tensor. The naive algorithm for calculating the sum is $O(n^m)$, where $m$ is the number of indices. I want to reduce the computational complexity as much as possible. When $A$ is a matrix and $m=3$, this become a matrix multiplication problem, but how about more general cases?

Question1: I am wondering if anyone know any math subjects or books related to my problem.

Question2: What is the mathematical term for the sum of products with entangled indices? It is difficult for me to google references without the standard terminology.

$\endgroup$
2
  • 3
    $\begingroup$ Your title is rather non-descriptive. You may want to modify it so people can get a basic idea of what the question is about. $\endgroup$
    – Ricardo Andrade
    Jun 27 '13 at 1:47
  • $\begingroup$ The $m = 3$ case is different because every index appears in exactly two terms (only $A_{ij}$ and $A_{ki}$ contain an $i$-index). That is what allows for the "matrix multiplication" (or more generally, tensor contraction) interpretation. $\endgroup$ Jun 27 '13 at 7:52
5
$\begingroup$

Update 2: If you consider fast matrix multiplication algorithms, then you can in fact do better than the naive $O(n^4)$. Let me suppose that there exists an algorithm that computes the product of an $l\times m$ by $m\times n$ matrix in $O(l m^\epsilon n)$ time, with $\epsilon < 1$. Let me slightly change the notation $A(i,j) \to A(i;j)$ to highlight the difference between the ingoing and outgoing matrix indices. Then consider the following steps.

  1. fixing $({k,l,i})$ do $n^3$ times ($1\times 1$ by $1\times 1$): $B_1(k,l;i) = A(k;l) A(k;i) A(l;i)$
  2. fixing $(k)$ do $n$ times ($n\times n$ by $n\times n$): $B_2(k,j;i) = \sum_l A(j;l) B_1(k,l;i)$
  3. fixing $(j)$ do $n$ times ($1\times n$ by $n\times n$): $B_3(j;i) = \sum_k A(j;k) B_2(k,j;i)$
  4. fixing $(i)$ do $n$ times ($1\times n$ by $n\times 1$): $B_4(i) = \sum_j A(i;j) B_3(j;i)$
  5. do $1$ time ($1\times n$ by $n\times 1$): $B_5 = \sum_i B_4(i)$

$B_5$ is the sum that you want, as you can see by substituting each $B_i$ into the next expression. The prefix of each step indicates the complexity as a given number (for each value of listed indices) of rectangular matrix multiplications of the indicated sizes, which also gives the storage requirements.

As you can see, the run time complexity will be dominated by step 2, with $O(n^{3+\epsilon})$ operations. Steps 1 and 2 dominate in terms of storage, requiring $O(n^3)$ space. As you point out in the comments, $\epsilon = 0.37$ is the best known value. Then $3+\epsilon = 3.37 < 4$ does beat the naive method.

Update: Sorry, on further reflection, I don't think you can do better with this particular contraction than $O(n^4)$, at least not with the optimizations I had in mind. These optimizations are of a dynamical programming kind. That is, to use extra storage for intermediate results with the hope of gaining a speedup in the operations that take you from one intermediate result to the next. In this case, the storage would consist of multidimensional arrays of size $O(n^d)$ (for some $d$) and the operations consist of multiplication by one ore more copies of $A$ and summation over one or more of the array indices, which involve $O(n^f)$ operations (for some $f$). But any way I try to do that always yields $f\ge 4$, which is no better than the naive approach.


Expressions like these are sometimes known as tensor networks. That should give you a good keyword for looking into the literature. Also, you might find helpful some of the "sparse factorization" techniques from one of my old articles (arXiv:0809.3190). You can safely ignore everything except section 5 and the discussion of how to evaluate the product-trace in equation (40).

As you've written it, the evaluation complexity is $O(n^4)$. I think this case can be simplified to $O(n^3)$. If I have time later, I'll try to write that out in more detail.

$\endgroup$
6
  • 1
    $\begingroup$ Hey Igor, good to see you on Math.SE! $\endgroup$ Jun 27 '13 at 7:53
  • 1
    $\begingroup$ I just clicked on the question and saw that it was migrated. Not really sure why, unless it was the work of the algebraic geometry mafia. ;-) $\endgroup$ Jun 27 '13 at 8:26
  • 1
    $\begingroup$ Nah, doesn't look like it. In fact, none of the ones who voted to migrate work in algebraic geometry; if anything I'd say it is the analysis mafia. :-) $\endgroup$ Jun 27 '13 at 8:29
  • $\begingroup$ I think there is a better way than the naive approach, even though I do not know how at this moment. m = 3 can be done by matrix multiplication and the up to date algorithm for matrix multiplication need $O(n^{2.37})$ (en.wikipedia.org/wiki/Matrix_multiplication). I guess I need some abstract algebra tool to handle this problem. $\endgroup$
    – icehouse
    Jun 27 '13 at 20:45
  • $\begingroup$ @icehouse, you're right. I hadn't considered fast multiplication algorithms. I've updated my answer to reflect that. $\endgroup$ Jun 27 '13 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.