scipy/scipy — pull request #2972 by argriffing (2013-10-10 03:03:34+00:00)
Title: MAINT: expm speedup for small matrices, through benchmarked one-norm estimation vs. calculation tradeoffs.

In the current scipy expm implementation, estimation of the 1-norm of matrix products and powers dominates the computation time for the expm of small matrices. While for large or sparse matrices this 1-norm can be estimated using clever tricks that are much faster than exact calculation, for small matrices it is faster to just multiply them out and compute the 1-norm exactly. This PR does some related benchmarking and adds an arbitrary threshold below which the 1-norm is computed exactly within the expm calculation.

The result is to speed up the expm of small matrices by an amount that may approach or exceed the EXPOKIT speed (which I would like to check, when some version of the expokit wrapper is merged). The underlying slowness is probably due to my sloppy onenormest code, so if that code were to be improved then presumably the matrix size threshold for the exact vs. approximate 1-norm calculation could be reduced. The timings listed here are not meant to be rigorous but are rather intended to demonstrate the existence of such a crossover point, for example appearing somewhere around n=300 on my system.

```
calculation and estimation of one-norm of matrix squaring
==============================================================
shape | repeats | operation | time
| (seconds)
--------------------------------------------------------------
(2, 2) | 100 | matrix sampling | 0.00
(2, 2) | 100 | one-norm exact | 0.01
(2, 2) | 100 | one-norm estimate | 0.03
(3, 3) | 100 | matrix sampling | 0.00
(3, 3) | 100 | one-norm exact | 0.01
(3, 3) | 100 | one-norm estimate | 0.06
(5, 5) | 100 | matrix sampling | 0.00
(5, 5) | 100 | one-norm exact | 0.01
(5, 5) | 100 | one-norm estimate | 0.04
(10, 10) | 100 | matrix sampling | 0.00
(10, 10) | 100 | one-norm exact | 0.01
(10, 10) | 100 | one-norm estimate | 0.05
(30, 30) | 100 | matrix sampling | 0.00
(30, 30) | 100 | one-norm exact | 0.03
(30, 30) | 100 | one-norm estimate | 0.50
(100, 100) | 100 | matrix sampling | 0.06
(100, 100) | 100 | one-norm exact | 0.08
(100, 100) | 100 | one-norm estimate | 0.62
(300, 300) | 100 | matrix sampling | 0.48
(300, 300) | 100 | one-norm exact | 0.93
(300, 300) | 100 | one-norm estimate | 1.00
(500, 500) | 100 | matrix sampling | 1.31
(500, 500) | 100 | one-norm exact | 3.47
(500, 500) | 100 | one-norm estimate | 1.48
(1000, 1000) | 100 | matrix sampling | 5.28
(1000, 1000) | 100 | one-norm exact | 22.93
(1000, 1000) | 100 | one-norm estimate | 5.69
```