Fast Algorithms for Structured Matrices with Arbitrary Rank Profile

摘要

Triangular factorization, solution to linear equations, inversion, computation ofrank profile and inertia (in the Hermitian case) etc. of general n x n matrices require O(n cubed) operations. For certain structured matrices including Toeplitz and Hankel matrices, the computational complexity is known to be O(n squared) or better. These structured matrices often arise in a wide variety of areas including Signal processing, Systems theory, and Communications. Fast (i.e. O(n squared)) algorithms for these structured matrices have been actively studied for over twenty-five years. However almost all the authors have assumed that the underlying matrices are strongly regular, i.e. every principal submatrix is nonsingular. Although some fast algorithms have recently been developed for certain problems involving some of these structured matrices which may have one or more zero minors, several other problems are lacking. In this dissertation, we obtain several new results through a unified approach to the problems mentioned earlier.