An Algorithm for Solving Toeplitz Systems by Embedding in Infinite Systems
Giuseppe Rodriguez, S. Seatzu, Daniela Theis · Birkhäuser Basel eBooks · 2005
In this paper we propose a new algorithm to solve large Toeplitz systems. It consists of two steps. First, we embed the system of order N into a semi-infinite Toeplitz system and compute the first N components of its solution by an algorithm of complexity O ( N log 2 N ). Then we check the accuracy of the approximate solution, by an a posteriori criterion, and update the inaccurate components by solving a small Toeplitz system. The numerical performance of the method is then compared with the conjugate gradient method, for 3 different preconditioners. It turns out that our method is compatible with the best PCG methods concerning the accuracy and superior concerning the execution time.