Levinson recursion

Levinson recursion, also called Levinson-Durbin recursion, is a procedure in linear algebra for recursively calculating the solution to an equation involving a Toeplitz matrix. It runs in quadratic time, a strong improvement over Gauss-Jordan elimination, which takes cubic time. Norman Levinson proposed the algorithm in 1947, James Durbin improved it in 1960, and W. F. Trench and S. Zohar later reduced the multiplication count to 4n squared and then 3n squared. Compared with Schur and Cholesky decomposition it tends to be faster, but it is more sensitive to round-off errors; it is at best weakly stable. The Bareiss algorithm for Toeplitz matrices is about as fast and numerically stable but needs quadratic space, whereas Levinson recursion needs only linear space. Newer superfast Toeplitz algorithms exist, yet Levinson recursion stays popular because it is relatively easy to understand and can beat them for small matrices.