The performance of optimaltree

[GiggleLiu]

Consider the problem of the optimal contraction ordering of Fullerene structured tensor network with 60 nodes and 90 edges, its contraction complexity is only approximately 10. Using optimaltree function, I did not find the optimal contraction ordering in several minutes.

@Jutho
Do you think setting the contraction complexity upper bound would help truncating the search space? https://github.com/Jutho/TensorOperations.jl/blob/5283953460f70cb8a8b6746b20ed534a274ca27e/src/indexnotation/optimaltree.jl#L7

Network data

(1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12), (13, 14, 15), (7, 16, 17), (18, 19, 20), (10, 21, 22), (23, 24, 25), 
(1, 16, 26), (27, 28, 29), (4, 21, 30), (13, 31, 32), (18, 31, 33), (26, 34, 35), (30, 36, 37), (38, 39, 40),
 (38, 41, 42), (39, 43, 44), (41, 45, 46), (47, 48, 49), (50, 51, 52), (23, 43, 53), (27, 45, 53), (32, 54, 55), 
(33, 56, 57), (34, 58, 59), (36, 60, 61), (62, 63, 64), (65, 66, 67), (17, 47, 68), (22, 50, 69), (48, 62, 70), 
(51, 63, 71), (54, 72, 73), (56, 72, 74), (73, 75, 76), (74, 77, 78), (75, 79, 80), (77, 79, 81), (2, 44, 82), 
(5, 46, 83), (8, 55, 84), (11, 57, 85), (70, 86, 87), (71, 86, 88), (68, 82, 89), (69, 83, 90), (35, 76, 84),
 (37, 78, 85), (58, 65, 80), (60, 66, 81), (24, 28, 67), (40, 87, 89), (42, 88, 90), (14, 19, 64), (9, 15, 49),
 (12, 20, 52), (3, 25, 59), (6, 29, 61)

[GiggleLiu]

It turns out, using Tuple to represent tree is very slow...

Please try the following code.

const order = (7, 14, 13, 5, 56,
    25, 26, 58, 29, 57,
    4, 44, 36, 35, 43, 3, 21, 33, 34, 22,
    50, 38, 37, 49, 6, 31, 45, 46, 32, 8,
    47, 54, 55, 48, 12, 16, 40, 39, 15, 10,
    1, 41, 19, 17, 18, 20, 42, 2, 60, 28, 52, 30, 51, 27, 59,
    9, 23, 24, 11, 53)

order2tree(order) = length(order) == 1 ? order[1] : (order2tree(order[1:end-1]), order[end])
tree = order2tree(order)

There is a crossover between 20-30 nodes, after that size, the performance becomes much worse.

[Jutho]

Thanks for this issue; I have to admit that I did not foresee these kind of applications. Furthermore, I certainly agree that the optimaltree could use some work, e.g. to expose more functionality or options to the user. Replacing tuples by a dedicated tree type might also be useful.

Note however that the optimaltree algorithm is anyway an exhaustive method that in a clever way will end up trying all posibilities, and thus scales exponentially/factorially (probably) with the number of tensors (nodes). With the cost capping, it might indeed be feasible to find optimal contractions of such large networks (if they exist), but I would certainly still expect this to take a while.