Nasser Akhoundi

This paper describes a new (Formula presented.) solver for the symmetric positive definite Toeplitz system TNxN = bN. The method is based on the block QR decomposition of TN accompanied with Levinson algorithm and its generalized version for solving Schur complements Sm of size m. In our algorithm we use a formula for displacement rank representation of the Sm in terms of generating vectors of the matrix TN, and we assume that N = lm with (Formula presented.). The new algorithm is faster than the classical O(N2)-algorithm for N > 29. Numerical experiments confirm the good computational properties of the new method. © 2015, Springer Science+Business Media New York.