论文部分内容阅读
求解矩阵特征值是科学计算中经常涉及到的问题。随着矩阵规模不断增大,串行算法在计算时间上无法满足人们的需要。采用并行机或者集群系统可以缩短求解大规模矩阵特征值的时间,但是因此会带来设备成本及耗电量的增加。为了解决上述存在的问题,本文提出了基于CUDA (Computer Unified Device Architecture)的雅可比迭代法求解对称矩阵特征值的GPU (Graphic Process Unit)并行算法Hybrid Algorithm(简称HA),从而克服了传统串行算法计算时间较长的问题。HA算法是结合本文提出的两个并行雅可比迭代法PA-1和PA-2这两个算法而提出的。PA-1和PA-2的主要思想都是把串行雅可比算法的求对称矩阵非对角线元素中绝对值最大者和矩阵更新这两步利用CUDA并行实现。PA-1与PA-2算法的唯一不同之处在于求对称矩阵非对角线元素中绝对值最大者时采用的算法。HA算法则是结合了PA-1和PA-2这两个算法的优点产生的。实验结果表明,HA算法比传统的串行算法运行时间要短,加速比为9.85～13.71。通过实验结果可以看到：随着矩阵规模的增加,加速比的总体趋势呈上升状态；随着迭代次数的增加,加速比非常稳定。因此,传统的串行算法的运行时间被显著减少了。本文同时也提出了基于CUDA的求解一般矩阵特征值的QR并行算法PA-QR。但是利用QR算法求解矩阵特征值要先把一般矩阵转化成上H矩阵,因此本文先提出了把一般矩阵转化成上H矩阵的并行算法PA-H。PA-H算法的主要思想是利用CUDA并行实现一般矩阵转化为上H矩阵的串行算法中的求出第k-1列的第k-1个以下的元素中绝对值最大的元素和行交换、列交换以及进行变换时对行和列进行消元变换。PA-QR算法的主要思想就是利用CUDA并行实现串行QR算法中的4个一重循环。实验结果表明,PA-H算法的加速比为1.79～7.81,而PA-QR的加速比可以达到3.24～118.9。并且随着矩阵规模的增加,加速比在不断增加。随着迭代次数的增加,加速比非常稳定。