Computations with Gohberg-Semencul-type formulas for Toeplitz matrices

The inverse of a Toeplitz matrix T_n can be represented in different ways by Gohberg-Semencul-type formulas as the sum of products of upper and lower triangular Toeplitz matrices. If we have given such a formula, we can solve every equation T_nx = b in O(n log n) steps. There are three main questions arising with such representations of T^-1_n: (1) which special linear equations can be solved in order to get generating vectors for Gohberg-Semencul-type formulas, (2) which algorithm we want to apply to solve these questions, and (3) which special Gohberg-Semencul-type formula we want to use for evaluating T^-1_nb. In this paper we present an elementary approach to derive all Gohberg-Semencul-type formulas. Then we introduce representations of T^-1_n with special properties. In particular we prove that there exists a Gohberg-Semencul-type formula such that the generating vectors are pairwise orthogonal. Finally, based on the previous results, we give new fast and stable algorithms for solving linear Toeplitz systems that can be used to compute generating vectors for Gohberg-Semencul-type formulas. In the case of a breakdown or near-breakdown in the kth step, the new method introduces a perturbation in the kth entry t_k of T_n such that the perturbed submatrix T̂_k is well conditioned. By using the Sherman-Morrison-Woodbury formula it is possible to recover the original problem as soon as the corresponding submatrix T_k+r is again nonsingular.