ENH: add `mdot`: fast dot with multiple arguments.

This is not ready to be merged!

`mdot` makes it easy to chain `dot`. Think of `mdot` as this:

    def mdot(*args): return reduce(np.dot, args)

However, `mdot` uses the fact that matrix multiplication is associative and
finds the optimal order of multiplications with dynamic programing before
doing the mutiplication. This can speed up the multiplication quite a bit.

The algorithm follows:
Cormen, "Introduction to Algorithms", Chapter 15.2, p. 370-378

Note: currently `mdot` only works with arrays which have `ndim == 2` to avoid
ambiguities of `dot`. Also see the discussion in #4311.

TODO:
- [x] Decide if `ndim != 2` should be ok
- [x] Add unittests
- [x] decide on name. possible names are:
  - `mdot`: think "multi dot"
  - `multidot`: as above :)
  - `multi_dot`: as above :)
  - `chain_dot`
  - `fdot`: think "fast dot" (should the parameter optimize be optional then? I don't think so.)
  - `ddot`: think "multiple d for multiple dot"
  - `cdot`: think "chain dot"
  - `odot`: think "optimal do

Yeah, good point.

So in the long run, it might be a nice enhancement to add space-optimal
orderings, or mixed critera. Also, a related observation is that, since
time-optimal and space-optimal are different criteria, for a given fixed
parenthesization there will generally be more-or-less space-optimal orders
for evaluating it, so even when optimizing for time we might want run a
secondary space-optimization step.

But, as far as immediate concrete actions go, the only thing this PR needs
(on this axis) is to remove the current optimize= flag. Any further
enhancements can be done separately, they don't need to block this ("the
perfect is the enemy of the good" and all that).

On Sat, Sep 13, 2014 at 7:52 PM, argriffing <notifications@github.com>
wrote:

> In numpy/linalg/linalg.py:
>
> > +    row and column vector. The other arguments must be 2-D.
> > +
> > +    Think of `multi_dot` as::
> > +
> > +        def multi_dot(arrays): return functools.reduce(np.dot, arrays)
> > +
> > +
> > +    Parameters
> > +    ----------
> > +    arrays : sequence of array_like
> > +        First and last argument can be 1-D and are treated respectively as
> > +        row and column vector, the other arguments must be 2-D.
> > +    optimize : bool, optional
> > +        If `True` (default) a optimal parenthesization is chosen to
> > +        speed up the multiplication, otherwise
> > +        `functools.reduce(np.dot, arrays)` is used.
>
>  If there are two different possible optimization criteria - which I
> doubt,
>
> @njsmith <https://github.com/njsmith> I'm pretty sure @jaimefrio
> <https://github.com/jaimefrio>'s example shows there are. If all of the
> matrices in his example are nearly square (say order 1000 plus or minus up
> to three or four rows and columns) then reordering to slightly reduce the
> number of operations would increase the required amount of temporary
> storage.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/numpy/numpy/pull/4977/files#r17515377>.
>



-- 
Nathaniel J. Smith
Postdoctoral researcher - Informatics - University of Edinburgh
http://vorpus.org