The GMRES algorithm of Saad and Schultz (1986) for nonsymmetric linear systems relies on the Arnoldi expansion of the Krylov basis. The algorithm computes the $QR$ factorization of the matrix $B = [\: {\bf r}_0, AV_k\:]$ at each iteration. Despite an $\mathcal{O}(\epsilon)\kappa(B)$ loss of orthogonality, the modified Gram-Schmidt (MGS) formulation was shown to be backward stable in the seminal papers by Paige, et al. (2006) and Paige and Strako\v{s} (2002). Classical Gram-Schmidt (CGS) exhibits an $\mathcal{O}(\epsilon)\kappa^2(B)$ loss of orthogonality, whereas DCGS-2 (CGS with delayed reorthogonalization) reduces this to $\mathcal{O}(\epsilon)$ in practice (without a formal proof). We present a post-modern (viz. not classical) GMRES algorithm based on Ruhe (1983) and the low-synch algorithms of \'{S}wirydowicz et al (2020) that achieves $\mathcal{O}(\epsilon) \: \|A{\bf v}_k\|_2 /h_{k+1,k}$ loss of orthogonality. By projecting the vector $A{\bf v}_k$, with Gauss-Seidel relaxation, onto the orthogonal complement of the space spanned by the computed Krylov vectors $V_k$ where $V_k^TV_k = I + L_k + L_k^T$, we can further demonstrate that the loss of orthogonality is at most $\mathcal{O}(\epsilon)\kappa(B)$. For a broad class of matrices, unlike MGS-GMRES, significant loss of orthogonality does not occur and the relative residual no longer stagnates for highly non-normal systems. The Krylov vectors remain linearly independent and the smallest singular value of $V_k$ is not far from one. We also demonstrate that Henrici's departure from normality of the lower triangular matrix $T_k \approx (\:V_k^TV_k\:)^{-1}$ in the modified Gram-Schmidt projector $P = I - V_kT_kV_k^T$ is an appropriate quantity for detecting the loss of orthogonality. Our new algorithm results in an almost symmetric correction matrix $T_k$.


翻译:saad 和 Schultz 的 GMRES 算法( 1986) 用于非对称线性系统的 Vlickr 值依赖于 Krylov 基质的 Arnoldi 扩展。 该算法计算基质 $B = [\:\ bf r ⁇ 0, AV_k\ :]$。 尽管有 $mathcal{O} (\ epsilon)\ knock 的损耗, 修改的 Gram- Schmidt (MGS) 配方在基质文件中显示向后稳定。 Kelov (2006) 和 Strako@v} (2002)。 经典 Gram- Smidt (C) 显示 $\ mathlickrickral=2 (b) 损耗耗值, 而 DCGS2 (x) 的损耗耗耗值是 ==xxxxxxal_ oral_ oralal_ oria_ oriax 。

0
下载
关闭预览

相关内容

自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
42+阅读 · 2022年6月30日
专知会员服务
123+阅读 · 2020年9月8日
专知会员服务
60+阅读 · 2020年3月19日
专知会员服务
159+阅读 · 2020年1月16日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2022年7月4日
Arxiv
0+阅读 · 2022年7月1日
VIP会员
相关VIP内容
自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
42+阅读 · 2022年6月30日
专知会员服务
123+阅读 · 2020年9月8日
专知会员服务
60+阅读 · 2020年3月19日
专知会员服务
159+阅读 · 2020年1月16日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
相关基金
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员