updates to 'dp' optimizer

[jcmgray]

Description

These updates the 'dp' optimizer in a few ways:

• fixes some edge case bugs (#116, #118) @yaroslavvb
• allows it to be customized in a few ways (without any impact on performance in the default case):
  • whether to target minimum flop count or minimize size
  • whether to search through outer products
  • how to set the cost_cap iterate strategy (on, off or manual)
• a few tweaks to make the overhead lower for small contractions particularly
• renames DynamicProgrammingOptimizer->DynamicProgramming and add it to the top namespace

I think with these, it would make sense to make the 'optimal' algorithm point at 'dp' since with the outer product search it should now find all the same contractions, and with the cost_cap turned off it's as fast for small contractions as well. This would fix #99. Thoughts @dgasmith? Also cc @mrader1248.

Todos

• [x] document customizable DynamicProgramming
• [ ] one could identify now 'standard tensor network' contractions (i.e. every index appears exactly twice) at the beginning from the index count, and possibly switch to a faster method for computing resulting indices (simply the symmetric difference of inputs)
• [ ] use a version of 'dp' for 'optimal'?
• [ ] have an 'auto'value for the cost_cap that simply turns it off til the contraction is quite big

Status

• [ ] Ready to go

[codecov[bot]]

Codecov Report

Merging #119 into master will increase coverage by 0.05%. The diff coverage is 100%.

[mrader1248]

Can you give me an example, where it is beneficial to construct outer products?

[mrader1248]

Sorry, it took me a while to have a look at this. Overall, LGTM. And especially thanks for fixing this stupid smallest dimension 1 bug.

[jcmgray]

Can you give me an example, where it is beneficial to construct outer products?

I've put this example in the tests (taken from you in another thread I think!):

def test_custom_dp_can_optimize_for_outer_products():
    eq = "a,b,abc->c"

    da, db, dc = 2, 2, 3
    shapes = [(da,), (db,), (da, db, dc)]

    opt1 = oe.DynamicProgramming(search_outer=False)
    opt2 = oe.DynamicProgramming(search_outer=True)

    info1 = oe.contract_path(eq, *shapes, shapes=True, optimize=opt1)[1]
    info2 = oe.contract_path(eq, *shapes, shapes=True, optimize=opt2)[1]

    assert info2.opt_cost < info1.opt_cost

Of course in practice I imagine it's almost never useful. However I think it would make sense for 'dp' to replace the optimal implementation, and if that happens then the option to be guaranteed optimal seems beneficial for testing edge cases etc. Plus for v small sizes there's no penalty hit.

@dgasmith do you have any thoughts on pointing 'optimal' to 'dp'? Maybe in a later PR.

[jcmgray]

@dgasmith Also happy to have a go a adding more docs (e.g. each variable etc) if you think necessary.

[mrader1248]

@jcmgray I see, I thought you found an example where constructing outer products first leads to a better solution even in the asymptotic limit. Maybe it would be good to mention in the docs that allowing for intermediate outer products can lead to horrible optimisation times?

[jcmgray]

@jcmgray I see, I thought you found an example where constructing outer products first leads to a better solution even in the asymptotic limit

Well in the asymptotic limit where da and db are fixed but dc get's larger, indeed the outer product is still necessary here.

Maybe it would be good to mention in the docs that allowing for intermediate outer products can lead to horrible optimisation times?

I've mentioned this in the docstring for the search_outer option, but yes might be worth adding another warning to the main docs as well.

[jcmgray]

OK, so I've added a warning to the 'dp' docs about turning on the outer product search, and factored out the single term parsing of inputs. Unless there are more comments I'll merge in a bit.