基于稀疏矩阵的并行体绘制算法

直接体绘制是三维数据可视化的重要方法。在实际应用中体数据规模庞大,如何降低计算工作量以获得更高的绘制速度是一个亟待解决的问题。文章针对该问题提出了一种运行于集群系统之上的基于稀疏矩阵的并行Splatting体绘制算法,该算法利用稀疏矩阵对体数据结构进行优化,通过实验获得了令人满意的结果。     

稀疏矩阵的转置

在《数据结构》课程中,三元组稀疏矩阵的转置算法通常会作为难点来讲解。通过介绍一般数组的矩阵转置的算法以及稀疏矩阵、稀疏矩阵的三元组表示,引出稀疏矩阵的一般算法。本文介绍的稀疏矩阵的算法是一种用C语言编写的转置算法,并通过对两种算法的涉及到的时间以及空间的复杂度进行分析,突出C语言编写的转置算法的优势。     

面向定制结构的稀疏矩阵分块方法

稀疏矩阵向量乘是科学计算的核心问题,采用定制结构来加速稀疏矩阵向量乘的执行对提升科学计算性能具有重要意义。针对目前面向定制结构的稀疏矩阵分块方法和表示方法的缺点,提出了稀疏矩阵二维均匀分块方法和相应的表示方法嵌套分块CSR。实验结果表明,提出的稀疏矩阵分块方法和表示方法能够有效减少填零个数。     

FPGA架构上面向稀疏矩阵求解的静态调度算法

在电力系统仿真中,大型稀疏矩阵的求解会消耗大量存储和计算资源,未有效利用矩阵的稀疏性将导致存储空间浪费以及计算效率低下的问题。当前关于稀疏矩阵求解算法的研究主要针对众核加速硬件,聚焦于挖掘层次集合的并行度以提升算法的并行效率,而在众核处理器架构上频繁地进行缓存判断及细粒度访问可能导致潜在的性能问题。针对基于现场可编程门阵列（FPGA）的下三角稀疏矩阵求解问题,在吴志勇等设计的FPGA稀疏矩阵求解器硬件结构的基础上,提出一种静态调度求解算法。通过对稀疏矩阵进行预处理,设计数据分布和指令排布流程,将下三角稀疏矩阵的求解过程静态映射到多个FPGA片上的处理单元,以实现下三角稀疏矩阵在FPGA上的并行高速求解。将串行算法中所有的隐式并行关系排布到缓冲中,使得所有计算单元都能实现计算、访存和单元间通信的高效并行,从而最大限度地利用FPGA的硬件资源。典型算例上的测试结果表明,相较传统的CPU/GPU求解算法,该算法能够实现5~10倍的加速效果。     

基于投影梯度法的非负矩阵分解稀疏算法

文章提出了一种基于投影梯度法的非负矩阵分解稀疏算法,该算法通过引入基于投影梯度的迭代方法,来解决加向量1-范数约束以及加向量2-范数约束的非负矩阵分解问题,得到了局部最优解。通过实验表明该算法在分解时间以及基矩阵的稀疏度表达能力上优于NMF算法和SNMF算法。     

关键路径的稀疏矩阵求解算法

求解AOE网的关键路径算法一般基于拓扑排序,虽然具有较好的时间复杂度(O(n+e)),但由于必须进行拓扑排序,同时还要进行拓扑逆序扫描,使得算法本身比较复杂。针对这个问题提出了一个算法,算法采用了稀疏矩阵作为数据的存储结构,为防止关键路径丢失,采用队列方式进行操作。同经典算法相比,该算法简单,时间复杂度相近(O(n+e/n))。     

稀疏矩阵相乘的一个改进算法

稀疏矩阵的乘法运算可用于解决许多实际的应用问题。提出一种新颖的稀疏矩阵相乘算法,算法实现中将计算单元由单个元素扩展至行向量,避免了矩阵的转置,减少了扫描次数。利用三元组和少量的额外辅助空间实现稀疏矩阵的相乘。实验结果表明了该算法的有效性。     

