Displacement structure for Hankel, Vandermonde, and related (derived) matrices (Q803726)

The Toeplitz displacement rank of a matrix A with respect to \(\{F^ f,F^ b\}\) is the rank of \(A-F^ fAF^{bT}.\) This generalizes the more restricted notion for square matrices \(F^ f=F^ b=Z_ n\), the \(n\times n\) lower shift matrix with ones on the first subdiagonal and zeros everywhere else, which has been studied by the second author [Proc. Symp. Appl. Math. 37, 71-109 (1987; Zbl 0644.94005)]. A matrix is ``close-to-Toeplitz'' if it has a displacement rank (with respect to some \(\{F^ f,F^ b\})\) which is independent of its size. ``Close-to-Hankel'' matrices are defined along similar lines. Both types are referred to as ``structured matrices'', a property which is preserved under inversion multiplication and Schur complementation. The Hankel displacement of A is \(\Delta_{(F^ f,F^ b)}A=F^ fA- AF^{bT}\). This notion may be used in the triangularization of A. For the case that A is Vandermonde matrix, the authors obtain a fast triangular factorization algorithm. Algorithms are also obtained for triangular factorization of Vandermonde inverses, ``close-to-Hankel'' matrices and their inverses. For similar results for close-to-Toeplitz matrices and Toeplitz displacements the reader is referred to the authors [Numerical linear algebra, digital signal processing and parallel algorithms, Proc. NATO ASI, Leuven/Belg. 1988, NATO ASI Ser. Ser. F70, 215-236 (1991)]. No discussion on the numerical stability properties of the resulting algorithms is offered.