In this paper a new O(N log3 N ) solver for N × N Toeplitz-like systems, based on a divide and conquer technique, is presented. Similarly to the superfast algorithm MBA for the inversion of a Toeplitz-like matrix [3, 18], it exploits the displacement properties. In order to avoid the well known numerical instability of the explicit inversion, the new algorithm relies on the triangular factorization and back-substitution formula for the system seen as a 2 × 2 block system with blocks of half size. This idea is the same one used in  to improve the numerical stability of superfast methods based on the generalized Schur algorithm for positive deﬁnite Toeplitz matrices, but the algorithm we propose can be applied also to nonsymmetric Toeplitz-like systems. The stability of the algorithm is examined through numerical experiments.
A divide and conquer algorithm for the superfast solution of Toeplitz-like systems / Favati, P; Lotti, Grazia; Menchi, O.. - In: SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS. - ISSN 0895-4798. - 33-34:(2012), pp. 1039-1056. [10.1137/110851407]