Superfast solution of Toeplitz-like systems

In this paper a new O(N log3 N) solver for N £ N Toeplitz-like sys- tems, based on a divide and conquer technique, is presented. Similarly to the superfast algorithm MBA for the inversion of a Toeplitz-like matrix [2, 16], 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. The same idea has been used in [19] to improve the numerical stability of superfast meth- ods based on the generalized Schur algorithm for positive de¯nite Toeplitz matrices, but the algorithm we propose can be applied also to nonsym- metric Toeplitz-like systems. The stability of the algorithm is examined through numerical experiments.