《大型稀疏线性系统的高性能算法研究》

该成果在国家自然科学基金“一类大规模稀疏复对称线性方程组的高效算法与理论研究(11301009)”和“特殊鞍点问题的高效预处理技术及在电磁计算中的应用研究(11501525)”的支持下,采用“算法分析-数值试验-方法创新-成果应用”等反复循环研究手段,针对大规模线性系统设计了高性能迭代算法,并将所得成果应用于实际问题的数值模拟,提高模拟的整体效率。该成果具有以下五个方面重要科学发现:

1.针对工程和科学计算中的很多重要领域,如计算流体力学、石油勘探、计算电磁学等实际问题数值模拟离散得到的一类复对称线性方程组,当实部为奇异时,得到了MHSS算法半收敛更一般结论;当实部为正半定时,设计了一类改进的斜正规分裂和斜尺度化分裂算法,理论分析表明两种方法均是无条件收敛;为进一步提高收敛速度,设计了非精确版本MSNS(MSSS)算法,数值实验表明了所提算法的有效性;当实部为正定时,设计了一类双参数广义PMHSS算法作用于Helmholtz方程;进一步设计了双参数双预处理子广义PMHSS算法和一类单步HSS算法,数值实例验证了单步HSS算法在一定条件下优于HSS算法;当实部为不定时,设计了HNS算法及其简化版本,数值实例验证了新算法的有效性。

2.进一步将此类复对称线性方程组转化为等价2乘2块结构状态-空间型线性方程组,利用矩阵的复对称及斜Hermitian分裂,建立了一类CSS算法和一种修正CSS算法,并分析了其收敛条件和最优参数选取;构建了含参数不定块三角预处理子、正定块对角预处理子和不定块对角预处理子,作用于其等价实线性方程组,理论分析和数值实验均表明,当参数选取0.5时,含参数不定块三角预处理子结合Krylov子空间算法的求解速度达到最优;设计了Picard-LMHSS算法及非线性LMHSS-like算法;将等价2乘2块线性方程组研究成果拓展到鞍点问题,给出了HSS预处理矩阵复特征值新的一些估计。

3.针对大型稀疏线性方程组,通过降低整体同步化点和算法重构,设计了适合分布式并行计算改进的广义平方共轭残差算法和并行广义全局平方共轭梯度算法,新算法使所有内积计算及矩阵向量乘是独立的,并分析了算法的收敛性、复杂度、并行性和等效率等,解决了迭代方法并行计算的瓶颈问题。

4.对离散时谐Maxwell方程得到的鞍点问题,首次提出了两类最优免增广免Schur补预处理子,并克服了已有块对角预处理子只能解决波数小于1的缺陷;给出了求解(2,2)块不为零的非对称广义鞍点问题GMLHSS算法,理论分析其收敛条件,给出了非精确Uzawa算法、GSSOR算法和MLHS算法求解奇异鞍点问题时的半收敛性分析。

5.针对大型稀疏线性互补问题,采用矩阵分裂技巧、松弛外推迭代技术和加速思想,设计了模系同步多分裂多参数迭代算法和带阻尼因子的重叠限制加法Schwarz算法,并在松弛参数和多分裂合理限制下,收敛性分析改善了多分裂算法参数收敛的固有模式;通过利用绝对值方程组与线性互补问题的等价关系,首次给出了绝对值方程组存在唯一解的充要条件;通过引入一类等价方程,并结合线性互补问题的不动点方程,提出了一类二步搜索模系矩阵分裂法。

项目组成员已在国内外著名学术期刊中国科学•数学、Numer. Linear Algebra Appl.、J. Comput. Appl. Math.、Appl. Math. Comput.和Appl. Math. Lett.等期刊上发表SCI学术论文27篇,7篇代表性论文被国内外同行SCI引用54次,非项目组成员SCI他引48次。

  1. 下载详细PDF版/Doc版

提示:为方便大家复制编辑,博主已将PDF文件制作为Word/Doc格式文件。