# Use of graph theory to determine tensor contraction ordering

I am considering using a computer program to execute tensor contractions like the following:

$\displaystyle \sum_{ij}^{o} \sum_{ab}^{v} \sum_{KL}^{X} B_{ia}^{K} B_{ia}^{L} B_{jb}^{K} B_{jb}^{L}$

Note: K and L are indices, not exponents.

Since the dimensions $o$,$v$, and $X$ are all different, it will require different amounts of computer time to do the contractions in different orders. I have written a program that does a brute force search of the possible contraction path orders. I would now like to teach this program that contracting over two symmetrical indices ($i$ or $j$, $a$ or $b$) give equivalent paths, and thus do not need to be considered independently. It has been suggested to me that this can be done using graph theory, by making some sort of graph of the connectivity of the indices in the different tensors; however, no more details were provided. Does anyone have any guidance on an efficient way for the program to recognize that certain paths are not unique?

-
Could you clarify "like the following"? A) Does a $B$ always have $3$ indices? B) Does the summation always involve $3$ dimensions? C) Does the multiplication always involve $4$ $B$'s? D) Does the summation always go over $2$ indices per dimension? E) None of the above? F) Anything else that is fixed? –  Glen The Udderboat Jan 22 '13 at 10:08
E) None of the above. Ideally, I would like a solution that can examine a set of general tensors, and a list of indices over which to contract, and figure out which contractions are equivalent (as a contraction over 'i' is equivalent to a contraction over 'j' in this problem) in something less than N! time. –  Sam Manzer Jan 22 '13 at 19:10
Please bear with me. Why doesn't the answer (to your underlying problem) simply roll out of the definition of symmetry? I am thinking of two possible defs. The first def is that $i$ and $j$ are symmetrical iff i) the "substring" $\mathcal{S}_i$ starting with the first $B_{i\cdot}^{\cdot}$ term and ending with the last $B_{i\cdot}^{\cdot}$ term does not overlap with $\mathcal{S}_j$ and ii) $\mathcal{S}_i$ and $\mathcal{S}_j$ are isomorphic. In the second def i) becomes the stronger i') $S_i$ consists of $B_{i\cdot}^{\cdot}$ terms only and $S_j$ consists of $B_{j\cdot}^{\cdot}$ terms only. –  Glen The Udderboat Jan 23 '13 at 12:38
That may work - I am uncertain, however. I feel like there may be cases in which $S_i$ and $S_j$ are isomorphic, but $S_j$ is coupled to some different tensor by a shared index that may make the paths not equivalent in the contraction problem. Thank you for your suggestion though, I will try to come up with a proof one way or another. –  Sam Manzer Jan 24 '13 at 6:09