稀疏线性方程组求解中的预处理技术综述

稀疏线性方程组的高效求解是数值计算方向的研究热点之一,其中包括预处理技术的研究。本文从技术分类的角度,总结了稀疏线性方程组求解中的预处理技术。首先,介绍了填充元缩减策略,旨在减少求解过程中存储量的同时,仍能保持矩阵的稀疏结构;其次,介绍了不同结构系数矩阵的多种匹配技术,旨在获得矩阵的对角优势性;最后,介绍了具有天然并行性的因子分解近似逆预条件子构造方法和不完全分解预条件中的并行求解技术等。     

稀疏线性方程组不完全分解预条件方法

稀疏线性方程组的高效求解在科学计算与工程应用中起着十分重要的作用。本文系统介绍一般稀疏线性方程组和块三对角线性方程组的不完全预条件构造技术,同时介绍我们提出的多行双门槛不完全分解预条件子MRILUT和局部块不完全分解预条件子LBF2（l）构造方法,并将它们应用于二维三温能量方程组的离散求解与二维Laplace微分方程的离
离散求解中,取得了满意的结果。     

大型稀疏线性方程组符号LU分解法

基于有限元总刚矩阵的大规模稀疏性、对称性等特性,采用全稀疏存储结构以及最小填入元算法,使得计算机的存储容量达到最少。为了节省计算机的运算时间,对总刚矩阵进行符号LU分解方法,大大减少了数值求解过程中的数据查询。这种全稀疏存储结构和符号LU分解相结合的求解方法,使大规模稀疏线性化方程组的求解效率大大提高。数值算例证明该算法在时间和存贮上都较为占优,可靠高效,能够应用于有限元线性方程组的求解。     

求解大型非对称稀疏线性方程组的FIMinpert算法

在Krylov子空间方法日益流行的今天,提出了又一求解大型稀疏线性方程组的Krylov子空间方法：灵活的IMinpert算法（即FIMinpert算法）。FIMinpert算法是在Minpert算法的截断版本即IMinpert算法的基础上结合右预处理技术,对原方程组作某些预处理来降低系数矩阵的条件数,从而大大加快迭代方法的收敛速度。给出了新算法的详细的理论推理过程和具体执行,并且通过数值实验表明,FIMinpert算法的收敛速度确实比IMinpert算法和GMRES算法快得多。     

一般稀疏线性方程组的因子组合型并行预条件研究

基于因子组合给出一般稀疏线性方程组的一种新并行预条件。在该方案中,应用基于邻接图的重叠区域分解,形成一串相互重叠的子区域。对每个子区域,可以采用任何不完全LU分解。之后,利用全局三角因子与全局下三角因子的乘积作为全局的并行预条件,其中全局三角因子利用限制加性Schwarz思想对每个局部上三角因子的逆进行组合得到。分析表明,提出的预条件优于经典加性Schwarz和限制加性Schwarz,且能保持对称正定性。对混凝土细观数值模拟中线性方程组的实验再次表明,新方案优于经典加性Schwarz。     

解大型稀疏线性方程组的一种有效并行ICCG法

该文分析了不完全Cholesky分解预处理共轭梯度（ICCG）法各部分的计算量，给出了占ICCG法主要计算时间的解预处理方程的并行算法，它既有比目前迭代算法快的收敛速度，又有较好的并行度。     

大型复线性方程组预处理双共轭梯度法

当复线性方程组的规模较大或系数矩阵的条件数很大时,系数矩阵易呈现病态特性,双共轭梯度法存在不收敛和收敛速度慢的潜在问题,采用适当的预处理技术,可以改善矩阵病态特性,加快收敛速度。从实型不完全Cholesky分解预处理方法出发,构造了一种针对复线性方程组的预处理方法,结合双共轭梯度法,给出了一种预处理双共轭梯度法。数值算例表明该算法求解速度快,可靠高效,能够应用于大型复线性方程组的求解。     

大型稀疏线性方程组新的ICCG方法

有限元线性方程组的系数矩阵一般具有稀疏性和对称性的特点,全稀疏存贮方法就是利用这些特点,只存贮对称部分的非零元素,采用链表式管理,即节省存贮空间,又便于动态更改．在完全Cholesky分解的基础上,构造出了新的预处理方法,应用适当的对角元修正策略,得到了一种新的ICCG方法,能够确保方程组高效准确的分解和求解．数值算例证明该算法在时间和存贮上都较为占优,可靠高效,能够应用于有限元线性方程组的求解．     