基于模糊扩张矩阵的启发式算法

扩张矩阵是一种规则归纳的方法。在模糊环境下,模糊扩张矩阵算法根据路径的最小模糊信息熵标准,从示例中归纳产生一组模糊规则。本文引入评价矩阵的概念,并使用近似集合覆盖算法的思想,对上述模糊规则归纳方法做了改进。实验结果表明,与原算法相比,改进后的版本增添了许多优点,比如,得到的规则较少,运算速度较快等。     

应用稀疏约束的非负正则矩阵学习算法

针对非负矩阵分解后的数据稀疏性较低,训练样本偏多导致运算规模持续增大的普遍现象,本文提出基于稀疏约束的非负正则矩阵学习算法,本文算法是在样本几何结构信息条件上执行非负矩阵分解操作,并且与学习算法结合,不仅能够有效保持样本局部结构,还能够充分利用前期分解结果参加迭代运算,从而达到降低运算时间目的. 本文实验表明与其他算法比较来说,本文方法在ORL人脸数据库上最多节省时间14.84 s,在COIL20数据集上为136.1 s;而在分解后数据的稀疏性上,本文方法在ORL人脸数据库上的稀疏度提高0.0691,在COIL20数据集上为0.0587. 实验结果表明了算法有效性.     

基于稀疏矩阵的低复杂度安全网络编码算法

针对安全网络编码复杂度较大的问题,提出一种基于稀疏矩阵的安全网络编码算法。利用稀疏矩阵占用较少的存储空间和运算速度快的优点,在信源处将信源信息与稀疏矩阵进行矩阵变换操作,使得随机网络编码能以较高的概率达到信息论安全的要求。仿真结果表明,该算法能提高编解码速率,降低复杂度,减少存储空间。     

基于分块和净化的搜索引擎排序算法

展开了对互联网搜索引擎结果集的智能排序研究,提出了一种基于扩展网页质量和VIPS分块算法的智能网页排序算法,并对结果进行净化处理以及查询优化。实验结果表明研究提出的新算法提高了推荐精度。     

Web页面主题相关性排序算法的研究

分析了Web页面主题的分布的特点,对经典的页面排序算法进行了探讨,提出了一种基于内容和超链接分析并结合用户点击行为的相关性排序算法。该算法考虑了超文本标记、锚文本、文本内容等对相关性的影响,引入动态比较矩阵来计算相应的权重系数,能够客观分析网页所包含的主题信息,使检索结果排序更合理。实验表明,该算法能有效提高查准率,较好地解决了主题的漂移现象,且具有较好的性能。     

基于稀疏矩阵的Arnold数字图像加密算法

针对原有Arnold数字图像加密算法中常见的密钥空间不足的问题,提出了一种基于稀疏矩阵的Arnold数字图像加密算法--SMA;同时为了进一步提高该基于稀疏矩阵的Arnold数字图像加密算法的安全性,利用图像分层及三层加密结构的思想来加以改进,提出了安全性提升算法--3SMA(3 round SMA)。SMA算法的加密流程首先利用Arnold变换将明文图片扩散到一个较大的稀疏矩阵中,再去除稀疏矩阵中的无效元素得到密文;解密时输入密文图片,依照预先计算好的对换表将密文中的像素调整回原来的位置得到明文。3SMA算法使用三个不同的轮密钥,每一轮都处理明文图像中的两个颜色分量以达到加密的目的。实验表明,与已有的Arnold数字图像加密算法进行对比时,SMA与3SMA算法具有更高的安全性。     

A parallel direct method circuit simulator based on sparse matrix partitioning

