对称矩阵特征值分解的硬件实现研究

论文摘要

矩阵特征值分解被应用于科研和工程的很多领域,如主成分分析算法、人工视觉等。因此,对矩阵特征值分解的硬件实现进行研究,寻找一种较好的硬件实现策略具有十分重要的意义。在现有的矩阵特征值分解算法中,乘幂法适合于求解稀疏矩阵的主特征值,反幂法适合于知道矩阵特征值求解相应特征向量的情况,而作为乘幂法推广的子空间迭代法非常适合于求解大型稀疏矩阵的特征值。对于对称矩阵,有三种方法可以求解其特征值:Jacobi旋转法、单侧旋转法和QR方法。Jacobi旋转法在利用矩阵的正交变换对矩阵进行对角化求取矩阵特征值,并且在求解特征值的同时可以很方便的利用正交变换求解出特征值对应的特征向量。单侧旋转法是Jacobi方法的变形,它只利用单侧旋转来先求取矩阵特征值的平方,再求取矩阵的特征值。QR方法是基于QR分解的一种求取矩阵特征值的方法,它将矩阵通过分解变成一个上三角矩阵,然后求解其特征值。对于Jacobi算法的硬件实现,论文经过分析总结提出了两种大的结构:串行计算机构和并行计算结构。串行计算结构又根据具体计算过程的不同分成了两种方法,一种方法是先寻找矩阵非对角元素的最大元,然后对其相应的行列进行Jacobi旋转;另一种方法是通过遍历的方法来对矩阵的行列依次进行Jacobi旋转。并行计算结构是一种阵列型的结构,它由对角线处理单元和非对角线处理单元通过一定的连接组成,每个处理单元处理四个矩阵元素,在一次处理后跟相邻的单元进行数据交换进行新的一次计算。CORDIC算法将一个向量[x,y]旋转θ角度分解成连续的±arctan2-i（i=0,1,…b）角度的旋转。利用它可以将每次Jacobi运算转换成只有加法和移位的多次迭代运算和一个比例因子的缩放运算。它非常适合应用于对Jacobi算法的硬件实现。论文通过CORDIC迭代来实现Jacobi算法的两种计算结构,利用VerilogHDL来进行硬件实现描述,然后对设计进行了验证和数据采集,通过几种结构的性能对比,确定并行计算结构为最佳实现方案。

论文目录

• 致谢
• 摘要
• ABSTRACT
• 插图清单
• 表清单
• 第1章 绪论
• 1.1 研究背景
• 1.2 主成分分析的数学模型、几何解释和推导过程
• 1.3 国内外研究现状
• 1.4 研究内容和选题意义
• 1.5 论文章节安排
• 第2章 矩阵特征值分解算法
• 2.1 矩阵特征值基本理论
• 2.2 乘幂法与反幂法
• 2.2.1 乘幂法
• 2.2.2 乘幂法的加速及降价
• 2.2.3 反幂法
• 2.2.4 子空间迭代法
• 2.3 求对称矩阵特征值的几种方法
• 2.3.1 Jacobi旋转法
• 2.3.2 单侧旋转法
• 2.3.3 QR方法
• 第3章 JACOBI算法计算结构分析
• 3.1 JACOBI方法的串行计算结构
• 3.2 JACOBI方法的并行计算结构
• 3.3 CORDIC算法的原理和应用
• 第4章 JACOBI算法的硬件实现和性能分析
• 4.1 JACOBI算法串行计算的硬件实现
• 4.2 JACOBI算法并行计算的硬件实现
• 4.3 不同实现的性能分析和对比
• 第5章 总结和展望
• 5.1 论文总结
• 5.2 前景展望
• 参考文献
• 作者简历