GENERALIZED DISPLACEMENT STRUCTURE FOR BLOCK-TOEPLITZ, TOEPLITZ-BLOCK, AND TOEPLITZ-DERIVED MATRICES

The concept of displacement structure has been used to solve several p roblems connected with Toeplitz matrices and with matrices obtained in some way from Toeplitz matrices (e.g., by combinations of multiplicat ion, inversion, and factorization). Matrices of the latter type will b e called Toeplitz-derived (or Toeplitz-like, close-to-Toeplitz). This paper introduces a generalized definition of displacement for block-To eplitz and Toeplitz-block arrays. It will turn out that Toeplitz-deriv ed matrices are perhaps best regarded as particular Schur complements obtained from suitably defined block matrices. The new displacement st ructure is used to obtain a generalized Schur algorithm for fast trian gular and orthogonal factorizations of all such matrices and well-stru ctured fast solutions of the corresponding exact and overdetermined sy stems of linear equations. Furthermore, this approach gives a natural generalization of the so-called Gohberg-Semencul formulas for Toeplitz -derived matrices.