求解周期性三对角方程组的广义Thomas算法

给出了求解周期性三对角线性方程组的一种新方法。该方法能够快速、稳定地求解周期性三对角线性方程组。与传统方法相比,求解一个N阶周期性三对角方程时,本文的方法可减少N次计算。本文还证明了,传统用于求解三对角线性方程组的Thomas方法(追赶法)是本文方法的一种特例,本文的方法自然地可用于求解三对角线性方程组。

一类Toeplitz循环三对角方程组的一种分布式并行算法

提出一类 Toeplitz循环三对角方程组的一种分布式并行算法 .在求解由一阶线性双曲型方程 (如迁移方程 )在一定边界条件下导出的隐式差分方程组时 ,要重复地求解此类 Toeplitz循环三对角方程组 .算法基于对系数矩阵的分解 ,贯彻并行算法设计中“分而治之”的原则 ,充分利用了系数矩阵结构的特殊性 .算法实现中通过秦九韶公式的运用 ,避免了不必要的冗余计算 ;理论分析和数值试验表明 ,算法是数值稳定的 ,且当方程组规模充分大时 ,该算法加速比趋近线性加速比的理想情况 .

循环块三对角线性方程组的一种分布式并行算法

提出一种分布存储环境下求解循环块三对角方程组的并行算法 ,该算法以矩阵子块运算为基础 ,算法实现调用BLAS3子程序 ;文中分析了算法的复杂性 ,给出了一个保证算法不会在执行过程中中断的充分条件 .

三对角线性方程组的循环规约对角占优算法

针对并行求解三对角线性方程组的对角占优(PDD)算法在系数矩阵为弱对角占优时,近似处理引入误差较大,即使是采用迭代PDD算法,收敛速度仍然很慢的问题,提出了一种PDD算法的循环归约方案。该方案采用新的分解方法,生成修正值计算方程组仍为三对角线性方程组,且保持对角占优特性。在修正值计算中采用循环归约方法,随着归约算法展开,系统的对角占优迅速增强,适时忽略非对角元素,取得解的修正值。算法的计算复杂性与迭代PDD算法基本相当,通信复杂性略高于迭代PDD算法,但解的收敛速度显著高于迭代PDD算法。不仅如此,该算法还可直接应用于非对角占优三对角线性方程组的求解。

申威众核处理器上的三对角并行求解器

三对角方程求解器是一种在很多科学与工程领域广泛应用的数值计算核心。目前,CPU、GPU等主流硬件平台上都提出了高度优化的并行算法,但是对于中国自主研发的申威26010众核处理器,还没有一种算法能有效地利用其独特的硬件特性来达到最大化的性能。提出了一种分布式CR算法swDCR,来求解大量的、规模不大的三对角方程。该算法对每个三对角方程使用多个从核并行求解,通过联合多个从核的缓存使得运算过程中所有中间变量都能存储在缓存中,同时利用寄存器通信完成核间数据的高速传输。通过设计线程级数据划分机制,使得向量化的优化效果最大化。swDCR的吞吐率相比主核上的追赶法达到了单精度43.9倍和双精度36.7倍的加速,相比从核上的追赶法达到了单精度和双精度均2.07倍的加速。该算法在申威26010处理器单个核组上可以获得24GB/s的有效带宽。

基于龙芯3B的循环规约算法向量化研究

研究国产CPU龙芯3B的体系结构,分析三对角线性方程组求解中的循环规约算法,并结合算法特性,提出循环规约算法的优化方案。采用向量化级数,利用龙芯3B处理器提供的向量扩展指令对该算法在龙芯3B上进行实现和优化。实验结果表明,与非向量化算法相比,向量化算法的性能提升较大。

循环三对角Toeplitz线性方程组的分组降阶算法

