One of the applications of finding mappings of indices is testing whether two expressions are equal (to within dummy indices relabelling and interchanging indices of simple tensors according to their symmetries). Probably, this operation is the most frequent operation that arises in any calculation (like reduction of similar terms). This problem can be solved by finding mapping of indices which maps free indices of one expression onto exactly same free indices of another.
As it well known, contractions between indices in product constitutes a graph. So, the problem of finding mappings between two expressions is equivalent to problem of testing whether two graphs are isomorphic. While no worst-case polynomial-time algorithms are known for the general Graph Isomorphism (GI) and closely related Graph Automorphism (GA) problems, there are several algorithms which solve these problems very effectively in all practical cases (see e.g. [1] and overview given in [2] ). It is important to note, that the complexity of these algorithms (which is still exponential in the worst case) is given in the number of graph vertices, or equivalently in the number of product multipliers.
On the other hand, the existing systems (known to the authors) are based on the so-called indices canonicalisation approach described in [3, 4] . This procedure brings indices of products into unique canonical order using the information about symmetries of its multipliers; when indices of tensors are brought into such order, it becomes trivial to test whether two expressions are equal. As it is shown in cited papers, this problem is equivalent to the problem of double coset enumeration which is known to be $\mathcal{NP}$-hard (see Sec. 4.6.8 in [5] ). Unfortunately, no really satisfactory algorithm for solving this problem has been found to date (see Sec. 4.6.8 in [5] ). Moreover, in contrast to GI problem, the complexity of algorithms for double coset enumeration is given in the number of all indices (free and dummy) of tensor. It is also important, that indices canonicalization is not useful for testing whether two tensors are equal to within free indices relabelling. Additionally, indices canonicalization works only with products of simple tensors, so if e.g. product contains a sum one need to expand out brackets first.
Redberry utilises the first approach, based on the GI finding. The main algorithm, which finds mappings of tensor indices is actually searches for isomorphisms of corresponding graphs. Currently, this algorithm is far from the best known algorithms for GI problem. However, it is specifically suited for typical problems arising in physics and performs well on typical input (i.e. when need to compare a huge number of small graphs; see Benchmarks), but still has exponential complexity for some special cases. Nevertheless, there is a wide area for improvements and this is the main issue of further Redberry development.
Another important subject closely related to tensor comparison, is finding symmetries of complicated tensors. It is clear that from the stand point of graph-theoretical approach, this problem is equivalent to Graph Automorphism problem. This problem is also related to testing whether the expression is zero using only the information about its symmetries (like \(\displaystyle F_{ab}{}F^{bc}{}F_{c}{}^{a} = 0 \) if $F_{ab}$ is antisymmetric). The canonicalization procedure used by other systems can naturally determine whether the expression is zero, while in Redberry one should apply special transformation EliminateDueSymmetries. The algorithm used in Redberry computes automorphism group $Aut(G)$ of corresponding graph $G$ and searches in this group for two equal permutations with different signs: if generators of group can produce two equal permutations with different signs (i.e. symmetry and antisymmetry), that means that corresponding expression is zero. Currently, Redberry uses a brute force algorithm for EliminateDueSymmetries and its performance is about of order of group, i.e. the number of all group elements $|Aut(G)|$, so it is impractical for large symmetric tensors. A vastly improved algorithm is under development and will appear soon in the next Redberry release.
Summarizing this section we point out that in our opinion, the approach based on graph algorithms provides a more flexible way to deal with tensors than canonicalization and has a broader perspective for further performance improvements. The good argument in favour of this point is a performance comparison of Redberry and other systems presented in Benchmarks section.