Unitary k-Hessenberg Matrices

In 1971, Householder and Fox [26] introduced a method for computing an orthonormal basis for the range of a projection. Using a Cholesky decompo- sition on a symmetric idempotent matrix A produced A = LL T , where the columns of the lower triangular matrix L form said basis. Moler and Stewart [32] performed an error analysis on the Householder-Fox algorithm in 1978. It was shown that in most cases reasonable results can be expected, however a recent paper by Parlett and Barszcz [36] included a numerical experiment by Kahan in which the Householder-Fox method performed poorly. Parlett proposed an alternate method which focused on exploiting the structure of the n×n projection I−qq T . In the case where the Householder-Fox algorithm produced an error of 1, this new method produced full accuracy. In what fol- lows, additional algorithms will be introduced, exploiting the decomposable, Green’s (H,1)-quasiseparable and Green’s (H,1)-semiseparable structure of unitary Hessenberg matrices. It will be shown that the more general and newly defined unitary k-Hessenberg matrices also have a great deal of struc- ture, and further, that the structure exploiting algorithms mentioned above are readily generalizable to this new unitary k-Hessenberg case