Finds the path by contracting the best pair until the input list is exhausted. The best pair is found by minimizing the tuple ``(-prod(indices_removed), cost)``. What this amounts to is prioritizing matrix multiplication or inner product operations, then Hadamard like operation
(input_sets, output_set, idx_dict, memory_limit)
| 310 | return mod_results |
| 311 | |
| 312 | def _greedy_path(input_sets, output_set, idx_dict, memory_limit): |
| 313 | """ |
| 314 | Finds the path by contracting the best pair until the input list is |
| 315 | exhausted. The best pair is found by minimizing the tuple |
| 316 | ``(-prod(indices_removed), cost)``. What this amounts to is prioritizing |
| 317 | matrix multiplication or inner product operations, then Hadamard like |
| 318 | operations, and finally outer operations. Outer products are limited by |
| 319 | ``memory_limit``. This algorithm scales cubically with respect to the |
| 320 | number of elements in the list ``input_sets``. |
| 321 | |
| 322 | Parameters |
| 323 | ---------- |
| 324 | input_sets : list |
| 325 | List of sets that represent the lhs side of the einsum subscript |
| 326 | output_set : set |
| 327 | Set that represents the rhs side of the overall einsum subscript |
| 328 | idx_dict : dictionary |
| 329 | Dictionary of index sizes |
| 330 | memory_limit : int |
| 331 | The maximum number of elements in a temporary array |
| 332 | |
| 333 | Returns |
| 334 | ------- |
| 335 | path : list |
| 336 | The greedy contraction order within the memory limit constraint. |
| 337 | |
| 338 | Examples |
| 339 | -------- |
| 340 | >>> isets = [set('abd'), set('ac'), set('bdc')] |
| 341 | >>> oset = set() |
| 342 | >>> idx_sizes = {'a': 1, 'b':2, 'c':3, 'd':4} |
| 343 | >>> _greedy_path(isets, oset, idx_sizes, 5000) |
| 344 | [(0, 2), (0, 1)] |
| 345 | """ |
| 346 | |
| 347 | # Handle trivial cases that leaked through |
| 348 | if len(input_sets) == 1: |
| 349 | return [(0,)] |
| 350 | elif len(input_sets) == 2: |
| 351 | return [(0, 1)] |
| 352 | |
| 353 | # Build up a naive cost |
| 354 | contract = _find_contraction(range(len(input_sets)), input_sets, output_set) |
| 355 | idx_result, new_input_sets, idx_removed, idx_contract = contract |
| 356 | naive_cost = _flop_count(idx_contract, idx_removed, len(input_sets), idx_dict) |
| 357 | |
| 358 | # Initially iterate over all pairs |
| 359 | comb_iter = itertools.combinations(range(len(input_sets)), 2) |
| 360 | known_contractions = [] |
| 361 | |
| 362 | path_cost = 0 |
| 363 | path = [] |
| 364 | |
| 365 | for iteration in range(len(input_sets) - 1): |
| 366 | |
| 367 | # Iterate over all pairs on first step, only previously found pairs on subsequent steps |
| 368 | for positions in comb_iter: |
| 369 |
no test coverage detected