Multi precision randomized Gram-Schmidt algorithm with application to GMRES

In this talk we propose a randomized Gram-Schmidt algorithm for orthonormalization of high-dimensional vectors. This algorithm can have higher efficiency than the classical Gram-Schmidt process, and stability of the modified Gram-Schmidt process. Our approach is based on a dimension reduction technique, called random sketching. The benefit of random sketching can be amplified by performing the non-dominant operations in higher precision. The distinguishing feature of our algorithm in this case is the guarantee of numerical stability with the working unit roundoff independent of the dimension of the problem, which is proven by appealing to statistical properties of rounding errors. The proposed methodology yields new Krylov subspace methods for solving high-dimensional systems of equations or eigenvalue problems. Among them we chose randomized GMRES method as a practical application.