A stabilized superfast solver for nonsymmetric Toeplitz systems (Q2784359)

The subject of this paper is the nonsymmetric Toeplitz system \(Tx= b\). A stabilized superfast solver is presented. In contrast to previous methods, the Toeplitz matrix is not first transformed into another matrix, but an explicit formula for the inverse of the Toeplitz matrix is used. This formula involves the values of the fundamental system at roots of the unity. The fundamental system is a pair of polynomials containing all the information about the Toeplitz matrix. These polynomials are connected with two linearized rational interpolation problems at the roots of unity. These interpolation problems are solved by a superfast algorithm.