文档介绍：西安电子科技大学
硕士学位论文
基于FPGA的稀疏矩阵分解实现
姓名:王亚南
申请学位级别:硕士
专业:电路与系统
指导教师:石光明
20090301
摘要稀疏矩阵广泛的应用于网络设计、计算机辅助设计、电力系统优化设计、数学规划、结构分析、微分方程求解、遗传学理论、图论等科学技术和工程领域中。稀疏矩阵算法己经发展成为计算数学的一个重要分支。而稀疏线性方程组求解是许多科学技术领域的核心问题,因此研究稀疏矩阵的算法是很有意义的。大型并行计算机和分布式计算机在该领域一直占据主导地位,但随着半导体技术的发展和结构工艺的不断改进,已经可以作为一种片上计算平台。新一代的不仅集成了大量的数值运算单元并且可以在单个芯片内部构建并行处理结构,在大数据量计算领域显著的提高了性能。本文主要设计了基于实现稀疏矩阵本文首先介绍了稀疏矩阵的特点和研究稀疏矩阵分解的意义,接着讨论了稀疏矩阵各种快速算法并给出了本文所采用的方法。在此基础上详细说明了稀疏矩阵模拟排序算法,直接分解算法,符号分解算法,数值分解算法及这些算法在上的实现过程。最后为充分发挥作为一种可编程逻辑器件的优势,将单核数值分解扩展为多核并行分解结构,并使用卣蠖该结构进行了验证,给出并分析了实验结果。关键词:稀疏矩阵分解并行分解分解的硬件结构。
,,。。—,甋甤甆,.,,,甋.,
日期望丝日期望乞至:丝本学位论文属于保密,在一年解密后适用本授权书。西安电子科技大学学位论文独创性虼葱滦声明关于论文使用授权的说明秉承学校严谨的学风和优良的科学道德,本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢中所罗列的内容以外,论文中不包含其他人已经发表或撰写过的研究成果;也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处,本人承担一切的法律责任。本人签名:本人完全了解西安电子科技大学有关保留和使用学位论文的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件,允许查阅和借阅论文;学校可以公布论文的全部或部分内容,可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证,毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。C艿穆畚脑诮饷芎笞袷卮斯娑导师签名:
第一章绪论研究背景研究概况近年来随着计算机的发展和普及,矩阵运算的重要性愈加显著,也日益广泛。在许多科学技术和工程问题中,都需要求解线性方程组应用的范围其中莕×追瞧嬉旆秸螅瑇和莕维列向量。在许多实际的问题中,矩阵脑K刂泻写罅康牧阍#橇阍5母鍪攘元的个数少的多。并且随着矩阵阶数的增加,矩阵的稀疏程度也越来越大。我们称上述零元素占优势热ヒ陨的矩阵为稀疏矩阵,而相应的线性方程组叫稀疏线性方程组【俊T诙源笮拖∈杈卣蠼星蠼馐保颐且话悴徊捎们逆矩阵的方法,因为这种方法的计算复杂度较高,不便于重复利用,也不利于硬件系统的实现,而通常采用高斯消去法或分解法。另一个问题是,这种方程组通常不能直接采用适用于满矩阵的高斯消去法或分解法,原因在于:当矩阵阶数较大时,若存储整个矩阵,将占用大量的存储空间,这对存储空间比较紧张的硬件系统并不划算。因此需要特殊的存储方案,即仅存非零元,而不存零元。在进行高斯消去或分解过程中仅对非零元进行操作,而且在消去的过程中还要尽可能的保持矩阵的稀疏性,节省硬件资源。研究稀疏线性方程组求解方法的直接目的是,充分利用矩阵的稀疏性来节省存储空间和计算时间。很多稀疏矩阵的算法都是围绕这个问题来进行设计的。用经典的高斯消去法解紫咝苑匠套椋枰5募扑慊娲⑷萘坑雗烧取K孀矩阵维数的增加,存储容量和求解时间的增加都是惊人的。而许多实际问题中的矩阵阶数都比较高,有的甚至达到几十万阶。这样仅靠提高计算机的存储容量和运算速度来解决问题是极为困难的。虽然现代的计算机工业发展水平已经相当迅速,但毕竟有它的极限。因为计算机的运算速度和存储空间每增加一个数量级,都要求设计工艺水平有一个飞跃,对要求以增加的存储容量,和对以要求增加的速度来说,计算机工业很难满足这种要求。因此研究如何节省存储空间和计对于稀疏矩阵而言,无论矩阵规模有多大,矩阵中零元还是占了绝大多数,。
矩阵的每行、每列中只有少量的非零元。所以非零元的个数与矩阵的阶数,烧取如果仅存非零元、并且只对非零元进行运算,那么存储的容量与计算时间,都将否有效利用矩阵稀疏性的关键因素。若能在求解稀疏线性方程组的过程中,解决节省存储空间、缩短计算时间和保证求解过程的数值稳定性这些问题,就能用较小的计算