Fast block Toeplitz orthogonalization (Q911220)

Algorithms are presented which compute the QR factorization of a block- Toeplitz matrix in \(O(n^ 2)\) block-operations, where n is the block- order of the matrix and a block-operation is a multiplication, inversion or a set of Householder operations involving one or two blocks. The algorithms are in general analogous to those presented in the scalar Toeplitz case in a previous paper, but the basic operation is the Householder transform rather than the Givens transform, and the computation of the Householder coefficients and other working matrices requires special treatment. Two algorithms are presented - the first computes only R explicitly and the second computes both Q and R.