运用并行算法中分而治之的思想,给出了一种求解循环三对角Toeplitz线性方程组的分组降阶串行算法。与求解同类问题的传统算法相比,分组降阶算法的优点在于它不仅大幅度减少了内存占用量,而且还大幅度减少了算术运算量。分组降阶算法可以通过3个步骤来实现。第一步是分组降阶,其基本思路是将一个n=μm阶的方程组按行分成μ组,每组m个方程;n维解向量也对应地分成μ组。第二步是构造参数方程组,也就是依据三对角系数矩阵的特点,给出各组解之间的关系式,把不属于该组的解分量看作参数。第三步是求解参数方程组和原方程组,在这一步中,首先求解参数方程组,然后再代入相应分组的关系式便可求出所有的解分量。对于三对角Toeplitz线性方程组,同样能减少内存占用量,从而在计算机性能不变的情况下,提高求解问题的规模,但与求解三对角Toeplitz线性方程组的传统算法相比运算量有所增加。数值实验结果表明,对于特定规模的方程组来说,总存在一个最佳的分组个数使得计算时间最少;随着方程组阶数的提高,最佳分组的个数也增大。

并行ADI-FDTD的循环归约PDD实现

实现ADI-FDTD并行计算的关键是三对角线性方程组的求解。提出了一种新的分解方法实现三对角线性方程组的并行求解,使得修正值计算方程组仍为三对角线性方程组,且具有对角占优特性。修正值方程组采用循环归约算法求解,根据三对角系统的对角占优的强弱和预期的计算精度选择适当的归约次数,近似处理可加速方程组的求解。利用FDTD的重复计算特性,保存适当的中间量可降低算法的计算复杂性和通信复杂性,但对存储空间的要求更高。算例验证了算法的正确性。

循环三对角线性方程组的一种分布式并行算法

A parallel solver for cyclic tridiagonal systems on distributed-memory multi- computers is presented. The complexity of the algorithm is analyzed. We prove that the processes will not break down if the cyclic tridiagonal systems’ coefficient matrix is strictly diagonally dominant. The results of numerical experiments on a distributed-memory multicomputer YH3E show that the algorithm has a high parallel efficiency.

快速求解一类Toeplitz循环三对角线性方程组的分布式并行算法

在分布式存储环境下,提出了一种在给定误差范围内快速求解一类Toeplitz循环三对角线性方程组的分布式并行算法,该算法是在仔细研究了方程组结构特点的基础上,通过求解满足给定误差范围的方程组的近似解,从而使得通信开销小,冗余计算量少,数值试验表明:该算法具有较高的加速比和并行效率。

Sherman-Morrison公式及其应用

Sherman-Morrison公式是求矩阵之和的逆矩阵的一种特殊方法,在最优化BFGS算法和循环三对角线性方程组的求解等方面有着重要的应用。

液压泵柱塞副油膜热-流耦合特性研究

针对柱塞副油膜超薄、易破坏进而加速柱塞副磨损失效的问题,将黏温-黏压效应考虑在内后,建立了油膜热-流耦合模型。开展了对不同柱塞腔入口油温下柱塞副油膜特性的分析,建立了入口油温与整体油温、油膜厚度之间的关系;使用有限体积法离散雷诺方程和能量方程,结合周期性三对角循环算法对离散方程进行了求解;随后,在一种360°油膜特性试验台上,对柱塞副油膜3个区域内的温度及偏心量进行了测量。研究结果表明:在入口端和出口端,柱塞副油膜温度整体变化较为平缓,但有微小凸峰的存在,在中段整体呈“线性”上升;柱塞副最小油膜厚度随温度上升而变薄,且处于排油区时,变化更为明显;当油温超过45℃时,油膜热平衡被破坏,最小油膜厚度急剧减小。

改进的求解线性方程组的并行Arnoldi方法

以Galerkin原理为基础,提出了求解循环块三对角线性方程组的并行算法。根据系数矩阵的稀疏性,选取适当的子空间的基,使算法不但不会发生中断,并从理论上证明了当系数矩阵对称正定时,该并行算法收敛。最后,在HPrx2600集群上进行的数值实验结果表明,该算法的并行效率很高,理论和实际计算相一致。