快速求解Lyapunov矩阵代数方程AтX+XA=-Q的Schawarz形法

本文把矩阵A相似变换为Schawarz形，得到了快速求解Lyapunov矩阵代数方程AтX+XA=-Q的一种新算法——Schawarz形法。该法只需12.5n3+O（n2）次乘除运算，3.5n2+ O(n)个存贮单元，比现有文献提供的算法要求的乘除次数与存贮单元均降低了几个数量级。用Schawarz形法还可以判断矩阵A的渐近稳定性。     

关于Vandermonde矩阵的串行与并行复杂性

为n+1阶Vandermonde矩阵,简称V阵。 本文首先给出求解相应线性代数方程组(简称V型方程组)的递推算法。算术运算总次数为O(n~2)级,接着进一步利用快速插值算法导出求V阵逆的O(n~2)算法,并分析了这两种算法的并行时间复杂性。     

二分图最大匹配问题的分布式算法

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n~2+m))、时间复杂性为 O(n~3);第二个算法的通讯复杂性为O(n~(1/2)(n~2+m))、时间复杂性为O(n~(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。     

复矩阵乘法的并行计算

<正> 在矩阵计算中矩阵乘法是最基本的。一个好的矩阵乘法算法往往能大量节省求解线代数问题的计算时间。如Strassen算法的问世就使线代数方程组求解、行列式求值等的运算量,从0(n~3)下降为O(n~(2.81))。不少领域中经常遇到复矩阵的乘法,而到目前为止讨论这一问题的并行算法的文章甚少。本文提出两类计算方法并讨论了各种算法的性能、并行时间复杂性及其误差分析。一、化为实短阵乘法的算法类众所周知,若A、B、C、D是实域上n阶全矩阵环中的元素,则成立互等式(A+B_i)(c+D_i):(Ac-BD)+i[(A+B)(c+D))-Ac-BD] (1)     

网孔处理机阵列上最小生成树算法

已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n~2/p)时间,使用了O(p)个处理机(1≤p≤n).当p=n时,此算法仅需O(n)时间和O(n)处理机.而目前基于同一计算模型上此问题的最好算法需O(n)时间和O(n~2)个处理机,因而这里给出的算法在使用处理机数目方面改进了O(n)因子.     

稀疏对称高斯消去法的两个算法

设A是对称正定的稀疏矩阵,我们用高斯消去法解方程组: Ax=b.(1)当A是带形矩阵时,一般可用一维存贮的变带宽算法求解.但在许多实际问题中,例如电网络问题及某些有限元问题,出现的稀疏矩阵不具有带形结构,而是根据存贮量或运算量优化的某种准则,排列矩阵各行所产生的具有随机分布稀疏结构的矩阵.本文主要讨论当A具有这种稀疏结构时,如何用对称高斯消去法结合上三角按行索引存贮技术去解     

LCS问题的一种新算法及其推广

求解LCS(Longest Common Subsequences)的通常算法,空间和时间的复杂性为O(n~2)。本文中提出的算法,空间复杂性为O(n),时间复杂性为O(n)～O(n~2),时间复杂性取决于序列中符号的分布,本算法便于并行处理及制成微处理器。 为了应用于模式识别,推广到WLCS(Weighted Longest Common Subsequences)以及LCSM(Longest Common Submatrix)。 给出了有关的定理,及算法正确性的证明。     

多队列快速排序

快速排序算法的平均时间小于所有已知的O(nlogn)排序算法。它的平均时间是O(nlogn),最坏情况为O(n~2)本文提出的算法对n个元素的排序时间为O(nlogm),其中其最佳性能为O(n)在M 16计算机上运行的结果符合文中给出的算法分析     

n 个规格化数的最优排序算法

<正> n 个实数的排序是最经常遇到的问题之一。目前常用的排序方法是“泡沫分类法”,用 ALGOL60书写,形式为for j:=n-1 step-1 until 1 dofor i:=1 until j doif A[i+1]相似文献   

矩阵的广义Schwarz形和多项式矩阵的稳定性

本文通过线性变换,对具有一般形式的多项式矩阵,建立了广义Routh数组和广义Schwarz形的概念,给出了由矩阵块状相伴标准形到广义Schwarz形的变换阵,利用Liapunoff第二定理,得到判别多项式矩阵稳定的充分条件,并把此结果运用到多变量控制系统中。     

一个求图的连通分支的并行算法

已知一个无向图G(V,E),|V|=n,|E|=m,本文基于SIMD共享存贮模型,运用数据在图中快速传播原理,建议了一个新的求图的连通分支算法,具体来讲,在SIMD—CREW共享存贮模型上,求图的连通分支需O(log²n)时间、O(n²/logn)处理器;而在SIMD—CRCW共享存贮模型上需O(logn)时间、O(n²)处理器,建议的算法同著名的Hirschberg算法相比,其主要差别表现在:1)采用的求解方法不同;2)建议的算法简单易懂     

