• 论文 •    下一篇

关于线性递推问题的并行算法

张宝琳   

  1. 应用物理与计算数学研究所
  • 出版日期:1988-02-20 发布日期:1988-02-20

张宝琳. 关于线性递推问题的并行算法[J]. 数值计算与计算机应用, 1988, 9(2): 65-71.

PARALLEL ALGORITHMS ON LINEAR RECURRENCE PROBLEMS

  1. Zhang Bao-lin Institute of Applied Physics and Computational Mathematics
  • Online:1988-02-20 Published:1988-02-20
线性递推问题的并行计算方法是具有重要理论意义和实际意义的研究课题。在这方面已经发表了一些有价值的文章,例如[1]-[5]。在处理机个数为任意的假定下,H.S.Stone和P.M.Kogge对于SIMD类型计算机建立了求解下述一阶线性递推问题的并行算法:计算
This paper gives a general idea and the algorithms for solving linear recurrenceproblems on parallel computers. The parallel algorithms and their time complexityto the first-order linear recurrence problem, the second-order and Mth-order linearhomogeneous recurrence problems are investigated. Take the second-order problem:findingx_i=a_ix_(i-1)+b_ix_(i-2), i=1, 2, …, nwhere a_i, b_i are constants, x_0, x_(-1) are given initial values, k<i_0,x_i=A_(i,1)~(i_0)x_(i_0)+A_(i,2)~(i_0)x_(i_0-1)in which A_(i,1)~(i_0) and A_(i,2)~(i_0) are_i_2 constants depending on i_0. Futhermore, A_(i,1)~(i_0) and A_(i,2)~(i_0) canrespectively be computed by choosing x_(i_0)=1, x_(i_0-1)=0 and x_(i_0)=0, x_(i_O-1)=1, asfollows:x_k=a_kx_(k-1)+b_kx_(k-2)k=i_0+1, i_0+2, …, i. The speedup of algorithm PLA2 is about k/3, betterthan that of the well known matrix method.
()

[1] H. S. Stone, An efficient parallel algorithm for the solution of a tridiagonal linear system of equations, J.ACM 20(1973) , 27--38.
[2] P. M. Kogge, H. S. Stone, A parallel algorithm for the efficient solution of a general class of recurrence equations, IEEE Trans. Cofmp. 22(1973) , 786--792.
[3] P. M. Kogge, Parallel solution of recurrence problems, IBM J. Res. Develop. 18(1974) , 138--148.
[4] 高庆狮,张祥,王嘉谟,一类递归计算的另一种有效的井行算法,计算机应用与应用数学,8(1974) ,11-15.
[5] L. Hyafil, H. T. Kung, The complexity of paralle evaluation of Linear recurrences, J. ACM 24(1977) ,513--521.
[6] 陈景良,并行数值方法,清华大学出版社,1983.
[7] J. Nievcrgelt, Parallcl methods for integrating ordinary differential equations, Communications of ACM 7 (1964) , 731--733.
No related articles found!
阅读次数
全文


摘要