Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Randomized Gram-Schmidt process with application to GMRES

Oleg Balabanov 1 Laura Grigori 1
1 ALPINES - Algorithms and parallel tools for integrated numerical simulations
INSMI - Institut National des Sciences Mathématiques et de leurs Interactions, Inria de Paris, LJLL (UMR_7598) - Laboratoire Jacques-Louis Lions
Abstract : A randomized Gram-Schmidt algorithm is developed for orthonormalization of high-dimensional vectors or QR factorization. The proposed process can be less computationally expensive than the classical Gram-Schmidt process while being at least as numerically stable as the modified Gram-Schmidt process. Our approach is based on random sketching, which is a dimension reduction technique consisting in estimation of inner products of high-dimensional vectors by inner products of their small efficiently-computable random projections, so-called sketches. This allows to perform the projection step in Gram-Schmidt process on sketches rather than high-dimensional vectors with a minor computational cost. This also provides an ability to efficiently certify the output. The proposed Gram-Schmidt algorithm can provide computational cost reduction in any architecture. The benefit of random sketching can be amplified by exploiting multi-precision arithmetic. We provide stability analysis for multi-precision model with coarse unit roundoff for standard high-dimensional operations. Numerical stability is proven for the unit roundoff independent of the (high) dimension of the problem. The proposed Gram-Schmidt process can be applied to Arnoldi iteration and result in 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 of the methodology.
Complete list of metadata
Contributor : Oleg Balabanov Connect in order to contact the contributor
Submitted on : Sunday, January 3, 2021 - 11:28:24 PM
Last modification on : Friday, January 21, 2022 - 3:16:36 AM

Links full text


  • HAL Id : hal-03093492, version 1
  • ARXIV : 2011.05090


Oleg Balabanov, Laura Grigori. Randomized Gram-Schmidt process with application to GMRES. 2021. ⟨hal-03093492⟩



Les métriques sont temporairement indisponibles