Fast Array Algorithms for Structured Matrices
Joohwan Chun · 1989
Many engineering or mathematical problems require to factorize structured matrices (Toeplitz, Hankel, Vandermonde, products of such matrices and their inverses, Schur complements, etc.) either in explicit or in disguised form. Consequently there exist various analytic tools regarding structured matrices as well as several factorization algorithms. In this thesis, we show that many of these results and several significant generalizations can be obtained in a very constructive way. The generic form is to use elementary circular and hyperbolic transformations to triangularize a certain array of numbers derived from the displacement representation of the given structured matrix; the desired results can then be read off from the resulting array. These fast array algorithms require $O$($mn$) operations for LU and QR factorizations of $m$ x $n$ structured matrices, and $O$($mn$) or even $O$($n$log$\sp2n$) operations for solving matrix equations. Also the array form suggests various alternative algorithms, depending upon the order in which the transformations are applied; these variations can have different numerical properties and lead to different implementations. Our algorithm is based on a generalized definition of displacement for block-Toeplitz (Hankel) and Toeplitz (Hankel)-block matrices slightly extending the previous definitions of Kailath, Kung and Morf (1979) and Lev-Ari and Kailath (1984). An important property of displacement structure is that it is preserved under Schur complementations. It will turn out that Toeplitz-(Hankel)-derived (near-Toeplitz, Toeplitz-like, etc.) matrices are perhaps best regarded as particular Schur complements obtained from suitably defined block matrices. The displacement structure is used to obtain a generalized Schur algorithm for the triangular and orthogonal factorizations of all such matrices, and well structured solutions of the corresponding exact and overdetermined systems of linear equations.