Reorthogonalized Block Classical Gram–Schmidt Using Two Cholesky-Based TSQR Algorithms
Jesse L. Barlow · SIAM Journal on Matrix Analysis and Applications · 2024
Abstract. In [ Numer. Math., 23 (2013), pp. 395–423], Barlow and Smoktunowicz propose the reorthogonalized block classical Gram–Schmidt algorithm BCGS2. New conditions for the backward stability of BCGS2 that allow the use of a more flexible version of that algorithm are given. Backward stability for BCGS2 means that, in floating point arithmetic with machine precision [Formula: see text], for a full column rank [Formula: see text], the algorithm produces [Formula: see text] and upper triangular [Formula: see text] such that [Formula: see text] and [Formula: see text]. However, each major step of BCGS2 requires the QR factorization of two intermediate [Formula: see text] matrices [Formula: see text] and [Formula: see text]. In many applications of interest [Formula: see text], thus these factorizations are called “tall, skinny” QR (TSQR) operations. Each such factorization was assumed to produce [Formula: see text], such that [Formula: see text] and [Formula: see text]. For this suboperation, the first of these two conditions limits the choice of QR factorization algorithms to those, such as Householder and Givens QR, which may not produce the [Formula: see text] as efficiently as some with weaker orthogonality restrictions. For the second of these QR factorizations, it is shown that the Cholesky decomposition of [Formula: see text] followed by the [Formula: see text] can be substituted without a significant change in the conditions for backward stability. With slightly stronger restrictions, the first QR decomposition can be done by algorithms such as the mixed precision CholQR algorithm described by Yamazaki, Tomov, and Dongarra [ SIAM J. Sci. Comput., 37 (2015), pp. C307–C330]. In a GPU/CPU environment, Yamazaki, Tomov, and Dongarra showed that algorithm to be a very efficient method of producing the TSQR. Given that a common application of Gram–Schmidt algorithms is in the implementation of Krylov subspace methods, such as block GMRES, these results make the BCGS2 algorithm more broadly applicable.