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

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.

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

构造解大型稀疏线性方程组的快速高效算法在科学与工程计算中许多领域十分重要。数值算法通常可分为直接法和迭代法两类。直接法具有计算过程稳定、运算量可测、计算精度高等优点，但也存在运算量和存储开销大等问题。迭代法的优缺点则与直接法互反。结合系数矩阵的结构特点进而构造直接法或迭代法算法对问题求解至关重要。项目执行过程中，我们研究了系数矩阵带有位移结构的线性方程组的迭代解法，以及系数矩阵为拟三对角结构的线性方程组的直接法，同时也考虑了将解线性方程组的Krylov子空间法推广求解矩阵方程。矩阵特征值计算问题是科学与工程计算中遇到的另一重要研究课题。围道积分法是近些年备受关注的特征值算法之一。围道积分法计算过程需要多次解带位移结构及多右端项的线性方程组，由于线性方程组求解在整个计算过程占的时间开销比重最大，围道积分法能否有效解特征值问题的关键因素之一便是能否高效解这些线性方程组。因此，项目进行过程中，我们除了研究线性方程组的数值解法，还对计算特征值问题的围道积分法进行了研究和分析。