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

• 作者: 胡玥 高庆狮
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 并行算法 广函数 递归方程 合并 Bitonic排序
• 年，卷（期）: 2005,（11）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1767-1777
• 页数: 11页
• 分类号: TP301
• 字数: 13349字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2005.11.002

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高庆狮	北京科技大学信息学院计算机系	20	100	4.0	9.0
3	胡玥	北京科技大学信息学院计算机系	13	102	4.0	10.0