稀疏矩阵快速转置算法的分析与优化

《稀疏矩阵快速转置算法的分析与优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第27卷第8期计算机应用与软件Vo1．27No．82010年8月ComputerApplicationsandSoftwareAug．2010稀疏矩阵快速转置算法的分析与优化王敏(渭南师范学院计算机科学系陕西渭南714000)摘要介绍稀疏矩阵的三元组表压缩存储方案时，提出了利用数组首下标元素存储稀疏矩阵总行数、总列数和非零元素总个数三方面信息的改进的存储定义方式。给出了基于新的定义结构上用C语言编写的快速转置算法，并通过对算法性能进行分析，提出了仅使用一个数组的两种改进的快速转置算法。经过对比两种改进算法的时间复杂度和空间复杂度，总结出既具有原快速转置算法时间复杂度低

2、的优点，又降低了算法的空间复杂度的优化算法，达到了对原快速转置算法进行优化的目的。关键词稀疏矩阵三元组表压缩存储快速转置时问复杂度空间复杂度ANALYSISAND0PTIMISATIoNoFFASTTRANSPoSITIoNALGoRITHMoFSPARSEMATRIXWangMin(DepartmentofComputerScience，WeinanTeachersUniversity，Weinan714000，Shaanxi，China)AbstractWhendescribingthetriplelistcompressionstoragemethodsofth

3、esparsematrix，inthispaperweproposeanimprovedstoragedefiningmethodwhichusesanarayelementinthefirstsubscriptofsequencetriplelistarraytostoretheinformationinregardtothetotalnumberofrows，totalnumberofcolumnsandtotalnumberoflion—zeroelementsofthesparsematrix．Thepapergivesthematrixfasttranspo

4、—sitionalgorithmwritteninCandbasedonthenewstructuredefinitionproposed，andpresentstwokindsofimprovedfasttranspositionalgo—rithm，bothusejustonearray，throughtheanalysisofalgorithmperformance．Aftercomparingthetimecomplexityandspacecomplexityofthesetwokindsofimprovedalgorithm，weconcludetoano

5、ptimisedalgorithmthatpossessestheadvantageoflowertimecomplexityinexistingfasttranspositionalgorithmwhilereducesthespacecomplexityofthatalgorithmaswell，anditreachesthepurposeofoptimisingexistingfasttranspositionalgorithm．KeywordsSparsematrixTriplelistcompressionstorageFasttranspositionTi

6、mecomplexitySpacecomplexity元组按“行序为主、列序为辅”的顺序构成一种线性序列，此时0引言可采用顺序和非顺序两种方式进行存储，具体采用哪种主要取决于将设计实现矩阵的那些操作。非顺序存储方式主要采用链式存储结构(比如十字链表)，适用于设计实现对稀疏矩阵的非计算机中存储矩阵的一般方法是采用二维数组，其优点是零元素个数有改变的一类操作(比如矩阵相加、相减、相乘等)；可以随机地访问每一个元素，从而易于实现矩阵的各种运算J。但对于稀疏矩阵(设m×n的矩阵中有t个不为0的元而对于矩阵转置之类非零元素个数不变的操作，则采用顺序存储结构(比如一维数组)实现较

7、为方便，即三元组顺序表。素，令6=—，称6为矩阵的稀疏因子，通常认为6≤0．05时mXn稀疏矩阵的存储信息还应包括矩阵总行数、矩阵总列数和为稀疏矩阵L2)来说，大量零元素的存储会造成存储空间的浪矩阵中非零元素的总个数。大多数参考文献中关于稀疏矩阵存费。为了在实现矩阵相关操作时提高存储空间的利用率，一种储结构的定义均额外定义了用于存储这三方面信息的结构体成有效的压缩存储方案是采用三元组压缩存储技术，即每个非零员变量，而这种存储处理其实可以进行简化：由于前述三种信息元素记录元素值的同时给出其所在行、列的下标位置，构成形如的类型同三元组的各个成员类型相兼容