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

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

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

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

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

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

三对角Toeplitz方程组的一种快速并行算法

利用矩阵结构的特殊性,提出了一种新的求解三对角Toeplitz方程组的快速分布式并行算法,拓展了骆志刚的求解空间.通过理论分析和在分布式存储多处理机上的数值实验,证明新算法的加速比接近于线性加速比.数值实验同时表明新算法具有很高的并行效率.

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

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

解三对角Toeplitz方程组的MIMD并行算法

本文把秩1修正技术和一阶线性递推并行消去法结合起来,给出了求解三对角Toeplitz方程组的MIMD并行算法。该算法结构简单,存储省,处理机之间通讯比较少,而且对处理机台数没有特殊要求;相对于追赶法的加速比可接近P/2(P为处理机台数)。值得指出的是,本文的算法关键产考虑并组织了一阶常系数线性递推的并行计算。

关于并行计算中的等价性定理与Toeplitz三对角方程组的并行解

一、关于L.Csanky的等价性定理 1976年,L.Csanky发表了并行计算中的重要理论结果。这一结论指出,对阵列式理论模型,求解线性代数方程组、矩阵求逆、行列式求值和求矩阵的特征多项式,在并行时间复杂性上是等价的。Csanky还给出了N阶矩阵求逆的两种O(log_2~2N)算法,使用的处理机台数分别为O(N^5)和O(N^4)。在这之前,所有求逆算法的并行步数不低于O(N)。Wang Guo-rong等已给出了求广义逆A^+和A_(MN)^+的一种复杂性相当的并行算法。

周期三对角Toeplitz线性方程组的并行算法

提出一种求解一类周期三对角Toeplitz线性方程组的并行算法.此算法的计算复杂性为O(5n),通讯复杂性为O(1),并给出了误差分析.在HP xr2600集群上的试验结果表明其并行效率可达90%以上.

块三对角线性方程组的一类二维区域分解并行不完全分解预条件

基于二维重叠区域分解,对每个子区域上局部不完全LU分解所得到的上、下三角因子分别进行组合,给出一类全局并行不完全分解型预条件.所给出的并行化方法适用于任何不完全LU分解型预条件.对采用二维区域分解与一维区域分解时所得并行预条件的并行计算性能进行分析比较.实验结果表明,提出的并行化方法普遍优于加性Schwarz并行化方法,且当处理器个数相对较多时采用二维区域分解优于一维区域分解.

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

利用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以上。求解三对角线性方程组的传统追赶法实则是本文算法的一种特例,因此,该算法也可用于求解三对角线性方程组。

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

循环三对角、循环 Toeplitz三对角线性方程组的求解在科学与工程计算中有着广泛的应用 .运用矩阵分解给出此类方程组的直接解法 ;通过分析其特性 ,给出了达到机器精度的截断算法 ,其计算复杂度几乎等同于求解一个三对角线性方程组的计算复杂度 .数值实验的结果与理论分析的结果十分吻合 .该算法还推广到求解拟三对角线性方程组 .

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

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

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

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

追赶法在求解循环和拟循环三对角方程组中的一种推广

针对循环或者拟循环三对角方程组,仿照追赶法的思想,给出了一种求解这两类方程组的追赶算法.该算法在求解循环和拟循环三对角方程组时用到的乘法和除法运算次数仅为8N和3N次,与传统计算循环三对角方程组的算法相比,提高了计算效率.数值试验表明,对于百万至千万阶的拟三对角方程组,本算法都可以在几秒内给出准确结果.

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

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

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

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

MPI+OpenMP混合编程模型在大规模三对角线性方程组求解中的应用

分布式共享存储系统的特点是每个节点内是共享存储的,而节点间是分布式存储.为了更好地利用这种多级体系结构,讨论了MPI+OpenMP混合编程模型的性能及实现方法,建立了大规模三对角线性方程组的MPI+OpenMP混合并行算法,并在上海大学高性能计算集群上与单纯MPI算法进行了性能方面的比较.结果表明,MPI+OpenMP混合并行算法具有更好的加速比和扩展性.

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

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

块三对角线性方程组的重叠分割可扩展并行近似求解方法

基于并行计算的分治思想,对于严格块对角占优的块三对角线性方程组提出一个可扩展的块重叠分割并行近似求解方法(PBOA方法).在机器精度内,利用块对角占优的条件,只需要相邻处理器间一次通讯,得到与精确解等价的近似解.在算法设计中,充分考虑计算与通信的重叠和处理机间负载平衡.通过精度分析,给出子方程组的阶数与精度的关系,从而得到通过调整子方程组的阶数来控制精度和并行效率,保证可扩展性的方法,得到的并行计算效率可随着问题规模的增加而增加.该文的方法在上海大学并行计算机“自强3000”上运行,数值实验的结果与理论分析的结果一致,得到的并行计算效率接近67%,加速比几乎是线性的.