.png){kind=icon}
返回
RANDOMIZED GRAM-SCHMIDT PROCESS WITH APPLICATION TO GMRES
.png){kind=icon}
OA
AI
DOI：10.1137/20M138870X.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 images, so-called sketches. In this way, an approximate orthogonality of the full vectors can be obtained by orthogonalization of their sketches. The proposed Gram-Schmidt algorithm can provide computational cost reduction in any architecture. The benefit of random sketching can be amplified by performing the nondominant operations in higher precision. In this case the numerical stability can be guaranteed with a working unit roundoff independent of the dimension of the problem. The proposed Gram-Schmidt process can be applied to Arnoldi iteration and results in new Krylov subspace methods for solving high-dimensional systems of equations or eigenvalue problems. Among them we chose the randomized GMRES method as a practical application of the methodology.
Keyword:
Gram-Schmidt orthogonalization
QR factorization
randomization
random sketching
numerical stability
rounding errors
loss of orthogonality
multiprecision arithmetic
Krylov subspace methods
Arnoldi iteration
generalized minimal residual method
期刊
IF:
2.6
论文数:
5.1K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏分享收藏
查看更多内容