Fast triangular factorization of the sum of quasi-Toeplitz and quasi-Hankel matrices

The literature contains several recent fast algorithms for the triangular factorization of strongly regular Toeplitz-plus-Hankel matrices. In this paper we study the rather more general sum of quasi-Toeplitz and quasi-Hankel matrices, both Hermitian and non-Hermitian. Quasi-Toeplitz and quasi-Hankel matrices are those that are congruent to Toeplitz and Hankel matrices in a special sense. The derivation is based on the concept of displacement structure and its intimate relation to the Schur reduction procedure for triangular factorization. Various special cases covering displacement ranks from two to eight are considered. Several other problems (e.g., factorization of the inverse matrix, solution of exact or overdetermined linear systems) can be reduced to the direct factorization problem.