解K阶线性递归N方程组的一种实用并行算法  

A PRACTICAL ALGORITHM FOR SOLVING THE K-TH ORDER LINEAR RECURRENCE SYSTEM OF N EQUATIONS

作　　者：罗晓广[1] 李晓梅[1] 

机构地区：[1]国防科学技术大学计算机科学系,长沙410073

出　　处：《计算机学报》1998年第S1期52-56,共5页Chinese Journal of Computers

基　　金：九五国防科技预研基金

摘　　要：本文提出了解K阶线性递归N方程组的一种实用并行算法．当K＜＜N时，其并行效率Ep=1／（K＋1．5）×（1＋（K＋0.5）／p），其中P是所用处理机台数．在计算过程中，每台处理机仅需通信两次，每次发送或接收K个数据．因而，本文算法通信量少，适合在分布式并行机上实现．数值实验的结果也在文中给出．This paper presents a practical parallel algorithm for solving the K-th order linearrecurrence system of N equations. If K<<N,Ep = 1/ (K+ 1. 5) × (1 + (K+ 0. 5) /p),where p is thenumber of processors,and Ep is the parallel efficiency of this new algorithm. Each processor needs onlytwo times of communication during computing. In each time,the processor sends or receives only Kdatas. Since the amount of communication is not much, the algorithm is quite suitable forimplementation on a distributed parallel computer. The numerical results are also presented in this paper.

关 键 词：线性递归方程组 递归倍增法 并行算法 并行效率 

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