矩阵条件数及高斯算法平滑分析的进一步研究

下载全文  

算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n³).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ²≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og₂(n)+3log₂(1/σ)+log₂log₂n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og₂n+3log₂(1/σ)+4√2+log₂n+log₂(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n²)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og₂n+3log₂(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.… …   相似文献

杨智应  朱洪  宋建涛 《软件学报》2004,15(5):650-659

基于OpenMP的Winograd并行矩阵乘算法应用研究

下载全文  

为了提高半经典分子动力学模拟中矩阵乘法效率,通过一种稀疏矩阵分解方法化简矩阵乘法,基于OpenMP实现矩阵相乘的Winograd并行算法。该算法将Winograd算法中各部分依次采用OpenMP并行计算,降低了数据通信。在16核服务器上测试表明,该方法能够显著提高半经典分子动力学… …   相似文献

阳光亮  李鸿健  豆育升  唐红 《计算机应用研究》2012,29(7):2435-2437

一种面向可理解性的可复用软件开发方法

下载全文  总被引：3，自引：1，他引：3

本文介绍一种支持软件理解和复用的程序设计方法,以及实现该方法的实验性系统URS—1。  相似文献

董韫美  李开德 《软件学报》1990,1(1):31-38

基于Level Set方法的曲线演化

下载全文  总被引：13，自引：0，他引：13

Level Set方法是一种描述曲线以曲率相关的速度演化的有力工具,最近几年在医学图像处理、自然现象的模拟以及计算机视觉等领域得到了广泛的应用.其中,曲线演化后的平滑算法和轮廓跟踪方法是Level Set方法实际应用中的两个关键算法.给出了一种平滑Level Set距离函数的简单… …   相似文献

杨猛  汪国平  董士海 《软件学报》2002,13(9):1858-1865

改进的分块算法在矩形图像加密中的应用

下载全文  

为提高图像加密算法抵御穷举攻击、统计分析攻击及差分攻击的能力,提出了一种改进的基于混沌的分块图像加密算法,并用于矩形灰度图像加密。该算法通过对外部密钥分组生成Logistic映射初始条件并迭代生成混沌序列,有效增强了密钥的敏感性。提出三向散布并结合像素值替代算法能够明显增强算法抵… …   相似文献

孙劲光  汪洁  姜文涛  孟祥福 《计算机应用研究》2013,30(1):282-284

一种基于二叉树结构表达的矩形物体布局的启发式方法

下载全文  总被引：14，自引：2，他引：14

本文提出了一种利用二叉树结构表达矩形物体布局状态空间的方法．通过将布局空间依次分割,每次放入相对于当前布局空间来说是满足特定条件的最优布局块,并将该布局块定位于当前布局空间的左上角来完成不同大小矩形物体的布局方案的确定．通过调整调序因子ＫＡ和ＫＢ的值,可得到满足不同要求的优化布局… …   相似文献

王爱虎  查建中  王金敏 《软件学报》1996,7(4):252-257

基于Web的刀具全生命周期管理的研究与实现*

下载全文  总被引：2，自引：0，他引：2

首先介绍刀具全生命周期管理系统的概念以及我国制造业对其的迫切需求,然后对刀具全生命周期管理系统中的关键技术展开研究,主要包括刀具信息编码技术、刀具标识技术以及车间分布式数字控制技术。最后运用面向对象的思想对刀具全生命周期管理系统进行系统的分析和设计,并遵循J2EE模式介绍了刀具全… …   相似文献

王苏安  何卫平  房亚东 《计算机应用研究》2006,23(5):128-130

基于混合势场法的移动机器人路径规划

下载全文  

针对目前移动机器人在路径规划中出现的问题,提出一种自主移动机器人路径规划的新方法——混合势场法.分析了人工势场法的不足,找出局部极小值点的形成原因;针对人工势场法中障碍物附近目标不可达问题,采用了在斥力场函数中加入斥力因子,使得机器人顺利到达目标点;针对陷入局部极小值和振荡的问题… …   相似文献

王梅  王叶婷  屠大维  江济良  张国栋 《计算机应用研究》2012,29(7):2447-2449

对一种新的序列密码结构的密码分析

下载全文  

对新提议的一种基于线性反馈移位寄存器、非线性反馈移位寄存器和过滤布尔函数的序列密码结构的安全性进行了研究,对这种结构给出了一种区分攻击.举例子说明了此攻击的有效性.这种新的攻击表明,此种新的序列密码结构存在潜在的安全弱点.  相似文献

黄小莉  武传坤 《软件学报》2008,19(5):1256-1264

针对环状流形数据的非线性降维

下载全文  总被引：1，自引：0，他引：1

近年来出现了多种新型的非线性降维方法,且在一些应用中体现出良好的效果.然而,当面对球体、柱体等环状流形产生的非线性流形数据时,这些方法往往会失效.针对这一问题,提出了针对环状流形数据的环结构检测算法与非线性降维方法.理论上,基于目前极受关注的Isomap降维方法的运行原理,给出了… …   相似文献

孟德宇  古楠楠  徐宗本  梁怡 《软件学报》2008,19(11):2908-2920