关于矩阵乘法的一个算法的时间复杂度

两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n³),文献[1]提出一个“运算次数”为O(n²)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n³log₂ⁿ),因而比常规算法的运算量还大.     

二阶矩阵快速乘法的一个新的算法集合

文献[1]—[4]从不同角度研究了二阶矩阵快速乘的各种问题,所有算法分属于以S算法与W算法为基础的两个算法集合.本文作者深入研究了算法的结构和性质,通过计算机检索,得到一个不属于上述两集合的算法和相应的包含有1048576个算法的封闭的算法集合.     

关于整数向量卷积的一个算法的时间复杂度

众所周知,两个n维整数向量循环卷积的常规算法(即按定义计算)的时间复杂度为O(n~2),现在已有时间复杂度为O(nlog_2n)的快速算法,[1]中提出一个新算法,称其时间复杂度为O(n),因而是最佳的。 本文首先指出[1]的错误原因,再根据算法分析理论得出[1]中算法的时间复杂度不低于O(n~2log_2n),因而比常规算法的运算量还大。     

一个无重复生成所有可逆矩阵的算法

在本文中,我们给聘个无重复生成所有可逆矩阵的算法,并估计了该算法的计算复杂度。     

关于矩阵乘法与整数卷积最佳算法运算量的估计

§1.引言 [1]通过构造一个大整数然后作整数乘除法给出了用于有理数矩阵相乘的算法,运算量为O(n~2),达到了矩阵乘法复杂性下界,是最佳算法。[2]曾指出[1]中忽略了不同字长有不同运算量这一事实。但对[1]中算法复杂性未作具体讨论和质疑。最近,[3]—[4]采用类似于[1]中的大整数乘除法分别提出整数向量卷积的算法,并认为运算量级为     

Winograd矩阵乘法算法用于任意阶矩阵时的一种新处理方法

