Fast Array Algorithms for Structured Matrices

Abstract
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 fast 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 genetic 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 square n) 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.

This publication has 0 references indexed in Scilit: