The GMRES algorithm of Saad and Schultz (1986) is an iterative method for approximately solving linear systems $A{\bf x}={\bf b}$, with initial guess ${\bf x}_0$ and residual ${\bf r}_0 = {\bf b} - A{\bf x}_0$. The algorithm employs the Arnoldi process to generate the Krylov basis vectors (the columns of $V_k$). It is well known that this process can be viewed as a $QR$ factorization of the matrix $B_k = [\: {\bf r}_0, AV_k\:]$ at each iteration. Despite an ${O}(\epsilon)\kappa(B_k)$ loss of orthogonality, for unit roundoff $\epsilon$ and condition number $\kappa$, the modified Gram-Schmidt formulation was shown to be backward stable in the seminal paper by Paige et al. (2006). We present an iterated Gauss-Seidel formulation of the GMRES algorithm (IGS-GMRES) based on the ideas of Ruhe (1983) and \'{S}wirydowicz et al. (2020). IGS-GMRES maintains orthogonality to the level ${O}(\epsilon)\kappa(B_k)$ or ${O}(\epsilon)$, depending on the choice of one or two iterations; for two Gauss-Seidel iterations, the computed Krylov basis vectors remain orthogonal to working precision and the smallest singular value of $V_k$ remains close to one. The resulting GMRES method is thus backward stable. We show that IGS-GMRES can be implemented with only a single synchronization point per iteration, making it relevant to large-scale parallel computing environments. We also demonstrate that, unlike MGS-GMRES, in IGS-GMRES the relative Arnoldi residual corresponding to the computed approximate solution no longer stagnates above machine precision even for highly non-normal systems.


翻译:Saad和Schultz(1986)的GMRES算法是用于近似解线性系统$A{\bf x}={\bf b}$的迭代方法,其中${\bf x}_0$是初始猜测,${\bf r}_0={\bf b}-A{\bf x}_0$是残差。该算法利用Arnoldi过程生成Krylov基向量($V_k$的列)。众所周知,这一过程可以被视为每次迭代矩阵$B_k=[{\bf r}_0,AV_k]$的$QR$分解。尽管存在一个${O}(\epsilon)\kappa(B_k)$的正交性缺失,单位舍入$\epsilon$和条件数$\kappa$,但局部修正Gram-Schmidt公式在Paige等人(2006)的开创性论文中被证明是向后稳定的。我们提出了GMRES算法的迭代Gauss-Seidel公式(IGS-GMRES),基于Ruhe(1983)和Świrydowicz等人(2020)的思想。IGS-GMRES在${O}(\epsilon)\kappa(B_k)$或${O}(\epsilon)$的级别维持正交性,具体取决于选择一次或两次迭代;对于两个Gauss-Seidel迭代,计算的Krylov基向量保持正交到工作精度,而$V_k$的最小奇异值保持接近1。因此,得到的GMRES方法是向后稳定的。我们展示了IGS-GMRES每次迭代仅需要一个同步点即可实现,使其与大规模并行计算环境相关。我们还证明,与MGS-GMRES不同,在IGS-GMRES中,对应于计算近似解的相对Arnoldi残差即使对于高度非正常的系统也不再停滞在机器精度之上。

0
下载
关闭预览

相关内容

粗粒化分子构象生成
专知会员服务
9+阅读 · 2022年9月18日
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
【硬核书】树与网络上的概率,716页pdf
专知会员服务
72+阅读 · 2021年12月8日
专知会员服务
31+阅读 · 2021年6月12日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
42+阅读 · 2020年7月7日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
上百份文字的检测与识别资源,包含数据集、code和paper
数据挖掘入门与实战
17+阅读 · 2017年12月7日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
3+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月11日
Arxiv
0+阅读 · 2023年5月11日
Arxiv
0+阅读 · 2023年5月10日
Arxiv
0+阅读 · 2023年5月9日
VIP会员
相关VIP内容
粗粒化分子构象生成
专知会员服务
9+阅读 · 2022年9月18日
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
73+阅读 · 2022年6月28日
【硬核书】树与网络上的概率,716页pdf
专知会员服务
72+阅读 · 2021年12月8日
专知会员服务
31+阅读 · 2021年6月12日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
42+阅读 · 2020年7月7日
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
上百份文字的检测与识别资源,包含数据集、code和paper
数据挖掘入门与实战
17+阅读 · 2017年12月7日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关基金
国家自然科学基金
3+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
1+阅读 · 2008年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员