稀疏图上有效的MST多边更新并行算法

ＭＳＴ（最小生成树ＭｉｎｉｍｕｍＳｐａｎｎｉｎｇＴｒｅｅ之略）多边更新（ｕｐｄａｔｉｎｇ）问题定义如下：给定一个赋权图Ｇ（Ｖ，Ｅ）和Ｇ的一棵最小生成树Ｔ（Ｖ，ＥＴ），其中｜Ｖ｜＝ｎ，ＥＴ是树边集合，（１）给Ｇ添加Ｋ条新边，或者（２）在图Ｇ上改变Ｋ条边的权后重新为Ｇ寻找一棵最小生成树，１≤Ｋ＜ｎ．本文基于ＳＩＭＤＣＲＥＷＰＲＡＭ共享存贮模型，运用“进－退”策略，并把这一特殊手段与已有的平行算法组合起来，为一类稀疏图（｜Ｅ—ＥＴ｜＝Ｏ（Ｋ））找到了一种有效的ＭＳＴ多边更新算法．该算法需要Ｏ（ｌｏｇｎｌｏｇＫ）时间和Ｏ（ｍａｘ｛ｎ，ｕＫ／ｌｏｇｎｌｏｇＫ｝）处理机．

一种有效的最小生成树并行算法

本文基于三维网孔处理机阵列，运用分而治之策略和数据归约技术在加权无向图上给出了一种新的有效的最小生成树算法．该算法需要Ｏ时间和Ｏ（ｐ）处理机．当时。

赋权有向图的最小生成树算法

针对赋权有向图最小生成树问题存在可行解的情况,根据树节点入度最大值为1的性质,提出赋权有向图最小生成树性质。采用反证法,调整生成树根节点到弧头的路径来证明赋权有向图MST性质的正确性。基于赋权有向图MST性质,给出改进的Prim和Kruskal算法及其时间复杂度分析。实验给出构造某赋权有向图实例最小生成树的具体步骤,表明这2种算法能正确有效地构造赋权有向图最小生成树。

事业选择我 我选择了事业

每个人在人生道路上常常会遇到如何选择的问题。路就在自己脚下,走什么路,要自己下决心作出选择。 我曾经是个埋头读书的学生,后来选择了教师职业,多年来的实践表明我选择了一条非常适合我自己的正确道路。静观世界,每个人都会有自己心目中的一份事业,这是历史过程的必然产物。我的事业本已确定,剩下来要做的全部事情就是驾驭好日常生活,健健康康的活着,然后争分夺秒地耕耘在教学、科研的岗位上,既培养合格学生,又攀登心目中已经确立的科学高峰。如果忽略一些因素的话,这应该说是一幅美好的蓝图。 现实生活虽然充分理解我的追求,却只赞同了一半,这是历史的安排。今年四月,我被正式安排到了学院党委副书记的岗位上,分管学生工作。

基于三变量模型的剪切波去噪方法

针对图像去噪问题,提出了两种基于三变量模型的剪切波去噪方法.首先利用互信息对剪切波系数间的依赖关系进行量化分析;然后根据依赖关系选取含噪系数s,s的父系数p以及与s方向相反的兄弟系数c,建立了三变量最大后验估计模型.在假定s,p,c具有相同标准差的情况下,由估计模型推出一种具有闭式解的去噪方法(方法1);对s,p,c具有不同标准差的情况,给出了一种迭代去噪方法(方法2),并证明了该方法的收敛性.实验结果表明,方法1和方法2不仅具有良好的视觉效果,而且具有较高的峰值信噪比和结构相似度均值.

一种VLSI设计到无向赋权图的转换系统

基于VLSI剖分问题的需要,设计并实现了VLSI设计到无向赋权图的转换系统(VLSI/Graph Converter,VGC).介绍了电路构造图和图文件存储格式,给出了VGC的处理流程图,提出了针对VLSI线网的无向赋权图转换算法.该算法解决的关键问题是,遍历树状结构的VLSI线网,将其转换为无向赋权图并存储为指定的图文件格式.VGC系统在Windows平台下用C++实现.实验及分析表明,该系统能正确地将Verilog语言描述的门级CPU转换为无向赋权图,避免了直接在VLSI线网上进行剖分,提高了VLSI剖分的效率.

基于谱方法的无向赋权图剖分算法

