Numerics of Gram-Schmidt orthogonalization

AbstractThe Gram-Schmidt (GS) orthogonalization is one of the fundamental procedures in linear algebra. In matrix terms it is equivalent to the factorization AQ1R, where Q1∈Rm×n with orthonormal columns and R upper triangular. For the numerical GS factorization of a matrix A two different versions exist, usually called classical and modified Gram-Schmidt (CGS and MGS). Although mathematically equivalent, these have very different numerical properties. This paper surveys the numerical properties of CGS and MGS. A key observation is that MGS is numerically equivalent to Householder QR factorization of the matrix A augmented by an n×n zero matrix on top. This can be used to derive bounds on the loss of orthogonality in MGS, and to develop a backward-stable algorithm based on MGS. The use of reorthogonalization and iterated CGS and MGS algorithms are discussed. Finally, block versions of GS are described