On Thu, Mar 20, 2014 at 1:36 PM, Dag Sverre Seljebotn <d.s.seljebotn@astro.uio.no> wrote:

On 03/20/2014 02:26 PM, Dag Sverre Seljebotn wrote:

Order-of-matrix-multiplication is literally my textbook example of a dynamic programming problem with complexity O(n^2) where n is number of terms (as in, it's how dynamic programming is introduced in my textbook).

I don't think adding sparse or diagonal matrices changes this as long as you only deal with chained @ and make some simple assumptions of the cost of a FLOP in sparse @ dense, sparse @ sparse, dense @ dense, and so on.

Where you need anything more than very simple dynamic programming algorithms is when you add + into the mix ("whether to use the distributive rule or not" and so on).

I'm positive to the chained @ idea, I think it's the answer to "what we really want".

Sorry, I totally misunderstood this. The question is of course how you dispatch technically (where the __matmul__ function lives and which one to use), not figuring out what you want done.

Or even more specifically, the question is whether getting the chance to use dynamic programming on chains of @'s (and only @'s!) is so valuable that we want to have a special parsing+dispatch rule to allow it. I have to say that after glancing at a few hundred 'dot' calls, I'm not as convinced that this is useful in practice. There are lots of complex expressions out there involving 'dot', and relatively few of them involve long chains of 'dot' calls [1][2]. There are strategies for doing whole-expression optimization that work for more general expressions, not just @ -- e.g. numexpr, numba, theano -- at the cost of a bit more intrusiveness. And as numpy gets better at supporting non-ndarray types, then it'll be easier to seamlessly support low-impact deferred computation APIs like: a, b, c = defer(a, b, c) d = np.sin(a) + a @ b @ c e = d / (a + b + c + d) return force(e) Having a special dispatch for @ would only help with one of the computations here. -n [1] http://mail.scipy.org/pipermail/numpy-discussion/2014-March/069565.html [2] http://mail.scipy.org/pipermail/numpy-discussion/2014-March/069578.html -- Nathaniel J. Smith Postdoctoral researcher - Informatics - University of Edinburgh http://vorpus.org