在多水平方法初始剖分阶段提出了一种基于谱方法的无向赋权图剖分算法SPWUG,给出了基于Lanc-zos迭代计算Laplacian矩阵次小特征值及特征向量的实现细节。SPWUG算法借助Laplacian矩阵次小特征值对应的特征向量,刻画了节点间相对距离,将基于非赋权无向图的Laplacian谱理论在图的剖分应用方面扩展到无向赋权图上,实现了对最小图的初始剖分。基于ISPD98电路测试基准的实验表明,SPWUG算法取得了一定性能的改进。实验分析反映了在多水平方法中,最小图上的全局近似最优剖分可能是初始图的局部最优剖分,需要加强优化阶段的迁移优化算法逃离局部最优的能力。

图压缩存储格式的核排序重边匹配算法

将图核概念引入到多水平方法粗化阶段,针对图的压缩存储格式提出了核排序重边匹配(CSHEM)算法。该算法借助图核的全局信息,改进了以往仅仅利用结点的度等局部信息进行匹配的粗化算法,在对原始图粗化过程中发挥结点核值导向性作用,克服以往只能选择随机匹配(RM)算法作为导向匹配算法的缺陷;提出了基于CSHEM和重边匹配(HEM)算法的组合粗化策略,在发挥结点核值的导向性作用的同时,又不至于被过分强调而使粗化图违背结点核值大小均匀分布的原则。基于ISPD98电路测试基准的实验和分析表明,相比无向图剖分软件MeTiS采用的RM和HEM算法的组合粗化策略,提出的策略取得了一定性能的改进。

一种VLSI剖分系统的研究与实现

基于多水平方法,设计并实现了一种VLSI剖分系统(Multilevel-based VLSI Partitioner,MVP)。介绍了MVP系统的结构框图、处理流程及模块功能。MVP系统的多水平剖分程序引入图核到粗化阶段,谱图论到初始剖分阶段,群智能到投影优化阶段,得到了无向赋权图更优的剖分。MVP系统特点体现在VLSI线网到无向赋权图的转换,避免了剖分算法直接在VLSI线网上进行剖分,提高了VLSI剖分的效率。实验及分析表明MVP系统的多水平剖分程序能找到更优的图剖分,以及MVP系统找到比现有技术更优的VLSI剖分,提高了VLSI剖分的性能。

对象存储系统的镜像快速复制研究

为了提高海量存储系统的可靠性,加快系统冗余副本的重建速度非常重要,理论上两路冗余镜像可以给存储系统提供安全备份,但是当系统有一个OBD(对象存储设备)损坏后,系统重建时间(系统脆弱期)往往会很漫长。为了缩短系统的脆弱期,根据基于对象存储系统的特点,提出了采用并行镜像复制方法。该方法避免了串行重建一个OBD时由于对总线的竞争而造成"瓶颈",可以大幅度缩短系统的脆弱期,并详细介绍了这种方法实现的数据结构和实现算法等重要技术环节。

利用非高速摄像机测量转速的方法研究

对有些测量对象根本无法安装测量设备或者设备的主人不允许安装测量设备,比如测量乒乓球的旋转速度等情况;因此需要引进一种新的转速测量方法,即基于视频的角速度测量方法;本研究的目标就是利用两台价格低廉的普通摄像机取代价格昂贵的高速专业摄像机;通过两台低速摄像机同时对高速旋转对象进行采样,两台低速摄影机分别设置不同的采样频率;根据获得的采样图像,发现两组不同采样数据之间关系,建立相应的数学方程,计算出高速旋转对象的旋转角速度;通过实验,利用两台最高30帧/秒速度的摄像机,测量转速为100转/秒左右旋转对象,取得相当准确的精度的,因此,证明了该方法具有很好的实际应用价值。

视频分析中全局运动矢量快速估计的研究

全局运动一般是由于摄像机移动或转动引起,但通常摄像过程中发生转动的概率很小,所以在全局运动估计中可以忽略旋转参数,运用简单的四参数全局运动模型。迭代最小二乘估计法求出运动模型中的4个参数,再根据解出的运动方程实现全局运动估计。为提高算法实时性,改变传统上对图像中所有块进行遍历的方法,而仅对图像中的特殊子集块进行迭代计算,使得运算复杂度大幅下降。实验显示在保证不降低精度的前提下,估计速度提3高倍左右。

运用视频技术的快速三维旋转分析与计算的研究

着重讨论了基于光流场的旋转运动矢量的估计方法,它是一种非接触式的运动测量技术,对特殊的场合具有很重要的应用价值。研究中运用的是光流场特征法,即首先建立刚体运动方程,然后根据特征点对坐标,采用两步迭代交替法计算出运动方程参数,进而计算出测量对象的旋转矢量。为了提高运算的速度,对投影平面上的位移矢量测量采用了基于灰度编码的位平面的块匹配算法,该算法中以简单的逻辑异或运算来完成两帧中的特征块匹配搜索,以降低运算复杂度。最后通过一组实验验证了测量结果是比较准确的。

