Randomized Orthogonalization Process With Reorthogonalization

ABSTRACT 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 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.