基于LARP BS模型的最大值查找算法

具备可重配置流水线总线的线性阵列LARPBS(linear arrays with a reconfigurable pipelined bus systems)是近来出现的一种高效的并行计算模型,与理想的PRAM模型不同,LARPBS是现实可行的。基于LARPBS模型,Y.Pan介绍了2种宽度和精度任意的数据项的最大值查找算法:算法1使用了N^2/2个处理机、O(1)时间,它是目前时间最优的算法;算法2使用了N个处理机、O(loglogN)时间。本文介绍了2种最大值查找算法,时间复杂度同Y.Pan的算法,但所用处理机数减少了一半,这是对Y.Pan算法的重要改进。

基于量子计算加速的Jacobi算法

Jacobi算法用于求解实对称矩阵的特征值和特征向量,算法中最费时的环节为查找非对角元素最大值;量子计算中的Grover算法在搜索规模为N的无序数据库时可以将时间复杂度降为O(N^(1/2))。本文提出用Grover算法的扩展算法——最大值查找的量子算法去加速Jacobi算法中最费时的步骤,进而提高整个算法的计算速度。