scipy/scipy — pull request #2754 by argriffing (2013-08-20 05:17:55+00:00)
Title: ENH: levinson-durbin

I implemented this off of the wikipedia page http://en.wikipedia.org/wiki/Levinson_recursion. In its current form it's faster than naive solve() for big enough matrices, and maybe if it gets some cython love it could be even faster. I also noticed that there are some O(N^2) memory algorithms that are more numerically stable which may be more appropriate, although they use more memory.

This implementation should partially address https://github.com/scipy/scipy/issues/2432 and I think there has been some discussion on mailing lists related to this feature in particular, in the context of scipy.signal.

```
Levinson-Durbin vs. generic solver
==============================================================
shape | solver | dtype | time
| | | (seconds)
--------------------------------------------------------------
(100, 100) | generic | float64 | 0.00
(100, 100) | toeplitz | float64 | 0.00
(100, 100) | generic | complex128 | 0.00
(100, 100) | toeplitz | complex128 | 0.00
(300, 300) | generic | float64 | 0.01
(300, 300) | toeplitz | float64 | 0.02
(300, 300) | generic | complex128 | 0.03
(300, 300) | toeplitz | complex128 | 0.02
(1000, 1000) | generic | float64 | 0.26
(1000, 1000) | toeplitz | float64 | 0.08
(1000, 1000) | generic | complex128 | 1.03
(1000, 1000) | toeplitz | complex128 | 0.11
```