Qr factorization revisited

A general framework capturing known QR factorization methods is presented. A relationship between the major classes of methods leads to a new, efficient and accurate method for computing the Cholesky decomposition of ( I − qqT). Incorporating the new Cholesky decomposition into an accurate QR factorization algorithm is expressed as a splitting of orthogonal Hessenberg matrices. Computation is further optimized by introducing a new factorization for orthogonal Hessenberg matrices called DST factorization. A QR algorithm based on DST factorization is presented that has accuracy comparable to Householder transformations, the flexibility of Givens rotations and the lowest operation count of known methods. Also, it has provable bounds on the computation. Results from computing the QR factorization of several ill-conditioned and rank deficient matrices are presented.