摘要
文中提出一类 Toeplitz三对角方程组的一种分布式并行算法 ,该算法以系数矩阵的分解为基础 ,充分利用了系数矩阵结构的特殊性 ,算法因并行化而引入的冗余计算量非常少 ,算法的通信机制简单 ,通信量仅与处理机台数p有关 ,与方程组规模 n无关 ,算法具有很高的并行效率 ,理论分析和数值试验表明 ,其加速比 Sp(n)→ p(n→ +∞ ) ,此为线性加速比的理想情况 .文中给出了算法在分布存储多计算机系统上的数值试验结果 .
The tridiagonal Toeplitz linear systems occur repeatedly in the solution of the implicit finite difference equations derived from linear first order hyperbolic equations, i.e. the Transport equation, under a variety of boundary conditions. Interest in fast direct methods for solving these kind of linear systems has long been a hot spot of research. A parallel algorithm for certain tridiagonal Toeplitz linear systems on distributed memory multicomputers is presented. Derivation of the algorithm is introduced. The algorithm is based on the factorization of the coefficient matrix and the principle of ‘divide and conquer’ in designing parallel algorithms. Authors make full use of the special structure of the coefficient matrix. By using the customary nesting procedure, Horner's formula, authors avoid the necessary of quantities α i, (-α) i(i=2,3,…,m ) and (α m) i, (-α m) i(i=2,3,…,p-1 ). This reduces the algorithm's redundancy computation caused by parallelization. The complexity of the algorithm is analyzed using Log P model. Its communication mechanism is very simple. The communication complexity is only related to p , the number of processors, and not related to n , the size of the matrix. The algorithm's parallel efficiency is high. The analysis of complexity and numerical experiments show that the algorithm's speedup satisfy: S p(n)→p(n→+∞) . This is the best a parallel algorithm can reach. The algorithm has been implemented on parallel computers. The results of numerical experiments about the algorithm on a distributed memory multicomputer are presented in this paper.
出处
《计算机学报》
EI
CSCD
北大核心
2001年第2期173-178,共6页
Chinese Journal of Computers
基金
国家自然科学基金!重点项目 (6 99330 30 )
国家"八六三"高技术研究发展计划! (86 3-30 6 -ZD-0 1-0 3-4 )
并行与分布处理国家重
