大型稀疏非对称线性方程组的归纳降维算法研究

项目名称： 大型稀疏非对称线性方程组的归纳降维算法研究

项目编号： No.11501079

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 杜磊

作者单位： 大连理工大学

项目金额： 18万元

中文摘要： 归纳降维法是一类求解非对称线性方程组的迭代法，其代表性算法为IDR(s)。相比于大多乘积型Krylov子空间法，归纳降维法更具竞争性，且s>1时IDR(s)计算性能优于稳定双共轭梯度法(BiCGSTAB)。近年，尽管归纳降维法已被广泛关注，无论在算法设计还是理论分析方面都取得不少研究成果，但是针对不同类型的线性方程组仍有许多问题有待进一步的研究。在本项目中，我们拟针对单右端、多右端及多右端位移线性方程组研究归纳降维算法。我们将研究广义归纳降维定理和影子向量的选取，给出求解单右端线性方程组的改良归纳降维算法。我们拟将块Krylov子空间法的技术和已发展的归纳降维算法推广，并讨论单双精度混合运算技术，构造求解多右端线性方程组的高效块归纳降维算法。我们还将研究块Sonneveld空间的位移不变性和残量矩阵共线性，设计种子方程切换策略，构造求解多右端位移线性方程组的高效位移块归纳降维算法。

中文关键词： 归纳降维法；线性方程组；多右端；混合精度；位移线性方程组

英文摘要： Induced dimension reduction methods are proposed as iterative methods for solving nonsymmetric linear systems, and the representative algorithm is IDR(s). Compared to most product-type Krylov subspace methods, Induced dimension reduction methods are very competitive, and IDR(s) outperforms the biconjugate gradient stabilized method (BiCGSTAB) when s>1. In recent years, induced dimension reduction methods have gained considerable attention, many research results of algorithm design and theoretical analyses have been obtained, but there are still many issues that need further research for different kinds of linear systems. In this project, we will study induced dimension reduction methods for solving linear systems with single right-hand side, multiple right-hand sides, multiple right-hand sides and multiple shifts. We will study the generalized induced dimension reduction theorem and the selection of shadow vectors, then propose an improved induced dimension reduction algorithm for solving linear systems with single right-hand side. We will extend techniques of block Krylov subspace methods and induced dimension reduction methods, discuss operations in single-double mixed precision, then construct efficient block induced dimension reduction algorithms for solving linear systems with multiple right-hand sides. We will also study the shift-invariance property of block Sonneveld spaces and collinearity of residual matrices, devise seed switching techniques, then construct efficient shifted block induced dimension reduction algorithms for solving linear systems with multiple right-hand sides and multiple shifts.

英文关键词： Induced dimension reduction methods;Linear systems;Multiple right-hand sides;Mixed precision;Shifted linear systems