Randomized Orthogonalization Process With Reorthogonalization

The dimension reduction technique of random sketching is advantageous in significantly reducing computational complexity. In orthogonalization processes like the Gram-Schmidt (GS) algorithm, incorporating random sketching results in a halving of computational costs compared to the classical/modified Gram-Schmidt (CGS/MGS) algorithms, while maintaining numerical stability comparable to the MGS algorithm. The randomized Gram-Schmidt (RGS) algorithm produces a set of sketched orthonormal vectors, and the loss of orthogonality in these vectors is linearly dependent on the condition number of the given matrix. We propose a new variant, RGS-L2, with reorthogonalization to obtain a set of (Formula presented.) orthonormal vectors. A round-off error analysis demonstrates that the loss of orthogonality is close to the unit round-off level. Numerical experiments exhibit the benefits of our proposed algorithm. Furthermore, we apply the RGS-L2 algorithm to the Generalized Minimal Residual Method (GMRES) and compare its numerical performance with other GMRES variants.