进化策略算法在矩阵特征值求解中的应用

工程实践中多种振动问题的求解常常归纳为求矩阵特征值问题,另外一些稳定性分析问题及相关分析问题也可以转化为求矩阵特征值问题.为了有效求解此类问题,提出了一种新的求解矩阵特征值的进化策略算法,该算法可用于求解任意矩阵的特征值.实验结果表明,这种基于进化策略算法求解矩阵特征值的方法,与传统方法相比,表现出求解精度高,收敛速度快等优点.     

基于QR分解的方阵特征多项式数值算法

借鉴QR分解的概念,探讨如何利用QR分解法求一个方阵的特征多项式的数值算法。这就为用Matlab编程求解矩阵的特征多项式提供了条件。通过对三个不同类型矩阵的实例计算验证了该数值方法能够较好地求解一般方阵的特征多项式,比用通常的求带变量的行列式的方法和基于迹的算法要相对简单些,特别是对于高阶矩阵,其优势更加明显,且易在计算机上用Matlab编程实现,从而说明了该算法具有较高的实用价值。     

基于0-保留扰动的高斯算法平滑复杂度分析

算法的平滑复杂度能够更合理地反映算法的实际性能.在运行高斯算法求解线性系统过程中,矩阵条件数是导致求解误差偏大的一个因素.Sankar等人用0-保留高斯扰动进行对称矩阵条件数平滑分析.然而,Sankar等人给出的平滑复杂度过高而且复杂.为了解决这个问题,首先提出了两个关键的不等式;然后将这两个不等式用于对称矩阵条件教的平滑分析,得到更简单、更低的平滑复杂度;并利用该结果对高斯算法求解精度进行平滑分析,从而得到更低的平滑复杂度.     

拟Newton法在高阶矩阵中的应用——求解最大特征值及特征向量

将求解高阶矩阵的最大特征值及其对应的特征向量问题转化为高阶非线性方程组的求解问题。在此基础上,提出了求解矩阵最大特征值及其对应特征向量的拟Newton法,给出求解矩阵最大特征值及其单位化向量重新整理后的Broyden方法公式、BFS方法公式、DFP方法公式及其对应的Broyden算法,BFS算法,DFP算法。以层次分析法中高阶判断矩阵为例验证了该方法的可行性,说明了该方法相对收敛速度快的优势。     

用GPU加速求解线性方程组的高斯消元法

提出了应用图形处理器(GPU)加速求解线性方程组的高斯消元法,用二维四通道纹理表示系数矩阵与常数向量构成的矩阵,在该矩阵内完成归一化、消元等操作.提出了新的纹理缩减算法,该算法不要求纹理的边长是2的幂,把该纹理算法应用于高斯消元法的列主元搜索和确定主元行号.根据这些算法,使用OpenGL着色语言编程,用图形处理器实现加速求解线性方程组的高斯消元法,运算时间与基于CPU的算法比较,随着方程组未知量数量增多,基于GPU的算法具有较快的运算速度,证实图形处理器能加速线性方程组的求解.     

分维自适应稀疏网格积分非线性滤波器

针对含加性高斯噪声的非线性离散系统,提出了可分别根据各维状态及量测方程的非线性函数特性来确定采样点及其权重的积分滤波器.设计了基于嵌入式高斯采样积分和稀疏网格法则的自适应多变量采样积分方法,可在匹配函数高阶泰勒展开项时,利用低阶采样点,提出了高效的数据结构和遍历算法,便于采用该积分方法分别估计系统状态/量测的预测均值和协方差矩阵.该滤波器既能根据各维非线性函数的特性确定采样点,又实现了对采样值和权重的完全复用,保证了算法效率.理论分析和仿真表明,该滤波算法中自适应调整的运算量小于计算非线性函数采样值.该滤波器与无迹卡尔曼滤波相比,提高了滤波精度,与固定形式的稀疏网格滤波器相比,提高了采样效率,且该方法为两者的广义形式.仿真实验也验证了状态估计的精确性和函数采样的高效性.     

基于核的双子空间方法及其快速求解算法

