Fast Algorithms for Structured Matrices with Arbitrary Rank Profile
Abstract
Triangular factorization, solution to linear equations, inversion, computation of rank 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 is lacking. In this dissertation, we obtain several new results through a unified approach to the problems mentioned earlier.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1990
- Accession Number
- ADA238975
Entities
People
- Debajoyti Pal
Organizations
- Stanford University