Levinson recursion

Levinson recursion or Levinson–Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix. The algorithm runs in Θ(n2) time, which is a strong improvement over Gauss–Jordan elimination, which runs in Θ(n3).

The Levinson–Durbin algorithm was proposed first by Norman Levinson in 1947, improved by James Durbin in 1960, and subsequently improved to 4n2 and then 3n2 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 errors.

The Bareiss algorithm for Toeplitz matrices (not to be confused with the general Bareiss algorithm) runs about as fast as Levinson recursion, but it uses O(n2) space, whereas Levinson recursion uses only O(n) space. The Bareiss algorithm, though, is numerically stable,[1][2] whereas Levinson recursion is at best only weakly stable (i.e. it exhibits numerical stability for well-conditioned linear systems).[3]

Newer algorithms, called asymptotically fast or sometimes superfast Toeplitz algorithms, can solve in Θ(n logpn) for various p (e.g. p = 2,[4][5] p = 3 [6]). 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 < 256).[7]

  1. ^ Bojanczyk et al. (1995).
  2. ^ Brent (1999).
  3. ^ Krishna & Wang (1993).
  4. ^ "Archived copy" (PDF). Archived from the original (PDF) on 2012-03-25. Retrieved 2013-04-01.{{cite web}}: CS1 maint: archived copy as title (link)
  5. ^ "Archived copy" (PDF). Archived from the original (PDF) on 2009-11-15. Retrieved 2009-04-28.{{cite web}}: CS1 maint: archived copy as title (link)
  6. ^ "Archived copy" (PDF). saaz.cs.gsu.edu. Archived from the original (PDF) on 18 April 2007. Retrieved 12 January 2022.{{cite web}}: CS1 maint: archived copy as title (link)
  7. ^ "Archived copy" (PDF). Archived from the original (PDF) on 2006-09-05. Retrieved 2006-08-15.{{cite web}}: CS1 maint: archived copy as title (link)