针对现有的双子空间方法中存在的问题,提出一种基于核的双子空间判别分析(KDS-DA)方法。此外,还提出一种基于镶边矩阵求逆运算的快速KDS-DA特征求解算法。该算法运用高阶镶边矩阵的求逆运算可转化为低阶镶边矩阵的求逆运算这一性质,使得当顺序求解样本类内散射矩阵主空间中第r+1个KDS-DA判别矢量时,可充分利用求解第r个判别矢量时所得到的计算结果来减少算法复杂度。通过在ORL和AR人脸库上的实验证实文中方法的有效性。     

超音速高阶面元法软件的可扩并行化

计算空气动力学的高阶面元法中，将原来位流升力面理论中求解积分方程的问题近似改成求解一组线性代数方程组。针对系数矩阵的特点，采用与所分网络块对应的数据分配方式，并用部分选主元的Ｇａｕｓｓ－Ｊｏｒｄａｎ算法求逆。分别在４台和８台Ｐｅｎｔｉｕｍ１６６微机组成的并行虚拟机上运行。当矩阵阶达到２１００时，并行效率分别为９５．４％和９１％。     

基于求积分卡尔曼滤波的交互式多模型算法

针对非线性系统中的多模型估计问题,将求积分卡尔曼滤波算法应用到交互式多模型算法过程中,提出一种基于求积分卡尔曼滤波的交互式多模型算法.该算法不需要求取非线性方程的雅可比矩阵,且能够获得比基于不敏卡尔曼滤波的交互式多模型方法更高的滤波精度.仿真结果证明了该算法的有效性.     

基于近似高斯核显式描述的大规模SVM求解

大规模数据集上非线性支持向量机(support vector machine,SVM)的求解代价过高,然而对于线性SVM却存在高效求解算法.为了应用线性SVM高效求解算法求解非线性SVM,并保证非线性SVM的精确性,提出一种基于近似高斯核显式描述的大规模SVM求解方法.首先,定义近似高斯核并建立其与高斯核的关系,推导近似高斯核与高斯核的偏差上界.然后给出近似高斯核对应的再生核希尔伯特空间(reproducing kernel Hilbert space,RKHS)的显式描述,由此可精确刻画SVM解的结构,增强SVM方法的可解释性.最后显式地构造近似高斯核对应的特征映射,并将其作为线性SVM的输入,从而实现了用线性SVM算法高效求解大规模非线性SVM.实验结果表明,所提出的方法能提高非线性SVM的求解效率,并得到与标准非线性SVM相近的精确性.     

基于MPI的不可压缩N-S方程并行计算方法的研究

在目前的计算流体力学问题中,当求解N-S方程等大型科学计算问题时,存在着计算量大、耗时长的问题,对此提出了一种MPI并行算法,其中包括并行求解三对角矩阵与超松弛迭代。通过实例验证,该方法准确、可靠,并且可以大大缩短计算时间,对于大型科学计算问题具有很好的适用性。     

固定结构约束下并行计算关键路径不变的可扩展方法

在固定结构的需求下,并行计算无法通过规模扩展提升其计算性能。针对此类并行计算可扩展问题,分析影响可扩展性的并行任务因素及体系结构因素,采用带权图对并行任务及体系结构进行建模,并提出一种关键路径不变的可扩展方法,其核心思想是固定图结构,仅合理地调整图节点权值和边权值。通过进一步推导,得出一些关于新扩展方法的性质结论。应用网格计算模拟工具SimGrid开展的实验结果表明,所提出的扩展方法能有效解决此类扩展问题,且保持速度效率不变。     

Monte Carlo methods for matrix computations on the grid

Many scientific and engineering applications involve inverting large matrices or solving systems of linear algebraic equations. Solving these problems with proven algorithms for direct methods can take very long to compute, as they depend on the size of the matrix. The computational complexity of the stochastic Monte Carlo methods depends only on the number of chains and the length of those chains. The computing power needed by inherently parallel Monte Carlo methods can be satisfied very efficiently by distributed computing technologies such as Grid computing. In this paper we show how a load balanced Monte Carlo method for computing the inverse of a dense matrix can be constructed, show how the method can be implemented on the Grid, and demonstrate how efficiently the method scales on multiple processors.     

面向低精度环境的安全高速批图像加密

