Journal
NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS
Volume 28, Issue 2, Pages -Publisher
WILEY
DOI: 10.1002/nla.2343
Keywords
Graphics processing unit; Gram– Schmidt process; Krylov methods; massively parallel; scalable GMRES; WY factorization
Categories
Funding
- Exascale Computing Project [17-SC-20-SC]
- U.S. Department of Energy [DE-AC36-08GO28308, DE-AC52-07NA27344]
- NSF [1645514]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1645514] Funding Source: National Science Foundation
Ask authors/readers for more resources
The Gram-Schmidt process uses orthogonal projection to construct the QR factorization of a matrix, and approximate projections with form P = I - QTQ(T) can improve orthogonality. New variants of modified Gram-Schmidt algorithms introduce a compact WY representation.
The Gram-Schmidt process uses orthogonal projection to construct the A = QR factorization of a matrix. When Q has linearly independent columns, the operator P = I - Q(Q(T)Q)(-1)Q(T) defines an orthogonal projection onto Q(perpendicular to). In finite precision, Q loses orthogonality as the factorization progresses. A family of approximate projections is derived with the form P = I - QTQ(T), with correction matrix T. When T = (Q(T)Q)(-1), and T is triangular, it is postulated that the best achievable orthogonality is O(epsilon)kappa(A). We present new variants of modified (MGS) and classical Gram-Schmidt algorithms that require one global reduction step. An interesting form of the projector leads to a compact WY representation for MGS. In particular, the inverse compact WY MGS algorithm is equivalent to a lower triangular solve. Our main contribution is to introduce a backward normalization lag into the compact WY representation, resulting in a O(epsilon)kappa([r0,AVm]) stable Generalized Minimal Residual Method (GMRES) algorithm that requires only one global reduce per iteration. Further improvements in performance are achieved by accelerating GMRES on GPUs.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available