求解循环三对角方程组的追赶法

利用LU分解的思想,首先将循环三对角方程组的系数矩阵A分解成3个矩阵的乘积LUD,其中L是下三角矩阵,U是单位上三角矩阵,D是拟对角矩阵(每行只有两个非零元素,前n-1行非零元位于主对角线和最后一列上,第n行非零位于第1列和最后一列上);然后,运用追赶法的思想依次用前代法("追")解出Lu=d的解,回代法("赶")解出Uv=u的解;再利用Dx=v的第一行和最后一行求出未知量xn,进而回代求解出所有未知量。该方法虽然将系数矩阵分解成3个矩阵的乘积,但计算过程并不复杂,总的算数运算量只有O(14n),小于传统算法的计算量(O(17n))。文章对数值计算的稳定性进行了分析,当矩阵A对角占优且2ai≤bi时,算法是数值稳定的。数值试验结果与理论分析相吻合。

追赶法并行求解循环三对角方程组

给出了求解循环三对角线性方程组的一种并行算法。在系数矩阵满足对角占优的条件下,利用该方法能够快速、稳定地求解循环三对角线性方程组,在单个进程上的计算量仅为O(17n),与传统算法求解循环三对角线性方程组的计算量相同。而且,本算法可以方便地实施分布式并行计算,各进程仅需向主进程传递8个实数,而主进程向各子进程传递2个实数,通讯量较小。数值实验结果表明:对于大规模的循环三对角线性方程组,利用16个进程计算的并行效率均在0.75以上。求解三对角线性方程组的传统追赶法实则是本文算法的一种特例,因此,该算法也可用于求解三对角线性方程组。

直接数值模拟中三对角方程组并行算法研究

为了提高大规模直接数值模拟(DNS)中三对角方程组的并行求解效率,提出了一种并行分裂算法.该算法基于Wang 的分裂算法,采用平均分配策略划分三对角方程组,利用非阻塞通信模式取代阻塞通信模式,以原有空间存储新的计算结果.在Linux集群服务器上进行了两种不同规模三对角方程组的实现,并研究了不同节点数目与计算规模下的计算时间和加速比.结果表明,该算法的计算与通信重叠度高,计算步骤和存储开销小,具有较高的并行计算效率.在百兆网络条件下,从1×105规模矩阵开始具有明显并行优势,并且随矩阵规模增大,加速比不断提高.该算法适用于大规模三对角矩阵的并行计算.

三对角方程组行处理法并行解法

利用行处理法和分治策略给出一个求解任意三对角方程组的并行迭代解法 ,证明了所给解法对任意相容性三对角方程组收敛 ,讨论了所给解法的迭代终止条件 ,进而讨论了其对应分布式MIMD并行迭代算法的设计法则 .按照并行解法 +并行计算机 =并行算法的模式 ,使用给出的并行解法 ,可以给出一些求解三对角方程组的新的MIMD并行迭代算法 .

三对角方程组通用性迭代解法

在文献(四川师范大学学报:自然科学版,2008,31(2):187-188.)的基础上,提出一种对任意相容性三对角方程组均有效的迭代算法,证明该算法的收敛性,并设计并行处理方案和测试用例.该算法基本思想是:利用三对角方程组系数矩阵中行向量的部分正交性,将三对角方程组系数矩阵分为3组,使组内行向量相互正交,通过压缩存储将3组行向量压缩为3个行向量,从第一组开始用文献的方法在3组之间循环迭代,并取加速因子为1.该算法的特点是:对任意相容性三对角方程组均收敛,易于并行且节省存储空间,特别适合大型和超大型方程组的求解.

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

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

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

文中提出一类 Toeplitz三对角方程组的一种分布式并行算法 ,该算法以系数矩阵的分解为基础 ,充分利用了系数矩阵结构的特殊性 ,算法因并行化而引入的冗余计算量非常少 ,算法的通信机制简单 ,通信量仅与处理机台数p有关 ,与方程组规模 n无关 ,算法具有很高的并行效率 ,理论分析和数值试验表明 ,其加速比 Sp(n)→ p(n→ +∞ ) ,此为线性加速比的理想情况 .文中给出了算法在分布存储多计算机系统上的数值试验结果 .

并行求解周期性三对角方程组的谢-莫方法