Solving a system of linear simultaneous equations representing an electrical circuit is one of the most time consuming tasks for large scale circuit simulations. In order to facilitate a multiprocessor implementation of the circuit simulation program SPICE, decomposition algorithms should be employed to partition a sparse matrix equation of the overall circuit into a number of subcircuit equations for parallel processing. In this paper, the performance of a parallel direct method matrix equation solving routine was studied in several contexts: the theoretical lower bound on performance was derived and the tradeoff between parallelism and communication is presented; various implementation and performance tuning issuing is also reported. This routine is written in such a manner that the data structure is compatible with SPICE Version 3c1. The speedup obtained from the simulation of two test circuits on a message passing multiprocessor system built on Transputers will be reported. Finally, the factors affecting the performance of the multiprocessor system are outlined and the overheads affecting the system performance in the implementation are identified.     

基于稀疏矩阵存储的状态表压缩算法

正则表达式匹配对于网络安全应用至关重要。将稀疏矩阵和索引表引入确定的有限自动机的状态转换表,提出了一种稀疏矩阵索引的状态压缩表算法,并给出了稀疏矩阵和索引表的构造方法。而后同字母压缩表算法结合,给出了该算法的优化策略。最后在实际规则集上进行评估,实验结果证明了算法的压缩效果,并进一步得出了算法的适用范围。     

Normalised fuzzy index for research ranking

ABSTRACT

There are great interests of designing research metrics and indices to measure the research impacts in research institutes. Unfortunately, most of those indices ignore critical design issues, e.g. the disparity between domains, the impact of journals or conferences in which papers are published, normalising the range of the index values to certain intervals, and the scalability of using the index to rank different research entities. In this paper, a new normalised fuzzy index, (NF_index), is proposed as a fuzzy-based research impact metric. The proposed index is a scalable index whose values are normalised to the percentage levels. NF_index achieves both inter-discipline normalisation and intra-discipline consistency. The capability of NF_index to achieve the inter-discipline normalisation enables fair comparison between different research domains regardless their nature in terms of influence and contribution to other research areas, e.g. natural science. Therefore, NF_index gives a universal normalised single-number metric that can be used by research institutes to solve the problem of inter-discipline scholar ranking. Moreover, it can help universal ranking of universities and research institutes according to their research capabilities and impacts. The obtained results, on diverse research areas, prove the potential of NF_index in terms of both intra-discipline consistency and inter-discipline normalisation.     

基于网站影响力的网页排序算法

传统的排序算法主要是根据网页之间的链接关系进行排序,没有考虑到网站与网页之间互相增强的关系和用户对网页的重要性的评价。为此提出了一种基于更新时间、网页权威性和用户对网页的反映的相关排序算法。该算法以网站为节点计算每个网站权威值,在为网页分配权威值时考虑了网页在网站内的位置和用户对其的反映,并通过网站与网页之间相互影响的关系来相互反馈。实验结果表明,与传统的PageRank、HITS等排序算法相比,该算法在检索性能上有明显提高。     

基于稀疏随机矩阵的再生码构造方法

针对已有的再生码编码方案的运算是基于有限域GF（q）、运算复杂度高、效率低的问题,提出了一种将GF（2）上的稀疏随机矩阵和乘积矩阵框架相结合的再生码构造方法。首先,将文件数据矩阵式排布后根据编码矩阵进行行异或运算;其次,节点失效后,参与帮助节点根据失效节点的编码向量编码本地数据并发送至修复节点;最后,修复节点根据接收到的数据译码出失效节点原有的数据。实验结果表明修复带宽至多只有传统纠删码修复方案的1/10,相比基于传统范德蒙编码矩阵的再生码,编码速率提升了70%,译码恢复速率提升了50%,方便了再生码在大规模存储系统中的应用。     

基于RISC-V向量指令的稀疏矩阵向量乘法实现与优化

开源指令集架构RISC-V具有高性能、模块化、简易性和易拓展等优势,在物联网、云计算等领域的应用日渐广泛,其向量拓展部分V模块更是很好地支持了矩阵数值计算.稀疏矩阵向量乘法SpM V作为矩阵数值计算的一个重要组成部分,具有深刻的研究意义与价值.利用RISC-V指令集的向量可配置性和寻址特性,分别对基于CSR、ELLPA...