Fast Triangular Factorization and Inversion of Hermitian, Toeplitz, and Related Matrices with Arbitrary Rank Profile
Debajyoti Pal, T. Kailath · SIAM Journal on Matrix Analysis and Applications · 1993
A fast procedure for computing a “modified” triangular factorization and inverse of Hermitian Toeplitz and quasi-Toeplitz (matrices congruent in a certain sense to Toeplitz matrices) matrices is presented. A modified triangular factorization is an $LDL^ * $ factorization where L is lower triangular with unit diagonal entries and D is a block diagonal matrix with possibly varying block sizes; only matrices with all leading minors nonzero, often called strongly regular, will always have a purely diagonal and nonsingular D matrix. For the matrices studied herein, the diagonal blocks also have a particular quasi-Toeplitz structure. The algorithms are obtained by extending a generating function approach of Lev-Ari and Kailath [Operator Theory: Adv. Appl.,18 (1986), pp. 301–324.] for matrices with a generalized displacement structure. A particular application of the result is a fast method of computing the rank profile and inertia of the matrices involved.