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

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

应用于分类EST序列拼接的并行遗传算法

利用EST（Expresscd Sequence Tag)序列数据发现新基因，是当前国际上基因组研究的热点，但程序设计十分复杂。计算量非常巨大。而遗传算法是一种能在复杂而庞大的搜索空间中利用问题的固有知识来缩小搜索范围，避免组合爆炸，从而得到最优解或准最优解的通用搜索算法。该文结合核酸序列的特征，提出了一种改进的并行遗传算法，应用于EST序列拼接的组合优化。     

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

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

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

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

自适应最优保存的模拟退火遗传调度算法研究及其应用

该文对调度算法做了简单的介绍。在结合已有的模拟退火算法和遗传算法的基础上,改进了现有的遗传调度算法,自适应地保存最优个体,并对其进行模拟退火。与简单最优保存遗传调度算法进行了比较,结果表明新的算法比原有算法搜索能力更强,在跳出局部最优方面也有改进,有效地解决了原有遗传调度算法的早熟现象。     

Smith-Waterman算法的若干优化及并行实现

Smith-Waterman算法是目前被使用最广泛的序列相似性比较算法之一,它适用于寻找局部相似序列对。该算法精确度较高,一直沿用到现在。目前,使Smith-Waterman算法提速,寻找该算法的优化方法,是世界各地的科学家们正花费大量心血研究的课题。该文从算法并行化着手,充分利用近期蓬勃发展的高性能计算机系统,提出了若干Smith-Waterman算法的优化思想,并在cluster机上实现。     

一种优化的三序列比对算法及并行实现

序列比对算法在许多不同的领域得到应用。当前,一个重要的应用就是比对大分子,例如DNA和蛋白质序列比对。许多情况,有必要比对三序列。DavidR.Powell就提出过一种使用线性空位罚分的优化的三序列比对算法。这个算法最早是由Ukkonen提出的,该算法基于简单打分的两序列比对。该文通过引入“检查点法”对其进行改进,并充分利用近期蓬勃发展的高性能计算技术,对算法并行化,且在cluster机上实现。     

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

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

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

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

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

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