Fast Array Algorithms for Structured Matrices
Rept. for 1989-1990,
STANFORD UNIV CA DEPT OF ELECTRICAL ENGINEERING
Pagination or Media Count:
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 Omn or even On 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.
- Numerical Mathematics