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

针对大型方程组的特点,本文提出了一种求解一类Toeplitz三对角方程组的分布式并行算法.该算法首先并行求出原Toeplitz三对角方程组的近似解,然后在给定的误差范围内对近似解进行修正,该算法的通信机制简单、冗余计算量少.数值试验表明该算法具有较高的并行效率.     

近似三对角Toeplitz方程组的快速分布式并行算法

利用近似三对角Toeplitz矩阵的特殊结构,提出了一种新的求解近似三对角Toeplitz方程组的快速算法．在三对角Toeplitz矩阵的近似LU分解的基础上,利用“分而治之”的思想,并结合秦九韶技术和特殊的数学技巧减少大量的冗余计算,提出了求解近似Toeplitz三对角方程组的快速分布式并行算法,并在理论上证明了算法具有近似于线性的加速比．最后通过数值实验证明,新的并行算法具有较高的并行效率,并且当矩阵阶数n足够大时,算法的加速比趋近于线性加速比．     

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

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

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

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

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

提出了分布式存储环境下求解三对角线性方程的一种并行算法,该算法基于“分而治之”的策略,高效地形成并求解其缩减方程组,避免不必要的冗余计算,通过对计算量的仔细估计,较好地平衡了各处理机的负载;同时,充分利用了计算与通信重叠技术,减少处理机空闲时间,分析了自救的复杂性,给 分布存储多计算机系统上的数值试验结果,数值结果表明,算法的效率较迟利华和李晓梅的ＤＰＰ算法有较大的提高。     

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

提出了分布环境下求解三对角线性方程组的一种并行算法,该算法基于对计算量的仔细估算,合理地将方程组求解工作分配到各处理机,达到负载平衡,同时,充分地将计算与通信重叠,减少处理机空闲时间;当块三以角线性方程组的系数矩阵为对角占优时,算法在执行过程中不会中断;文中分析了算法的复杂性,给出了在分析布存储多计算机系统上的数值试验结果,数值结果表明,文中算法的效率较Ｃｈｕｎｇ等的算法有较大的提高。     

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

本文提出一种求解严格对角占优的三对角线性方程组的并行算法（简称ＰＰＤ算法）,新算法计算复杂性约为８ｎ,与最优串行算法追赶法的计算复杂性相同,通信复杂性为常数．目前求解此类方程组的最优并行算法的计算复杂性约为１７ｎ,通信复杂性约为ｌｏｇＰ,相对而言ＰＰＤ算法的计算性能和通信性能都有大幅度提高．试算结果表明,加速比呈线性增加,并行效率达到９０％以上．     

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

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

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

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

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

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

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

文中回顾了Ｍｉｃｈｉｅｌｓｅ＆Ｖｏｒｓｔ算法，分析了影响Ｍ＆Ｖ．算法并行效率的主要因素，根据分布治之思想提出了一种求解三对角方程组的并行算法，新算法通信建立次数的Ｍ＆Ｖ算法的５０％，数据传输量为其３３％，最后的工作站网络环境下实现了新算法，就并行效率与Ｍ＆Ｖ算法进行了比较，结果表明在由６台工作站的组成的网络中新算法必能提高可达到４０％。     

分布存储系统上一种新的并行调度算法

在一般的分布存储系统上各个处理器可能不同且资源共享,导致了并行任务在各个处理器上的执行时间具有很大的随机性,主要根据系统及并行任务特性等引进特征参数,采用计算与通信重叠等方法设计出了一种新的并行调度算法,即使在多用户环境下应用此算法不仅能达到极高的负载平衡,充分利用系统资源而且能有效地提高并行效率及加速比。实验结果表明,提出的新的并行调度算法与已有的类似调度算法相比能更加有效地利用系统资源及提高并行效率。     

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

本文提出一种球解严格对角占优的三对角线性方程组的并行算法（简称ＰＰＤ算法）,新算法 计算复杂性约为８ｎ,与最优串行算法追赶法的计算复杂性相同,通信复杂性为常数。目前求解此类方程组的最优并行算法的计算复杂性约为１７ｎ,通信复杂性约为ｌｏｇＰ,相对而言ＰＰＤ算法的计算性能和通信性能都有大幅度提高。试验结果表明,加速比呈线性增加,并行效率达到９０％以上。     

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

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

稀疏三角矩阵线性系统的基于树结构并行求解

本文分析了大型稀疏矩阵线性方程组直接法求解的回代过程．基于改进的树结构（Ｍ—ｔｒｅｅ），提出了一种新的面向分布存储多机系统的稀疏三角矩阵线性系统并行Ｆｏｒｗａｒｄ求解算法ＭＰＦＳ．文中讨论了Ｍ—ｔｒｅｅ的结构特征，并将所提出的并行求解算法与基于Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ求解算法进行了分析和比较．结果表明，ＭＰＦＳ算法不仅适用于更多的稀疏矩阵系统，而且在求解过程中可以开发Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ算法不能开发的计算并行性，从而使求解性能得到显著改进．