Block modified gram-Schmidt algorithms and their analysis

New block modified Gram-Schmidt (BMGS) methods for the Q-R factorization of a full column rank matrix XAbstract. New block modifed Gram-Schmidt (BMGS) methods for the Q-R factorization of a full column rank matrix X ∈ Rm×n, m ≥ n, are considered. Such methods factor X into Q ∈ Rm×n and an upper triangular R ∈ Rm×n such that X = QR, where, in exact arithmetic, Q is left orthogonal (i.e., QT Q = In). Gram-Schmidt-based algorithms play an important role in the implementation of Krylov space methods, such as GMRES, Arnoldi, and Lanczos. For these applications, the left orthogonal factor Q is needed and the matrix is produced either one column at a time or one block of columns at a time. For block implementations of Krylov methods, a block of columns of X is introduced at each step, and a new block of columns of Q must then be produced. That is a task for which BMGS methods are ideally suited. However, for these Krylov methods to converge properly, the BMGS algorithms need to have numerical behavior that is similar to that of modifed Gram-Schmidt. To design such BMGS algorithms, we build upon the block Householder representation of Schreiber and Van Loan [SIAM J. Sci. Stat. Comput., 10 (1989), pp. 53-57] and an observation by Charles Shefeld analyzed by Paige [SIAM J. Matrix Anal. Appl., 31 (2009), pp. 565-583] about the relationship between modifed Gram-Schmidt and Householder Q-R factorization. Our new BMGS algorithms exploit the Shefeld framework so that they share a similar relationship to Householder Q-R and thus have error analysis properties similar to modifed Gram-Schmidt. The last BMGS algorithm developed is based entirely upon matrix multiplications and the `tall, skinny" Q-R (TSQR) factorization-two operations that have been studied extensively for cache-based architectures and distributed architectures. It is shown that if the TSQR part of the BMGS algorithm satisfes error analysis properties connected to the Shefeld structure, then so does the entire BMGS algorithm. Thus new criteria for when a BMGS algorithm has error analysis properties similar to those of MGS are proposed.