Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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(i,j)A(j,k)A(k,i)$, where A(i,j) 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(i,j)A(i,k)A(i,l)A(j,k)A(j,l)A(k,l), where all indices are tangled together (like a clique in a graph), and A can be also extend to a symmetric multi-dimensional array. 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 wandering if anyone know any math fields 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.

Thank you very much in advance for your time!

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.