求解k阶线性递归方程组的一种更有效的并行算法  

A New Parallel Algorithm for Solving the System of k-th Order Linear Recurrence Equations

作　　者：崔国华[1] 李庆华[1] 肖国强[1] 熊光荣 

机构地区：[1]黄冈地区工业学校,华中理工大学计算机科学与工程系

出　　处：《华中理工大学学报》1994年第7期92-96,共5页Journal of Huazhong University of Science and Technology

基　　金：国家自然科学基金

摘　　要：将求解ｋ（ｋ≥２）阶线性递归方程组问题转化为求矩阵序列部分积问题，在ＳＩＭＤ共享存储模型上提出了求解ｋ阶线性递归方程组的一种新的有效并行算法．研究表明，本算法的加速和效率比现有算法均有较大的改善．To facilitate the parallelization of solving a system of linear recurrence equations,thesolution of the system of the k-th(k≥2)order linear recurrence equations is transformed in-to the computation of partial products Ai A(i=1)…Ai(i=2,3,…, N)of matrix sequence AN,A(N-1),…,A1. Based on the SIMD-SM model, a new and more efficient parallel algorithm isproposed. It is shown that for N=tp2 and P>k ,the algorithm proposed gives a speed-up ofSp>P/[2(k+1)] with efficiency Ep>1/[2(k+1)],where t is an integer,t≥1, N is thenumber of unknowns and P is the number of processors,For N》k and k =iP,he speed-upand efficiency For N=tp2 +n,the performance of the algorithm is still foundsatisfactory.

关 键 词：线性递归方程 并行算法 加速 矩阵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]