This article is cited in 4 papers

A continuation method for solving symmetric Toeplitz systems

M. Van Barel^a, Kh. D. Ikramov^b, A. A. Chesnokov<sup>ba

a</sup> Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200 A, B-3001 Leuven, Belgium
^b Faculty of Computational Mathematics and Cybernetics, Moscow State University, Moscow, 119992, Russia

Abstract: A fast algorithm is proposed for solving symmetric Toeplitz systems. This algorithm continuously transforms the identity matrix into the inverse of a given Toeplitz matrix $T$. The memory requirements for the algorithm are $O(n)$, and its complexity is $O(\log n k(T)n\log n)$, where $k(T)$ is the condition number of $T$. Numerical results are presented that confirm the efficiency of the proposed algorithm.

Key words: Toeplitz matrices, circulants, superfast algorithm, continuation method, iterative refinement, eigenvalues.

UDC: 519.612

Received: 29.12.2007
Revised: 22.05.2008

 English version: Computational Mathematics and Mathematical Physics, 2008, 48:12, 2126–2139

Bibliographic databases:

• 
• 
•