Take the 2-minute tour ×
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.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.