Doubling Levinson/Schur algorithm and its implementation
H.M. Zhang, Pierre Duhamel · International Conference on Acoustics, Speech, and Signal Processing · 2003
The authors propose a doubling Levinson/Schur algorithm (DLSA) for the superfast solution of real positive definite Toeplitz systems of order n+1, where n=2/sup v/. This algorithm belongs to the class of development the class of Levinson and Schur algorithms based on a doubling (or divide and conquer) strategy, but with the lowest cross point over the initial Levinson algorithm and the lowest arithmetic complexity. The minimum number of multiplications required for this class of algorithm is given. The algorithm was implemented in order to check whether the improvement in arithmetic complexity was hidden by a loss of regularity, resulting in less efficient implementations.>