广义Hilbert矩阵与向量积及一类广义Hilbert方程解的计算复杂性

P为正整数,t_i,s_i(i=1,2,…,n)为复平面上不同的点。文献[1]引述了如下问题:“任给n维向量b,是否存在算术运算次数少于O(n~2)的计算矩阵向量积B_1b的算法”,Gerasonlis研究了上述问题的推广形式,即计算B_pb,在P(?)n的前提下,证明了矩阵向量积B_pb所需     

O(n)时间有限Abel群同构检验算法

计算群论和复杂性理论中的一个重要问题是,有限群同构检验是可行的,还是NP完全的?这个问题迄今没有解决。C.Savage和陈溧分别得到一个O(n~2)时间的n阶Abel群同构检验算法。 本文得到,存在O(n)时间的n阶Abel群同构检验算法。即使使用对数成本的RAM,完成这样     

关于矩阵乘法的一个最佳算法

一、引言 文献中提出一个适用于有理数矩阵乘法的算法,指出对于m列n行矩阵和m行t列矩阵的乘法,运算的次数阶为0(m(l+n)),作者称之为最佳算法,本文将指出文献的算法忽略了不同字长有不同运算量这一事实,如果承认文献的观点,则利用补零和截位技术仅需用一个乘法就能实现二个非负整数矩阵的乘法。     

Fuzzy分块矩阵的一个定理

式(2)中的符号O是指Fuzzy矩阵的乘法运算(或称合成运算)。接着,作者证明了关于Fuzzy分块矩阵乘法的一个定理:     

DNA缩短法计算模型求解最大独立集问题

提出了一种基于环形DNA缩短法的新型计算模型. 该模型可以求解n个顶点m条边的图的最大独立集. 算法的时间复杂度是O(n+m). 随着问题规模的增大, 计算所需的试管数量呈线性增长. 在计算模型的生物操作中, 有两个主要技术: DNA分子内环化和DNA长度逐步缩短. 结合反向PCR(聚合酶链式反应), 磁珠吸附和环化酶催化等多种方法, 在求解步骤中, DNA分子的结构在线性双链DNA(dsDNA)、线性单链DNA(ssDNA)和环形单链DNA之间进行循环变化. 利用环形DNA分子的结构特点, 在计算过程中避免了DNA分子间重组. 为了证实该DNA计算模型的可行性, 利用其求解了一个最大独立集问题的实例.     

矩阵正定性的判定及线性方程组AX=b的反问题求解

对称正定阵是一类很重要的矩阵,目前判定一对称阵是否正定,可以由求它的所有顺序主子式或求出它的全部准确特征值来判定。但求所有顺序主子式运算量太大(O(n~4)),而求其准确特征值又没有有效的一般方法。随着数学本身及应用矩阵的其它学科的需要,有不少人从事研究未必对称的正定阵和更为广义的正定阵,文献[1]对广义正定矩阵作了大量有益的工作。     

矩阵代数∑(α,β)的强拓扑乘法连续性

乘法连续性是拓扑代数的一个基本问题。1978年,作者之一(数学学报,21(1978),2:161—170)讨论了完备矩阵代数Σ(α)的乘法连续性。本文在我们所引入的更广泛的矩阵代数∑(α,β)(哈尔滨工业大学学报,1984,增刊)类的框架下进一步研究     

矩阵的半张量积: 一个便捷的新工具

矩阵的半张量积是一种新的矩阵乘法. 它将普通矩阵乘法推广到前阵列数与后阵行数不等的情况. 推广后的乘法不仅保持了原矩阵乘法的主要性质, 而且, 具有伪交换性等比推广前更好的性质. 因此, 这是一个便捷而有力的新的数学工具. 在简单介绍它的历史、定义和主要性质之后, 本文对半张量积的本质及其优越性进行了分析, 从而揭示它的合理性及有效性.接着, 着重介绍它在若干领域的应用. 包括(1) 非线性(控制)系统的半张量积方法; (2) 布尔网络的结构分析与控制; (3) 半张量积在数学、物理中的其他应用. 最后, 本文对目前在研及可能突破的问题作了一个较详细的介绍, 并对其潜在应用前景作了展望.     

带框矩阵及其在图论中的应用

本文提出带框矩阵及其乘法.在图论中,用带框矩阵乘法可充分必要地判定与求出某图是否存在Euler 通路或环路,是否存在Hamil-ton 通路或环路.定义1 矩阵A~k=(a_i~kj)_(m×n)的带框矩阵记为A~k,表示为:     

低复杂度Chase-2型级联码译码器

由里德-所罗门码(RS码)和递归系统卷积码(RSC)组成的级联码被广泛应用于现有的通信系统中, 如卫星通信系统和WiMAX系统. 介绍了一种用于这类级联码的低复杂度迭代软判决译码算法. 通过减少测试图样的使用数量, 对chase-2型算法进行了简化, 达到了减少运算复杂度的目的; 此外, 通过改进内外码解码器之间软信息的处理方法, 增加了软信息的使用效率, 改善了译码性能. 仿真结果表明, 改进型译码算法在性能和计算复杂度上取得了良好的平衡.     

基于线性自组装的DNA减法模运算