摘要t矩阵乘法StraSsen算法及其变形winograd算法用分而治之的方法把矩阵乘法时间复杂性由传统的D(n。)改进到0(佗kg。n.但是对于奇数阶矩阵,在划分子矩阵时,要作特殊处理才能继续使用此算法.本文提出了一种非等阶“十”字架划分方法,可以最少化填零,最大化性能,使得奇数阶矩阵乘法的时间复杂性更加接近偶数阶矩阵乘法的效果.计算实例显示该方法是有效的.     

Toeplitz矩阵,Hankel矩阵求逆的固有复杂度

对于一类问题P,如果能找到一个算法(对串行计算而言)其计算复杂性为f_1(u),则称f_1(n)为问题P固有复杂度的上界,若问题P的所有算法(对串行计算而言)其计算复杂性不小于f_2(n),则称f_2(u)为问题P固有复杂度下界.问题P的固有复杂度介于上     

对“关于矩阵乘法与整数卷积最佳算法运算量的估计”一文的评注

对“关于矩阵乘法与整数卷积最佳算法运算量的估计“一文的评注张振祥（安徽师范大学教学系,中国科技大学研究生院信息安全国家重点实验室）ＣＯＭＭＥＮＴＳＯＮ“ＥＳＴＩＭＡＴＩＯＮＯＦＴＩＭＥＡＢＯＵＴＴＨＥＯＰＴＩＭＡＬＡＬＧＯＲＩＴＨＭＳＦＯＲＭＡＴＲＩ...     

上三角Toeplitz矩阵的一个结论

本得出了上三角Toeplitz矩阵关于矩阵乘法构成一交换群的结果,并给出其逆矩阵的计算方法．     

Pascal矩阵与Vandermonde矩阵的关系

EI-Mikkawy M证明了对称Pascal矩阵Q_n和Vlandermonde矩阵V_n之间满足矩阵方程Q_n=T_nV_n,这里T_n是一个随机矩阵。本文证明了随机矩阵T_n能够分解成第一类Stirling矩阵和对角矩阵的乘积,得到了矩阵T_n的元素之间的递推关系,从而回答了EI-Mikkawy M的一个公开问题。同时得到了一些与Stirling数相关的组合恒等式。     

用改进遗传算法求解矩阵实特征值

依据矩阵特征值的分布理论,通过确定矩阵实特征值的分布区域,用实数编码和具有自适应交叉概率和变异概率的遗传算法来求解矩阵实特征值的近似值.仿真结果表明,此算法可以达到一定的精度,具有一定的通用性.并给求矩阵特征值提供了一种快速的方法.     

一种求布尔矩阵传递闭包的基于自反矩阵构造的平方算法

首先,介绍布尔矩阵传递闭包的概念及计算问题;随后,分析布尔矩阵的传递闭包和由该布尔矩阵与单位矩阵取并所得到的自反矩阵的传递闭包之间的关系;最后,利用上述结果给出一种求解布尔矩阵传递闭包的基于自反矩阵构造的平方算法,并通过实例说明了其具体计算过程.     

用矩阵方程法求解循环卷积的改进算法

从循环卷积的定义出发,描述了用以m为变量的方法求解循环卷积的步骤.特别详述了其中的矩阵方程法,指出了该方法的不足——含有冗余项,提出了矩阵方程法的改进算法,消除了冗余项,简化了矩阵方程,给出了矩阵方程内部各列的构成规律.实例表明该方法简便、有效.     

周期三对角矩阵逆的一种新算法

给出了一类周期三对角矩阵逆的新的递归算法.新方法充分利用周期三对角矩阵的结构特点,采用递归方法将高阶周期三对角矩阵求逆转化为低阶周期三对角矩阵的求逆.并同时得到简化的计算方法,方法可以有效地减少运算量和存储量,计算精度也有明显的优势.数值实验表明此算法是有效的.     

r-对称循环矩阵及逆矩阵三角分解的快速算法

根据r-对称循环矩阵的特殊结构给出了求这类矩阵本身及其逆矩阵三角分解的快速算法,算法的运算量均为O(n2),一般矩阵及逆矩阵三角分解的运算量均为O(n3).     

一种改进的禁忌搜索算法及其在连续全局优化中的应用

禁忌搜索算法是一种元启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题,提出了一种改进的禁忌搜索算法,并进行了理论分析和数值实验。数值实验表明,对于连续函数全局优化问题的求解该算法是可行有效的,并且结构简单,迭代次数较少,是一种较好的全局启发式优化算法。     

A Class of Inverse Dominant Problems under Weighted l ∞ Norm and an Improved Complexity Bound for Radzik’s Algorithm

In this paper, we first discuss a class of inverse dominant problems under weighted l_∞ norm, which is how to change the original weights of elements with bounds in a finite ground set so that a given set becomes a weakly dominant set with respect to a given collection of subsets under the new weights and the largest change of the weights is minimum. This model includes a large class of improvement problems in combinatorial optimization. We propose a Newton-type algorithm for the model. This algorithm can solve the model in strongly polynomial time if the subproblem involved is solvable in strongly polynomial time. In the second part of the paper, we improve the complexity bound for Radzik’s Newton-type method which is designed to solve linear fractional combinatorial optimization problems. As Radzik’s method is closely related to our algorithm, this bound also estimates the complexity of our algorithm. Supported by the Hong Kong Universities Grant Council (CERG CITYU 9040883 and 9041091). Xiaoguang Yang - The author is also grateful for the support by the National Key Research and Development Program of China (Grant No. 2002CB312004) and the National Natural Science Foundation of China (Grant No. 70425004).     

遗传规划的改进算法

通过改变遗传规划算法中初始群体的生成方法,改变变异策略和修正适应度函数,对遗传规划算法进行了改进,并通过符号回归数值实验对改进后算法的性能进行了测试,且将改进后的算法与改进前以及其它改进算法进行了比较,数值实验结果表明,改进后的算法有效地提高了遗传规划的效率。