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

The paper presents fast triangular factorization algorithms \([O(n^ 2)]\) for matrices close to Toeplitz plus Hankel, and in particular for quasi- Toeplitz, quasi-Hankel, and Toeplitz-plus-Hankel matrices. Both Hermitian and non-Hermitian matrices are considered. 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 close relation to the Schur reduction for triangular factorization. It is an extension from the Hermitian case presented by the second and third author [Oper. Theory Adv. Appl. 18, 301-324 (1986; Zbl 0593.47015)] to the non-Hermitian case of the generating function approach inclusive structured non-Hermitian matrices. Various special cases covering displacement rank from two to eight are considered. The result includes many special cases studied separately, for instance factorization of the inverse matrix, solution of exact and overdetermined linear systems which can be reduced to the direct factorization problem.