ABS算法在Karmarkar算法中的应用

应用ABS算法计算Karmarkar算法中的迭代方向 ,讨论了带有较多或较少约束的线性规划投影矩阵及方向失量的求解方法 ,从而在不同情形下降低了运算量及存储量     

矩阵正定性判别的快速算法

在现代工程计算和统计科学中矩阵正定性的判别具有重要的应用价值.通常,为了判别一个矩阵的正定性,需要求出其所有的顺序主子式或全部的准确特征值.前者的运算量为O(n~4);而至今还没有切实可行的方法来求出矩阵的全部准确特征值.文献[1]利用递推手段给出了判别矩阵正定性的一种方法,使运算量降为 O(n~3).本文应用 Strassen 快速矩阵乘法与快速求逆方法,给出了判别矩阵正定性的一种快速算法.结果表明判别矩阵是否为正定问题的时间复杂度不超过 O(n~(2.81).     

带状Toeplitz方程组的解

本文提出求解带状 Toeplitz 线性方程组的一种新方法.其计算复杂度为O(n(p+q)),而不是一般 Toeplitz 方程组的算法的 O(n~2).这里,n 是方程的阶,p 和 q 分别是上和下半带宽.此外,该方法比用一般的带状 LU 分解方法既节省运算量,也少用计算机存贮.     

求解凸二次规划的新内点算法

对凸二次规划提出了一种基于双障碍三角核函数的大步校正原始-对偶内点算法。通过应用新的技术性引理和这类核函数良好的性质,证明了算法的迭代复杂性为O(n~(2/3) logn/ε),这与目前凸二次规划基于三角核函数的大步校正内点算法最好的迭代复杂性一致。     

非对称代数Riccati方程的一类不精确迭代解法

研究了非对称代数Riccati方程的数值解法.不动点迭代法是求解非对称代数Riccati方程的一类经典算法,然而不动点迭代法在每步迭代中都需要求解一个Sylvester方程,因此运算量比较大.本文对一类不动点迭代法进行了改进,提出了不精确迭代法以求解方程,该方法在外层迭代中使用不动点迭代法,而在内层迭代求解Sylvester方程时使用了Smith算法,进而减少了运算量.理论分析和数值实验表明,本文所提的方法是可行的,而且与基本的不动点迭代法相比,也是较为有效的.     

有限群上几个问题的算法及复杂度分析

本文讨论有限群上几个计算问题。我们设了一个O(n~2)时间的算法去查找n阶Abel群的基底(把n阶Abel群分解为循环P群的直积)。给出了复杂度为O(n~2log_2n)的n阶Abel群的检验算法。证明了n阶Abel群的同构检验可在O(nlOg_2n)时间内完成。最后,我们讨论定义在有限群上的旅行售货员问题:证明了该问题是NP完全的,并给出了一个O(m·n~2·2~n)时间的算法求解它。     

块斜循环矩阵预条件方程组的快速算法

应用快速Hartley变换和快速W变换得到了一种新的求解mn阶块斜循环矩阵预条件方程组的快速算法,其计算复杂度为O(mnlog2(mn)).特别的,当m=1时,新算法所需运算量仅为预优迭代算法的(1/5).     

求解凸二次规划的一个新的全牛顿步内点算法

根据求解线性规划的原始-对偶内点算法的思想,对凸二次规划设计了一种新的全牛顿步内点算法。算法的搜索方向由一个含有线性增长项的核函数确定。利用这个核函数和相应的障碍函数良好的分析性质,得到算法的复杂性阶为O(n~(1/2)lognlog(n/ε),这是目前已知的此类算法最好的理论迭代阶。     

超立方体中过k个指定点的最短路径

利用超立方体的拓扑结构,基于其内部节点编码的特点,分析研究得到在n维超立方体Qn中任意两节点s、t之间经过k(kn)个指定点的最短路径算法.该算法共包括了十个步骤,在最坏的情况下执行2n~2+2n(n~2+2)次运算,算法的时间复杂度为O(n~3),属于多项式计算.     

线性规划的一个新算法

§1 引 言 线性规划通常是用单纯形法求解,即沿约束多面体棱边探索以确定那个顶点为最优解。算法简明但迭代次数随维数比例增大,收敛时程为指数型。因而对大系数来说,就产生改进的Dantzig单形分解法。79年Kauиан把椭球体法应用于线性规划并证明其时程为多项式型、时复杂性为O(n~6L~2),其中n为维数、L为精度的位数。