Efficient implementations of the modified Gram-Schmidt orthogonalization with a non-standard inner product

摘要

The modified Gram-Schmidt (MGS) orthogonalization is one of the most well-used algorithms for computing the thin QR factorization. MGS can be straightforwardly extended to a non-standard inner product with respect to a symmetric positive definite matrix A. For the thin QR factorization of an mxn matrix with the non-standard inner product, a naive implementation of MGS requires 2n matrix-vector multiplications (MV) with respect to A. In this paper, we propose n-MV implementations: a high accuracy (HA) type and a high performance type, of MGS. We also provide error bounds of the HA-type implementation. Numerical experiments and analysis indicate that the proposed implementations have competitive advantages over the naive implementation in terms of both computational cost and accuracy.