TY - JOUR

T1 - Reorthogonalized block classical Gram-Schmidt

AU - Barlow, Jesse L.

AU - Smoktunowicz, Alicja

N1 - Funding Information:
The research of J. L. Barlow was sponsored by the National Science Foundation under contract no. CCF-1115704.

PY - 2013/3

Y1 - 2013/3

N2 - A reorthogonalized block classical Gram-Schmidt algorithm is proposed that factors a full column rank matrix A into A = QR where Q is left orthogonal (has orthonormal columns) and R is upper triangular and nonsingular. This block Gram-Schmidt algorithm can be implemented using matrix-matrix operations making it more efficient on modern architectures than orthogonal factorization algorithms based upon matrix-vector operations and purely vector operations. Gram-Schmidt orthogonal factorizations are important in the stable implementation of Krylov space methods such as GMRES and in approaches to modifying orthogonal factorizations when columns and rows are added or deleted from a matrix. With appropriate assumptions about the diagonal blocks of R, the algorithm, when implemented in floating point arithmetic with machine unit ε M, produces Q and R such that {double pipe}I - QT Q{double pipe} = O(εM) and {double pipe}A - QR{double pipe} = O(εM{double pipe}A{double pipe}). The first of these bounds has not been shown for a block Gram-Schmidt procedure before. As consequence of these results, we provide a different analysis, with a slightly different assumption, that re-establishes a bound of Giraud et al. (Num Math, 101(1):87-100, 2005) for the CGS2 algorithm.

AB - A reorthogonalized block classical Gram-Schmidt algorithm is proposed that factors a full column rank matrix A into A = QR where Q is left orthogonal (has orthonormal columns) and R is upper triangular and nonsingular. This block Gram-Schmidt algorithm can be implemented using matrix-matrix operations making it more efficient on modern architectures than orthogonal factorization algorithms based upon matrix-vector operations and purely vector operations. Gram-Schmidt orthogonal factorizations are important in the stable implementation of Krylov space methods such as GMRES and in approaches to modifying orthogonal factorizations when columns and rows are added or deleted from a matrix. With appropriate assumptions about the diagonal blocks of R, the algorithm, when implemented in floating point arithmetic with machine unit ε M, produces Q and R such that {double pipe}I - QT Q{double pipe} = O(εM) and {double pipe}A - QR{double pipe} = O(εM{double pipe}A{double pipe}). The first of these bounds has not been shown for a block Gram-Schmidt procedure before. As consequence of these results, we provide a different analysis, with a slightly different assumption, that re-establishes a bound of Giraud et al. (Num Math, 101(1):87-100, 2005) for the CGS2 algorithm.

UR - http://www.scopus.com/inward/record.url?scp=84873746310&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873746310&partnerID=8YFLogxK

U2 - 10.1007/s00211-012-0496-2

DO - 10.1007/s00211-012-0496-2

M3 - Article

AN - SCOPUS:84873746310

SN - 0029-599X

VL - 123

SP - 395

EP - 423

JO - Numerische Mathematik

JF - Numerische Mathematik

IS - 3

ER -