大型稀疏线性方程组的一种压缩求解算法

求解线性代数方程组是工程上经常遇到的问题,而它们的系数矩阵又往往是大型稀疏矩阵。文章介绍了一种简单易行,并且已经用C语言实现了的求解这类方程组的压缩算法。最后,还对压缩和非压缩算法进行了比较。     

一种求解线性方程组的算法

把求解线性方程组的问题转化为一个二次函数的优化问题后,给出了一个降低该优化问题求解空间维数的方法.使用这种方法把求解空间的维数降低到一维后,二次函数的最小值将很容易求得,从而得到线性方程组的解.     

块三对角线性方程组的一种并行算法

本文提出了分布式环境下求解块三对角线性方程组的一种并行算法,该算法通过分裂系数矩阵,充分利用系数矩阵结构的特殊性,使算法只在相邻处理机间通信两次.并从理论上给出了算法收敛的一个充分条件,分析了误差.最后,在HP rx2600集群上进行了数值试验,结果表明,实算与理论是一致的,并行效率也很高.     

解大规模线性方程组的Mann迭代并行算法

利用实函数不动点的Mann迭代算法,提出了一种求解大规模线性方程组新的并行算法,分析了算法的并行加速比,讨论了算法在基于消息传递机制的MPI并行环境下的实现流程,给出了并行环境上的实验.该算法适用范围广,数值计算结果表明理论分析与实际计算相符合,算法在并行环境下具有较好的并行度,可适合大规模科学与工程的高性能计算.     

求解鞍点问题的一种新的结构算法

该文给出了一种求解鞍点问题的新的结构算法.这种算法将通常算法中大型矩阵的求逆转化为求一个较小维数矩阵的逆.数值实验表明这类新方法是可行且有效的.     

块三对角线性方程组的一种有效并行算法

提出了求解系数矩阵为块三对角的线性方程组的一种适合于MIMD分布式存储的并行算法,该算法以系数矩阵分解为基础,充分利用了系数矩阵结构的特殊性,进行了近似处理,使整个计算过程只在相邻处理机间通信两次,具有很高的并行效率,并在理论上给出了该算法成立的充分条件。最后,在HPrx2600集群上进行数值试验,结果表明,加速比呈线性增加,并行效率达到90％以上。     

三维非定常不可压涡量—速度Navier—Stokes方程组的有限差分法

提出了一种数值求解三维非定常涡量—速度形式的不可压Navier-Stokes方程组的有限差分方法,该方法在空间方向上具有二阶精度,并且系数矩阵具有对角占优性,因此适合高雷诺数问题的数值求解．同时,给出了适合的二阶涡量边界条件．通过对有精确解的狄利克雷边值问题和典型的驱动方腔流问题的数值实验,验证了本文格式的精确性、稳定性和有效性．     

求多变量线性矩阵方程组自反解的迭代算法

利用矩阵分解的方法求多变量线性矩阵方程组的自反解是很困难的.本文建立了一种迭代方法来解决这个问题,利用此迭代方法可以判断多变量线性矩阵方程组的可解性,且当矩阵方程组相容时,可以在有限步迭代后得到其自反解.选取特殊的初始矩阵时,能够求得矩阵方程组的极小范数自反解.进一步,通过求新的线性矩阵方程组的极小范数自反解,能够求得给定矩阵的最佳逼近矩阵.数值算例表明,迭代算法是有效的.     

求解规范型Lyapunov矩阵方程的新方法

本文揭示了规范型Lyapunov矩阵方程及其对偶方程的一些特殊性质,充分压缩解矩阵的未知元素,并利用对偶解矩阵与解矩阵的合同关系,提出了一种高精度、高效率求解规范型Lyapunov方程的新算法,文中举例验证了新算法的正确性。 Lyapunov矩阵方程 能控制和能观测规范型 单输入单输出系统     

退化线性规划的一个新的改进的单纯形方法

本文讨论退化线性规划单纯形方法最优解的判定准则和有限主元规则.首先改进简约价值系数向量,提出线性规划单纯形方法最优解的判定准则.并且利用本文的判定准则给出[3]中定理2.3.5(P.84)的一个新的证明.然后提出一种新的混合有限主元规则,在退化情形下通过对单纯形表使用新的混合有限主元规则进行迭代,可以判断当前退化基本可行解或为最优解或给出下次迭代的主元并且跳出循环.最后给出在一组经典的退化线性规划例子下,改进的单纯形方法好的计算表现.