• 论文 •

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

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

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

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!