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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes

Solving circulant Toeplitz tridiagonal systems arises in many engineering applications. This paper presents a fast parallel algorithm for solving this type of systems. The number of floating-point operations required in our algorithm is less than the previous parallel algorithm [cf. Kim and Lee (1990)] for solving the similar system. Specifically, an overlapping technique is proposed to reduce the communication steps required. In addition, an error analysis is given. The implementation of our algorithm on the nCUBE2/E with 16 processors has been carried out. The experimental results show that the speedup is almost linearly proportional to the number of processors.     

A Note on Parallel Selection on Coarse-Grained Multicomputers

Consider the selection problem of determining the k th smallest element of a set of n elements. Under the CGM (coarse-grained multicomputer) model with p processors and O(n/p) local memory, we present a deterministic parallel algorithm for the selection problem that requires O( log p) communication rounds. Besides requiring a low number of communication rounds, the algorithm also attempts to minimize the total amount of data transmitted in each round (only O(p) except in the last round). In addition to showing theoretical complexities, we present very promising experimental results obtained on a parallel machine that show almost linear speedup, indicating the efficiency and scalability of the proposed algorithm. Received June 1, 1997; revised March 10, 1998.     

三对角矩阵的行列式的并行计算方法

文章针对三对角矩阵,利用矩阵的Schur余子式求矩阵行列式的方法,提出了一种并行求解三对角矩阵及其逆的行列式的算法,应用该算法可以得到较好的加速度。     

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.     

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

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

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

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