超立方机上一阶线性递推问题的并行求解(英文)

摘要

本文考察解一阶线性递推问题的三个并行算法在超立方机上的实现方案.通过给出原始数据与超立方机之间的适当的映射以及算法执行过程中数据的通讯方式,奇偶消元法、奇偶约简法和变间距二分法都可以在起立方机上有效地执行.文中给出了这些算法的复杂性结论.最后,为进一步减少通讯费用,我们提供了一种复杂性更小的新算法,其通讯时间是与问题规模无关的常数.