目的 随着存在大量低性能电子设备的物联网系统迅速发展和普及,人们对低精度计算环境下安全高效的图像加密技术有着越来越迫切的需求。现有以混沌系统为代表的图像加密方法不仅加密速度普遍较低,而且在低精度计算环境下存在严重的安全缺陷,难以满足实际需求。针对上述问题,本文提出了一种基于素数模乘线性同余产生器的批图像加密方法,用以提升低精度环境下图像加密的效率和安全性。方法 该方法的核心是构建一个能在低精度环境下有效运行的素数模乘线性同余产生器;将图像集均分为3组,并借助异或运算生成3幅组合图像;接着引入图像集的哈希值更新上述第3组图像;将更新后的组合图像作为上述产生器的输入,进而生成一个加密序列矩阵;基于加密序列矩阵对明文图像进行置乱和扩散,并使用异或运算生成密文图像;使用具有较高安全性的改进版2D-SCL(a new 2D hypher chaotic map based on the sine map, the chebysher map and a linear function)加密方法对加密序列矩阵进行加密。结果 仿真结果表明,本文提出的批图像加密方法在计算精度为2^-8     

基于神经动力学优化的压缩感知信号恢复方法

针对稀疏信号的准确和实时恢复问题,提出了一种基于神经动力学优化的压缩感知信号恢复方法。通过引入反馈神经网络（Recurrent Neural Network, RNN）模型求解l1范数最小化优化问题,计算RNN的稳态解以恢复稀疏信号。对不同方法的测试结果表明,提出的方法在恢复稀疏信号时所需的观测点数最少,并且可推广到压缩图像的恢复应用中,获得了更高的信噪比。RNN模型也适合并行实现,通过GPU并行计算获得了超过百倍的加速比。与传统的方法相比,所提出的方法不仅能够更加准确地恢复信号,并具有更强的实时处理能力。     

Schur法解Riccati方程时的一种加速解法

当前,在解代数Riccati方程的各种方法中,Schur向量法是一种相当有效的算法。Schur向量法的关键在于交换伪上三角形矩阵对角线上的对角块的位置。以前,均使用EXCHNG程序来实现这一交换过程。它用的是QR方法,因而占用了很大一部分计算时间。本文提出用一种直接方法来实现这一交换,可节省一些计算时间。     

一种新的求解最小生成树问题的DNA算法

基于生化反应的生物智能计算是现阶段计算领域研究的热点,DNA计算是通过DNA分子之间的生化反应来进行计算的一种计算模式,凭借运算巨大的并行性和海量存储的优势,DNA计算在解决复杂运算问题方面的计算能力显而易见。设计了一种利用DNA计算来求解图的最小生成树的计算模型,采用一种特殊的编码方式来对顶点,边和权值进行编码,并且描述了MSTP解的计算过程。     

基于边缘计算的智能视频分析算法研究

为适应摄像头在智慧城市、智能交通、自动驾驶等新兴领域应用部署愈加广泛的需求,视频分析需更高精度、更低延时地响应分析结果。然而,这种高精度的分析同时也带来了巨大的计算资源需求,计算资源受限的摄像头无法胜任分析任务。边缘计算不仅可以解决本地摄像头计算资源问题,还可以显著降低向云端传输视频流数据的时间。本文探讨了利用深度强化学习方法,在边缘节点辅助摄像头集群视频分析任务场景下,根据当前网络系统条件动态决策,卸载部分指定摄像头上的分析任务,以在满足任务响应延时的约束前提下,最大化一段时间内任务分析的精度。仿真结果表明,本文提出的方法在任务的响应延时和准确度方面获得了良好效果。     

Solving linear systems in interior-point methods

There are two approaches to solve the linear systems in interior-point methods: the normal equation approach and the augmented system approach. We integrated the two methods by applying matrix partitioning to the augmented system approach. Specifically, we show the Schur complement method which is applied to problems with dense columns is a special case of the augmented system approach. We will use this property for the integrated approach. If we use the integrated approach, we can solve linear systems maintaining sparsity of matrices without respect of the existence of dense columns.Scope and purposeInterior-point methods require a step to solve the linear systems for computing a new direction at every iteration. Generally, we solve the linear systems by applying Cholesky factorization. When there is a dense column, we can not exploit the sparsity of matrices. The most popular way of treating such a dense column employs the Schur complement method or the augmented system approach. The Schur complement method is faster than the augmented system approach, but suffers from numerical unstability. We present a fast and numerically stable approach by integrating former approaches.