In the context of large-scale linear algebra, random sketching has emerged as a powerful technique to reduce computational costs and memory requirements. As data dimensions grow, traditional methods often become impractical. Random sketching provides a way to approximate large matrices and datasets by projecting them onto lower-dimensional subspaces using randomized linear maps, which capture essential properties of the original data –such as norms of vectors– but at a fraction of the size.

In this talk, we present the application of random sketching to Gram-Schmidt process for orthonormalizing a set of vectors. One [1] can provide a set of vectors, which are not \(l_2\) orthogonal but their low dimensional images through random sketching are orthonormal. Using this method, called randomized Gram-Schmidt (RGS) algorithm, for QR factorization of a matrix \(W\in \mathbb {R}^{n\times m}\) (with \(m\leq n\)), we obtain \(W=QR\), where \(Q\) is not orthonormal, but \(\Theta Q\) becomes orthonormal with a random sketching matrix \(\Theta \in \mathbb {R}^{t\times n}\) for \(t\ll n\). Furthermore, inspired by the reorthogonalization techniques in classical Gram-Schmidt (CGS) and modified Gram-Schmidt (MGS) (namely CGS2 and MGS2, respectively), we develop the RGS2 algorithm [2]. The RGS2 algorithm combines RGS with CGS/MGS to result improved numerical stability and \(l_2\) orthonormal \(Q\).

By employing fast computation techniques for sketching, such as fast Walsh Hadamard transformation, our RGS algorithms bring significant computational cost reductions. RGS has half the complexity of CGS/MGS, and RGS2 reduces computational costs by 25% compared to CGS2/MGS2. Furthermore, with the probabilistic rounding model, we analyze rounding errors and show that RGS exhibits better numerical stability than CGS and comparable stability to MGS. Additionally, under a numerical non-singularity condition, the loss of orthogonality in RGS2 is independent of the condition number of \(W\). Thus, the randomized orthogonalization process offers both reduced computational cost and enhanced numerical stability.

When solving linear systems with GMRES, the quality of Krylov basis vectors is crucial; poor quality can deteriorate GMRES convergence. To accelerate the convergence of GMRES, a deflation strategy is combined together. However, in GMRES with deflated restarting (GMRES-DR), where the previous Krylov subspace is reused, loss of orthogonality may accumulate over iterations, potentially leading to stagnation or divergence. Hence, the orthogonalizing process is particularly important in GMRES-DR. Here, RGS-based Arnoldi iterations can ensure numerical stability in generating Krylov basis vectors rather than other GS algorithms. Consequently, the randomized GMRES and the randomized GMRES-DR exhibit better numerical performance [3].

In this presentation, we introduce the randomized variants of FGMRES-DR, FGCRO-DR, SVD based deflation, and augmentation, (e.g., please refer to [4, 5, 6, 7] and the references therein for the GMRES methods with deflation and augmentation). To validate the stability and convergence improvements, we present numerical examples that solve ill-conditioned systems arising from compressible turbulent CFD simulations.

References

• [1]  Balabanov, Oleg, and Laura Grigori. “Randomized Gram–Schmidt process with application to GMRES.” SIAM Journal on Scientific Computing 44, no. 3 (2022): A1450-A1474.

• [2]  Jang, Yongseok, and Laura Grigori. “Randomized orthogonalization process with reorthogonalization.” HAL open science (2024).

• [3]  Jang, Yongseok, Laura Grigori, Emeric Martin, and Cédric Content. “Randomized flexible GMRES with deflated restarting.” Numerical Algorithms (2024): 1-35.

• [4]  Giraud, Luc, Serge Gratton, Xavier Pinel, and Xavier Vasseur. “Flexible GMRES with deflated restarting.” SIAM Journal on Scientific Computing 32, no. 4 (2010): 1858-1878.

• [5]  Parks, Michael L., Eric De Sturler, Greg Mackey, Duane D. Johnson, and Spandan Maiti. “Recycling Krylov subspaces for sequences of linear systems.” SIAM Journal on Scientific Computing 28, no. 5 (2006): 1651-1674.

• [6]  Daas, Hussam Al, Laura Grigori, Pascal Hénon, and Philippe Ricoux. “Recycling Krylov subspaces and truncating deflation subspaces for solving sequence of linear systems.” ACM Transactions on Mathematical Software (TOMS) 47, no. 2 (2021): 1-30.

• [7]  Soodhalter, Kirk M., Eric de Sturler, and Misha E. Kilmer. “A survey of subspace recycling iterative methods.” GAMM‐Mitteilungen 43, no. 4 (2020): e202000016.