Controlling noise error in block iterative methods

This paper describes a new \(O(N^{\frac {3}{2}}\log (N))\) solver for the symmetric positive definite Toeplitz system T_Nx_N = b_N. The method is based on the block QR decomposition of T_N accompanied with Levinson algorithm and its generalized version for solving Schur complements S_m of size m. In our algorithm we use a formula for displacement rank representation of the S_m in terms of generating vectors of the matrix T_N, and we assume that N = lm with \(l, m\in \mathbb {N}\). The new algorithm is faster than the classical O(N²)-algorithm for N > 2⁹. Numerical experiments confirm the good computational properties of the new method.