Editing Levinson recursion (section)

{{Short description|Recursive algorighm in linear algebra}}
'''Levinson recursion''' or '''Levinson–Durbin recursion''' is a procedure in [[linear algebra]] to [[recursion|recursively]] calculate the solution to an equation involving a [[Toeplitz matrix]]. The [[algorithm]] runs in {{math|[[Big O notation|Θ]](''n''<sup>2</sup>)}} time, which is a strong improvement over [[Gauss–Jordan elimination]], which runs in Θ(''n''<sup>3</sup>).

The Levinson–Durbin algorithm was proposed first by [[Norman Levinson]] in 1947, improved by [[James Durbin]] in 1960, and subsequently improved to {{math|4''n''<sup>2</sup>}} and then {{math|3''n''<sup>2</sup>}} multiplications by W. F. Trench and S. Zohar, respectively.

Other methods to process data include [[Schur decomposition]] and [[Cholesky decomposition]]. In comparison to these, Levinson recursion (particularly split Levinson recursion) tends to be faster computationally, but more sensitive to computational inaccuracies like [[round-off error]]s.

The Bareiss algorithm for [[Toeplitz matrix|Toeplitz matrices]] (not to be confused with the general [[Bareiss algorithm]]) runs about as fast as Levinson recursion, but it uses {{math|''O''(''n''<sup>2</sup>)}} space, whereas Levinson recursion uses only ''O''(''n'') space.  The Bareiss algorithm, though, is [[numerical stability|numerically stable]],<ref>Bojanczyk et al. (1995).</ref><ref>Brent (1999).</ref> whereas Levinson recursion is at best only weakly stable (i.e. it exhibits numerical stability for [[Condition number|well-conditioned]] linear systems).<ref>Krishna & Wang (1993).</ref>

Newer algorithms, called ''asymptotically fast'' or sometimes ''superfast'' Toeplitz algorithms, can solve in {{math|Θ(''n'' log<sup>''p''</sup>''n'')}} for various ''p'' (e.g. ''p'' = 2,<ref>{{Cite web |url=http://www.maths.anu.edu.au/~brent/pd/rpb143tr.pdf |title=Archived copy |access-date=2013-04-01 |archive-date=2012-03-25 |archive-url=https://web.archive.org/web/20120325215317/http://maths.anu.edu.au/~brent/pd/rpb143tr.pdf |url-status=dead }}</ref><ref>{{cite web |url=http://etd.gsu.edu/theses/available/etd-04182008-174330/unrestricted/kimitei_symon_k_200804.pdf |title=Archived copy |access-date=2009-04-28 |url-status=dead |archive-url=https://web.archive.org/web/20091115041852/http://etd.gsu.edu/theses/available/etd-04182008-174330/unrestricted/kimitei_symon_k_200804.pdf |archive-date=2009-11-15 }}</ref> ''p'' = 3 <ref>{{cite web |url=http://saaz.cs.gsu.edu/papers/sfast.pdf |title=Archived copy |website=saaz.cs.gsu.edu |access-date=12 January 2022 |archive-url=https://web.archive.org/web/20070418074240/http://saaz.cs.gsu.edu/papers/sfast.pdf |archive-date=18 April 2007 |url-status=dead}}</ref>). Levinson recursion remains popular for several reasons; for one, it is relatively easy to understand in comparison; for another, it can be faster than a superfast algorithm for small ''n'' (usually ''n''&nbsp;<&nbsp;256).<ref>{{Cite web |url=http://www.math.niu.edu/~ammar/papers/amgr88.pdf |title=Archived copy |access-date=2006-08-15 |archive-date=2006-09-05 |archive-url=https://web.archive.org/web/20060905064921/http://www.math.niu.edu/~ammar/papers/amgr88.pdf |url-status=dead }}</ref>