快速算法及矩阵的新式分解

本文根据文献讨论了矩阵∑LU 分解法的普遍意义,详细分析了文献提出的新算法的步骤及算法的复杂性,并对它们作了补充和订正。本文指出,新算法的乘法复杂性为O(N log~2 N);加法复杂性为O(N~2);空间复杂性为O(N~2)。本文还探讨了该算法的几个实际问题及适用范围。算法已在HP-3000计算机上用PASOAL 语言程序实现。     

单管MOS存贮单元的存贮阵列和读出-再生电路

简介——破坏读出单管MOS存贮单元的读数信号随单元面积减小而减小。要达到必要小的单元面积,必需具有大的特殊电容的器件作为存贮电容器,还需要灵敏的再生放大器和补偿噪音的阵列。 对于用硅栅工艺的单元布局设计,存贮电容器建议采用电场感应的非平衡反型层作为一个电极。 提出一个门控触发器作为一个灵敏的再生放大器,它的两个输入结点各连接一条位线。这样得到的对称阵列不但是高度灵敏的(输入电压差的不可辨区大约定晶体管阀值电压的0.3)和与制造工艺参数不相关的,而且容许在触发器的每边用一条假的字线(带有假的存贮单元)进行噪音补偿。 不同的单元和再生电路已经用硅栅工艺实现。面积为1600微米~2(2.6密耳)~2的存贮单元已经成功地进行工作,读/写周期时间为350毫微秒(存贮电容为0.134微微法,每条位线64个单元或每个放大器128个单元的位线电容为0.32微微法)。     

一个新的多项式实根分离算法

本文提出了分离多项式方程P(x)=0的实根的一个新的计算机代数算法,它解决了王湘浩教授在[1]中提出的用连分数变换分离有重根多项式的实根的问题.对于有重根的n次多项式P(x),该算法具有时间复杂性上界O(n~6L~3(|P|_0)),远远优于现有的解决同样问题的计算机代数算法的时间上界O(n~(10)+n~7L~3(|P|_0)).该算法已在计算机代数系统SAC-2上实现.上机实验的结果也初步证实了新算法的优越性.     

平均分类(Meansort)算法

本文给出了一个基于快速分类(Quicksort)算法的高效算法。人们已经知道,快速分类算法是最有效的分类方法之一。但是,这种方法有一个缺陷,就是在最坏的情况下要进行 O(n~2)次比较。本文给出的算法改进了快速分类算法的平均性能,减少了最坏情况的发生。     

转置大矩阵的快速算法

本文是介绍一种转置2~n×2~n数据矩阵的算法,矩阵是大于现有的主存容量,数据存放在可以直接存取的外存贮设备上。算法的性能与主存的容量有关,至少应该能存放2~(n+1)数据点。实现矩阵转置,必需读写n次矩阵。     

不存贮总刚度矩阵的迭代解法

应用有限元方法解椭圆型边值问题的一类数值解法,最后都归结为解一个n阶线性方程组.这个方程组的系数按矩阵的形式排列,称为总刚度矩阵(例如位移法).尽管总刚度矩阵是稀疏和对称的,但用半带宽或变带宽来存贮它仍需占用计算机大量的存贮单元,使得中小型计算机难以求解这类大型结构的问题.本文将介绍不存贮总刚度矩阵的迭代     

连接依赖子类可满足性的多项式测试

测试一个关系是否满足所给的依赖,这在关系数据库设计中是很重要的。本文定义了一些连接依赖子类:顺序连接依赖,广义顺序连接依赖,环形连接依赖,广义环形连接依赖和梯形连接依赖,前二类依赖可满足性测试算法时间复杂性是O(n~2logn),后三类依赖可满足性测试算法时间复杂性是O(n~4)。目前所定义的应用范围比连接依赖小的所有依赖都包含在这里所定义的连接依赖子类中。     

充分利用局部有序的快速排序

1984年R.G.Dromey提出了在快速排序中利用部分有序的算法。本文对他的有序性概念进行了扩充。改进后的算法充分利用了排序数据的有序性。算法的最佳性能为o(n),最坏情况为O(n~2)。因此本算法优于快速排序和TRANSORT。     

有限群上几个问题的复杂性分析

本文,我们设计了一个O(n~2)时间的算法,去求n阶Abel群的基底;即把n阶Abel群分解为循环P群的直积。接着,我们讨论有名的群同构检验问题,洪加威O(n)时间的n阶Abel群同构检验算法也列入本文(洪加威教授提供)。最后,我们证明有限群上流动售货员问题是NP-完全的;并给出O(m~2·n·2~m)时间的算法求解这个问题,这里n为群的阶,m为图中结点个数。