视频分析中利用可变阈值的运动估计算法研究

研究的是基于阈值的运动矢量估计技术,根据视频序列中运动矢量的特性,构建阈值函数。对于匹配搜索的不同位置自动生成对应的阈值,建立从中心向外逐渐松弛的约束条件,及时终止对不必要候选块的匹配搜索。不仅能够提高匹配速度,而且能够避免遍历搜索中容易陷入局部最小化的问题。同钻石搜索法相结合,能进一步提供运算速度。还提出了通过均值累加阈值法消除由于全局运动补偿引入的噪声,该方法可以确保捕获运动对象的真实性。通过实验验证,对大多数的视频序列,能在不损失精度的情况下,运动估计速度提高几乎一个数量级,运动矢量捕获的真实率在70%以上。

无向赋权图剖分优化问题的研究进展

无向赋权图剖分优化问题作为图论中的一个典型组合优化问题,在大规模集成电路设计、并行计算、数据挖掘、任务调度、知识发现、图像分割等领域有着广泛的应用。本文给出了无向图剖分优化问题的相关概念;从寻优策略的角度,将无向图剖分优化问题的求解算法分为构造性算法和迭代改进算法;分析了求解无向图剖分优化问题的迁移方法、几何方法、组合方法、谱方法、元胞自动机方法;重点讨论了多水平方法的粗化阶段、初始剖分阶段和优化阶段相应的匹配算法、初始剖分算法和迁移优化算法;介绍了无向图剖分优化问题的典型应用领域并指出了该问题今后的研究方向。

基本和混合元胞自动机的伪随机数发生器研究

针对基本元胞自动机(Cellular Automata,简称CA)、混合CA的伪随机数发生器进行了深入的研究,通过对比实验观察到混沌型基本CA输出的伪随机序列质量稳定并较优,而混合CA输出伪随机序列的相关性,尽管优于基本CA的平均表现,但远差于混沌型基本CA的表现。针对混合CA的伪随机数发生器,提出了一种基于混合CA与粒子群优化(Particle Swarm Optimiza-tion,简称PSO)算法融合的伪随机数产生算法。在该算法中,元胞对应于PSO的粒子,每个元胞按照各自不同的规则进行迭代演化,其对应粒子在迭代规则空间中飞行。该算法通过计算每个元胞产生伪随机序列的熵值作为粒子的适应度函数值,有效地实现每个元胞最佳规则的搜索,一定程度上提高了混合CA产生伪随机序列的质量。给出了基于小生境技术、构造出最优CA-PSO耦合伪随机数发生器的研究方向。

一种应用于矩阵计算的并行算法──行固定法

Row fixation is a parallel algorithm based on MPI that can be implemented on high performance computer system. It keeps the characteristics of matrices since row-computations are fixed on different nodes. Therefore the locality of computation is realized effectively and the acceleration ratio is obtained very well for large scale parallel computations such as solving linear equations using Gaussian reduction method, LU decomposition of matrices and m-th power of matrices.

利用数字视频技术测量旋转速度的研究

基于视频的测量系统,具有非接触,安装维护简捷而且费用低等特点;本研究的目标就是利用摄像机对测量对象进行视频采集,然后提取相邻两帧图像;当运动对象进行简单的单轴旋转时,利用Hough变换(或Rando变换)技术进行直线的角度检测;计算出相邻帧的角度差,根据间隔时间,计算出角速度;当球体进行多轴旋转时,根据球体标志投影,结合三维空间刚体运动模型,利用一组特征点坐标,采用两步迭代交替估计运动参数,求得运动物体相对三维空间各个轴的角速度;并对特殊已知结构参数的运动物体给出了简化的计算方法,通过实验表明本方法测量结果满足要求。

一种借助邻接矩阵求任意图最大团的方法

最大团问题是图论中重要的NPC问题。文章以一种新的方法,通过矩阵运算选择图上可能存在最大团的分支,进而实现求解最大团的问题。算法的每一个步骤都可以用成熟的并行方法替代。

一个基于QR分解的并行原-对偶内点算法

首先介绍了原-对偶内点算法的主要计算步骤,阐明哪一步上可以进行并行化处理.接着介绍QR分解的理论,及如何利用QR分解并行求解线性方程组.最后提出了一种基于QR分解的并行内点算法,并给出了实验结果.