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

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

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

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

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

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

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

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

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

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

三角形方程组的一种分布式并行算法

提出了分布式环境下求解三角形方程组的一种新的并行算法,该算法基于将系数矩阵和右端顶分,并将其以块行卷帘方式存储在各处理器的局部存储器,利用通信与计算重叠的技术,取得了比块列扫描算法好的效果,当方程组具有多重右端项时,效果尤为突出。文中给出了在YH3M计算机上该算法的数值试验结果及其与块列扫描算法的数值比较结果。     

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

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

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

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

求解块三对角方程组的一种并行策略

提出了一种在MIMD分布式存储环境下求解块三对角线性方程组的并行算法。基于Galerkin原理适当取基构造算法,使整个计算过程只在相邻处理机间通信两次,并给出了系数矩阵为对称正定矩阵时算法收敛的条件。在HP rx2600集群系统上进行的数值计算结果表明该算法与多分裂方法相比具有较高的加速比和并行效率。     

三角形方程组的一种分布式并行算法

本文提出了一种在分布式存储环境下求解三角形方程组的并行算法,该算法将系数矩阵及右端项以行卷帘方式分布存储到各处理机中。算法中引入了一个一维p阶向量F,该向量的循环传送使处理机间的通信次数明显下降,同时该算法还采用了计算与通信重叠的技术。理论分析与数值实验表明,该算法较列扫描并行算法优越。     

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

１．引 言 循环三对角线性方程组的求解是诸多应用问题的重要组成部分．例如,周期的样条插值就导致对角占优的循环三对角线性方程组的求解［１］,当边界条件为周期边界条件时,一些偏微分方程的离散化也可能导致循环三对角线性方程组的求解．适应计算机体系结构发展的此类方程组的算法研究,是数值并行算法的重要问题之一．文献［２］讨论了适用于共享主存并行机的此类方程组的并行算法,在 Ｍｌｌｅｒ和 Ｓｃｈｅｅｒｅｒ［３］提出的并行化Ｈ对角线性方程组解法的划分方法基础上,Ｃｈｕｎｇ［４］等对循环块三对角线性方程组进行了研究…     

块三对角线性方程组的并行直接解法

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

Optimal and Efficient Parallel Tridiagonal Solvers Using Direct Methods

The problem of solving tridiagonal linear systems on parallel distributed-memory environments is considered in this paper. In particular, two common direct methods for solving such systems are considered: odd-even cyclic reduction and prefix summing. For each method, a variety of lower bounds on execution time for solving tridiagonal linear systems are presented. Specifically, lower bounds are presented that (a) hold when the number of data items per processor is bounded, (b) are general lower bounds, and (c) for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Furthermore, algorithms are presented that have running times within a constant factor of the lower bounds provided. Lastly, a comparison of bounds for odd-even cyclic reduction and prefix summing is given.     

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

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

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

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