A Numerically Stable Communication-Avoiding \({s}\)-Step GMRES Algorithm

作者：Zan Xu, Juan Jose Alonso, Eric Darve · 发表于：SIAM Journal on Matrix Analysis and Applications · 年份：2024 · DOI：10.1137/23m1577109 · 被引用次数：10 · 研究领域：Advanced Adaptive Filtering Techniques、Matrix Theory and Algorithms、Sparse and Compressive Sensing Techniques

Abstract. Krylov subspace methods are extensively used in scientific computing to solve large-scale linear systems. However, the performance of these iterative Krylov solvers on modern supercomputers is limited by expensive communication costs. The [Formula: see text]-step strategy generates a series of [Formula: see text] Krylov vectors at a time to avoid communication. Asymptotically, the [Formula: see text]-step approach can reduce communication latency by a factor of [Formula: see text]. Unfortunately, due to finite-precision implementation, the step size has to be kept small for stability. In this work, we tackle the numerical instabilities encountered in the [Formula: see text]-step GMRES algorithm. By choosing an appropriate polynomial basis and block orthogonalization schemes, we construct a communication-avoiding [Formula: see text]-step GMRES algorithm that automatically selects the optimal step size to ensure numerical stability. To further maximize communication savings, we introduce scaled Newton polynomials that can increase the step size [Formula: see text] to a few hundreds for many problems. An initial step size estimator is also developed to efficiently choose the optimal step size for stability. The guaranteed stability of the proposed algorithm is demonstrated using numerical experiments. In the process, we also evaluate how the choice of polynomial and preconditioning affects the stability limit of the algorithm. Finally, we show parallel scalability on m...