Reorthogonalized block classical Gram-Schmidt (Q1939650)

A block classical Gram-Schmidt algorithm with reorthogonalization for computing a \(QR\) decomposition of a matrix \(A \in \mathbb R^{m \times n}\), \(m \geq n\), is proposed, where \(Q \in \mathbb R^{m \times n}\) with \(Q^TQ = I_n\) and \(R \in \mathbb R^{n \times n}\) is an upper triangular matrix. The presented algorithm works with groups of columns of the matrix \(A\) instead with columns of \(A\). Therefore, matrix-matrix-operations instead of matrix-vector-operations or vector operations are necessary in the algorithm. This can lead to more efficient implementations on modern computer architectures. The presented algorithm is a generalization of the classical Gram-Schmidt method with reorthogonalization (see, e.g. [\textit{N.~N.~Abdelmalek}, BIT, Nord. Tidskr. Inf.-behandl. 11, 345--367 (1971; Zbl 0236.65031)]). Under appropriate assumptions on the diagonal blocks of the matrix \(R\), it is proved that the presented algorithm is numerically stable, more precisely, the following estimates are proved: \(\| I_n - Q^TQ \| = O(\varepsilon_M)\) and \(\| A - QR \| = O(\varepsilon_M \| A \|)\), where \(\varepsilon_M\) is the machine unit.