一类广函数——纵横矩阵加工广函数

A Kind of Wide-Function: The Vertical-Horizontal Array Processing Wide-Function

提出具有某些相同算法特征的广函数的概念,并且具体讨论了纵横矩阵加工广算法这一类广算法的定义和定理,直接推导出这类广算法的串行、倍增并行、纵横并行、多维并行等各种不同的算法.进一步以Bitonic排序问题和包括一阶递推方程在内的一类一阶递推方程的求解这两种十分不同的问题为例,把它们化成为纵横矩阵加工广函数,就可以自然地得到各自的不同的各种并行算法.并以(m,N)选择问题为例说明,一旦发现它是纵横矩阵加工广函数,就容易得到该问题的常数效率新算法,而不是并行台数增大时,效率趋向于0.

A new concept, wide-function, with some computing characteristic is proposed in this paper. For example, Bitonic Sort problem proposed by K. E. Batcher and a General Class of Recurrence Equation proposed by P. M. Kogge and H. S. Stone are two very different kinds of problem, but they can be transformed into the same kind of wide-function called vertical-horizontal array wide-function. In this paper, some definitions and theorems about this kind of wide-function are discussed. And several algorithms, such as sequential algorithm, doubling parallel algorithm, vertical-horizontal parallel algorithm, k-dimension parallel algorithm, etc. , of this kind of wide-function, including a general class of recurrence equation and Bitonic sort problem are discussed also. In this paper, authors also take （m,N） selection algorithm as an example, some new optimal algorithms with constant efficiency O（1） can be got easily when it is found that is a vertical-horizontal array wide- function.