Randomized block Gram-Schmidt process for solution of linear systems and eigenvalue problems - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Randomized block Gram-Schmidt process for solution of linear systems and eigenvalue problems

(1) , (1)
1

Abstract

We propose a block version of the randomized Gram-Schmidt process for computing a QR factorization of a matrix. Our algorithm inherits the major properties of its single-vector analogue from [Balabanov and Grigori, 2020] such as higher efficiency than the classical Gram-Schmidt algorithm and stability of the modified Gram-Schmidt algorithm, which can be refined even further by using multi-precision arithmetic. As in [Balabanov and Grigori, 2020], our algorithm has an advantage of performing standard high-dimensional operations, that define the overall computational cost, with a unit roundoff independent of the dominant dimension of the matrix. This unique feature makes the methodology especially useful for large-scale problems computed on low-precision arithmetic architectures. Block algorithms are advantageous in terms of performance as they are mainly based on cache-friendly matrix-wise operations, and can reduce communication cost in high-performance computing. The block Gram-Schmidt orthogonalization is the key element in the block Arnoldi procedure for the construction of Krylov basis, which in its turn is used in GMRES and Rayleigh-Ritz methods for the solution of linear systems and clustered eigenvalue problems. In this article, we develop randomized versions of these methods, based on the proposed randomized Gram-Schmidt algorithm, and validate them on nontrivial numerical examples.
Fichier principal
Vignette du fichier
RBGS_balabanov_grigori.pdf (540.72 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03469555 , version 1 (07-12-2021)

Identifiers

Cite

Oleg Balabanov, Laura Grigori. Randomized block Gram-Schmidt process for solution of linear systems and eigenvalue problems. 2021. ⟨hal-03469555⟩
93 View
82 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More