针对工程计算中出现的周期性三对角线性方程组,本文利用谢尔曼-莫里森方法修正周期性三对角线性方程组,将其转化为求解两个三对角线性方程组的问题,结合分治法进行并行计算。在对周期性三对角线性方程组并行化分析的基础上,在集群系统中利用可移植消息传递标准MPI进行并行程序设计。结果表明,使用该方法求解周期性三对角线性方程组,既具有数值稳定性,又收到较好的并行效果。

求解三对角方程组的并行追赶算法

通过分析影响算法的并行效率的主要因素,根据分而治之策略中的分块思想提出了一种求解三对角方程组的并行追赶算法。然后在机群系统中,MPI环境下实现了该并行算法,对并行算法的加速比和效率与原串行算法进行了比较,结果表明此算法有较高的计算效率。

三对角方程组贪心方法并行迭代法

利用正交投影方法、贪心方法和分治策略给出一种求解任意三对角方程组的新的并行迭代解法.证明了该解法对任意的相容性三对角方程组收敛.分析了解法的复杂性、数值稳定性和相容性.探讨了解法对应的消息传递MIMD并行算法的设计方法.

三对角方程组的分布式SPP算法

发展了单向并行分裂法(SPP)用于求解三对角和块三对角线性方程组,算法考虑了三对角线性系统求解中文件IO及结果传输通信所占时间比例较大的特点,充分利用了计算、文件IO与通信三者之间的重叠。分析了SPP算法的计算与通信开销。在工作站机群上进行了测试分析。

三对角方程组通用性迭代解法

在行处理法的基础上，提出一种求解三对角方程组的通用性迭代解法，用几何法证明了该算法的正确性，并讨论了该算法的内在并行性。最后，给出了一个测试用例。该算法的优点是：对任意相容性三对角方程组均收敛，易于并行实现。

三对角方程组行处理法分布式并行迭代算法的分组方法

给出大型和超大型三对角方程组的一种分组方法,使之适合三对角方程组行处理法分布式并行迭代算法设计中分治策略的需要,并适合三对角方程组行处理法并行解法在结合给定分布存储MIMD计算机模型时的任一种MIMD互连网络拓扑结构.

用插值法求拟三对角方程组的数值解

文章将求解三对角线性方程组数值解的插值法进行推广 ,得到一种求解拟三对角方程组的插值算法 .从理论分析和数据实验两方面都表明 ,此算法的时间复杂性和精度都与LU分解法相当 .由于在计算过程中不需设置二维数组 ,和其它算法比较起来 ,它占有较小的内存 .另外 ,此算法的设计思想还可用来求解其它一些线性方程组 .

基于MPI三对角方程组的并行算法

并行计算作用是通过把计算任务基本平均的分配给各个处理器,从而使每一处理器计算的规模减小,最终使大规模的计算划分为小规模的计算,并且使计算精度提高、计算时间减少。为此,介绍了MPI的一些基本概念以及基于MPI的三对角方程组的并行算法,并且利用MPI并行环境分析了三对角方程组实际并行计算结果,因而证明了基于MPI的并行计算对处理大型稀疏线性方程组是较高效的一种方法。

并行求解拟三对角方程组的二分算法

用并行算法设计的基本技术——二分法。

非对角占优三对角方程组的一类解法及其数值实验

本文针对非对角占优三对角方程组,通过矩阵变换,可将其化为五对角方程组,证明了该系数矩对称正定,并给出了一组对角占优的充分条件,从而可用多种方法有效地求解。用数值实验验证了该算法的有效性。

工作站网络环境中三对角方程组并行求解

此文考虑工作站网络环境中三对角方程组的有效并行求解，其中每台处理机只拥有原方程组的部分等式信息，并提出适合于分布主存并行计算的并行ＬＵ分解算法，同时给出算法的计算与通讯的复杂性分析；并从理论及实验两方面阐述了缩减系统求解策略是影响算法在多机系统中求解效率的重要因素；所有算法由ＰＶＭ软件系统，支持实现并在工作站网络环境中测试。

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

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

工作站网络下三对角方程组并行求解

考虑工作站网络（ＮＯＷｓ）中三对角线性方程组的并行求解，基于最小秩解耦算法与分而治之并行计算模式，提出并行最小秩解耦算法（ＰＭＲＤ）。它在计算过程中保持原矩阵的结构特征，数值稳定性高。本文给出算法的数值特征分析以及计算与通讯复杂性分析并与Ｍｅｈｒｍａｎｎ的分治算法比较。