摘要
An improved recursive doubling algorithm for solving linear recurrence R <n,1>is given,whose parallel time complexity is (τ++τ.) logn when n processors are available,achieving the lower bound in array processor type computation.
众所周知，一阶线性递推式Ｒ＜ｎ，１＞的计算是代数结构的一个基本计算模型。目前，在阵列机的并行处理环境下，较快的并行计算方法当数递推倍增法［１，２］。当有ｎ台处理机可供使用时，其计算时间复杂性为（τ＋＋２τ．）ｌｏｇｎ。本文改进了上述递推倍增算法，使在相同的应用条件下，计算时间复杂性改善为（τ＋＋τ．）ｌｏｇｎ，达到了更低的下界。
