Classical Vadermonde matrices can be traced back to the 18th century; their properties were first used by Alexandre-Theophile Vandermonde. Since then they have been arising in quite diverse problems in mathematics and engineering. In 1966 Traub designed the first fast algorithm for inversion of Vandermonde matrices. His algorithm requires only O(n) operations to invert an n x n matrix, which compares favorably with the cost of standard inversion methods.

Since then several dozens of papers were devoted to inversion of matrices generalizing Vandermonde matrices. These generalizations can be roughly divided into two categories. The first direction deals with replacing monomials used in the classical Vandermonde Sirani K. Mututhanthrige Perera - University of Connecticut - 2012 matrices by the more general polynomials, such as orthogonal polynomials, Szego polynomials, etc. In the first chapter of this thesis we pursue research in this first direction. We design fast algorithms to invert the so-called Laurent Vandermonde matrices defined using the concept of displacement structure. Let us say a few more words about this. Perhaps the first example of quasiseparable structure was an oscillation matrix studied by Gantmacher and Krein in 1940 [GK02]. However, intensive investigation of quasiseparable matrices began in only 1990's. Hence, it is not surprising that currently only one monograph [VVGM05] contains a survey of relevant results. To our knowledge, two more monographs are in preparation. Quasiseparable matrices arise in many applications in linear system theory, control theory, statistics, mechanics, and others. This explains why quasiseparable matrices have been among the hottest research topics in Numerical Linear Algebra in the last decade. In particular, quasiseparable structure was used to define new quasiseparable Laurent polynomials that generalize classical Laurent polynomials orthogonal on the unit circle (and in particular the classical Szego polynomials). In the first chapter we derive the most generalized inversion formula for the Laurent Vandermonde matrices as well as a fast inversion algorithm.

The second direction in generalizing the classical Traub algorithm is via defining the more general classes of matrices using the concept of displacement structure. We use Sirani K. Mututhanthrige Perera - University of Connecticut - 2012 the latter concept to introduce a new fairly general class of matrices called quasiseparable Vandermonde-like matrices, and design a fast inversion algorithm.

Finally, in the last chapter we focus on discrete sine transformations that can also be related to the so-called Chebyshev-Vandermonde structure. Currently, there are no papers addressing the numerical stability of DST algorithms. Moreover, the existing DST algorithms, though fast and recursive, are not based on orthogonal factors, and are unstable. In the third chapter we derive fast, recursive and numerically stable algorithms for discrete sine transformations based on orthogonal factors.