使用线性自组装方法, 提出了两个非负二进制整数减法模运算的DNA算法. 对于两个表示为n位的二进制数A与B, 算法给出A-B在模2n情况下的运算结果. 算法中包含反应被减数与减数大小关系的扩展借位信息, 从而在计算前不必对A与B的大小关系进行预分类. 结果反应链中包含运算结果、每一步借位信息、参与运算的数值、判断被减数与减数大小的标志位等信息. 算法充分利用DNA反应的并行特性, 在给定两个被减数集与减数集时, 可进行两个集合的减法模运算的并行计算. 算法的可行性基于已知的DNA算法实验. 算法具有良好的自发反应特性, 避免了人工操作随运算数值位数增长的情况, 对于计算位数n, 在本算法中参与反应的单链库规模为O(n), 生物操作复杂度为常数.     

m序列扩展及一类M序列快速生成

由于m序列数量少、线性复杂度小,不能满足保密通信等需要。M序列虽已得到了深入研究,但许多产生M序列的算法因需要大量存储空间或计算时间而不实用,对k>2,仅有两个产生k进M序列的有效算法。设U为GF(q~m)上周期为q~(mn)-1的序列全体,PN删     

S~7上无Lie群构造

广义特征值问题 Ax=λBx (1.1)其中A,B是n×n实对称矩阵,是矩阵论和计算数学中的基本问题之一。熟知,当B是正定矩阵时,(A—λB)的顺序主子式形成一Sturm序列。基于这个性质产生了一些著名的算法,如Givens方法,Gupta方法。     

坡矩阵的特征向量(Ⅱ)

关于坡矩阵的特征向量问题,最早获得解决的是布尔矩阵,于1966年由Blyth解决的。而后,作者解决了分配格矩阵的情况。并改进为与Blyth的定理完全一致的形式。在文献[3]中对于一些特殊的坡矩阵也给予了彻底的解决。本文是文献[3]的继续,主要讨论乘法运算不是半格运算的坡上的矩阵特征向量问题。例如:([0,1];V,*)上的矩阵,其中*可以是     

在孤立分子MO基组下自洽场计算程序和应用

作者根据线性代数理论的证明编制了可以将SCF-LCAO量子化学计算所得结果只作矩阵乘法便转换成孤立分子MO基组下结果的程序(图1)。它避免了文献中报道的需要对孤立MO进行正交化处理等繁琐过程并可方便地和各种SCF-LGAO程序联用。具有灵活、简便之特点。     

非线性最优化一个超线性收敛的序列方程组方法

本文考虑如下的优化问题:这里x=(x_1,…,x_n)∈E~n.对于问题(P),本文给出了一个超线性收敛的序列方程组算法.此算法与现有的序列二次规划(SQP)方法相比,具有以下三个重要的性质:(1)由于算法每一次迭代只需计算三个系数矩阵完全相同的线性方程组,因此算法每一次迭代的计算量要比现有的SQP方法大为减少;(2)算法每一次迭代产生的点都是可行的;(3)算法是一步超线性收敛的.     

复杂度理论中某些不可证明的真命题

在复杂度理论研究中,上界不断被改进,但下界的研究却迟迟没有重要进展。对于任何一个NP完全性问题,现有最好的算法也需要指数的时间,但数学家们费尽九牛二虎之力也只能证出一个线性时间的下界。这使我们想到:复杂度理论中的许多真命题是不可证明的。但如果只是并行于Gdel的不完全性定理,得出一些诸如:“下界是2。但不可证”的结论,仍不能说明真实下界与理论下界之间的巨大差距。我们得到了下面的结果:定理1设,f(n)≥n是任一时间可构造的函数(例如2~2~m),A是一个可以用谓词P(c)表示“程序c的时间复杂度t(n)不会低于一个常数”的公     

本征值问题的有限元方法的加速

算子本征值问题的有限元离散必然导致大型矩阵的广义特征值问题。这种问题很难计算。因此,研究这方面的加速算法很有理论与实际意义。目前,在矩阵特征值计算方面已有了较多的研究。而本文是从算子本征值问题的离散过程来研究的。在冯康教授的启示下,把文献[1]中关于非线性方程加速收敛的思想推广到算子本征值问题,提出了关于算子本征值问题的一种加速计算方法。     

电子计算机串并行运算器乘除运算的一种新方法

七十年代小型和微型电子计算机的串并行运算器,都采用子程序法进行乘除运算,这种方法运算速度低,因此在高速过程控制中不能采用,比如在武汉1700工程中,由于数千次的调用乘法和除法子程序,使轧钢系统在出现断带事故情况下,实现紧急停车所需时间,比设计中规定的时间增加了大约28％.为了改变这一现实,使串并行运算器有一种较理想的乘、除算法,作者首次提出了“舍弃乘法原理”和“分组耗尽除法原理”.舍弃乘法,即二进制定点乘法在串并行运算过     

关于形心连线方向法

1.考虑n元函数f(x),要求它的局部极小.本文提出的形心连线方向法是一种以积分作为工具的方法,它的优点是可以处理不可微函数.从表面来看,积分计算显然比求导计算工作量大得多,但是如果要求的精度不高,用蒙特卡罗方法来实现,其计算量与维数无关,内存要求也小.然而,求梯度的运算和内存随维数n增长,求二阶导数矩阵则随n~2增长.