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

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

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

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

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

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

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

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

保持矩阵迹的乘法映射

设F是一个域 ,An,是一个乘法半群且满足 {aEij|i,j=1 ,2… ,n ,a∈F} An (F) ,其中Mn(F)定义F上所有n×n矩阵组成的乘法半群 ,本文证明了一个结果 :若f:AnF是一个保迹映射 ,则存在一个可逆阵P∈Mn(F)使得f(A) =PAP- 1 , A∈An由此推广了 [1 ]的一个结果 .     

矩阵乘法不满足交换律的解释

一般地,AB≠BA.它"是什么"众所周知,而"为什么"通常不被重视,或重视程度不够.介绍AB≠BA的一个具体解释,试图说明它不是哪个数学家空想出来的,而是建立在有关实际应用的基础之上.     

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

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

分布式系统上并行矩阵乘法

1．引言矩阵乘法是最简单的数学问题,同时由于其计算量大而通常被用来对计算机的浮点运算速度进行测试,尤其是对于并行计算机,其并行效率的好坏可通过这个简单的问题反应出来,如果在这个问题上都不能取得很好的效果,对于其它问题就更不可能．此外,为了提高计算性能,对求解数值代数中的问题最终会归结到有矩阵乘法的计算,如LAPACK,ScaLAPACK等,因此有效地并行计算矩阵乘法在实际应用中是非常重要的．矩阵乘法是做C＝A×B,其中A是m×k阵,B是k×n阵,C是m×n阵．设矩阵A,B可以分成p×p块矩阵,即A＝（Ai,j）p×p,B＝（B…     

一类无穷矩阵代数的乘法序列连续性

设λ，μ是两个序列空间并有符号弱滑脊性，（λ，μ）是变换λ进入μ的无穷矩阵算子所成的无穷矩阵代数，本文研究了这类代数的强，Mackey、弱乘法序列连续性问题。     

矩阵Hoffman-Wielandt型乘法相对扰动界

<正>1引言设A是一个方阵,(?)是它的扰动矩阵.特征值的加法扰动和乘法扰动是矩阵特征值的两种不同类型的扰动.当(?)=A+E时,称(?)是A的加法扰动矩阵;当(?)=D_1~*AD_2时,其中     

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

两个ｎ阶非负整数方阵相乘,常规算法的时间复杂度为Ｏ（ｎ^３）,文献［１］提出一个“运算次数”为Ｏ（ｎ²）的“最佳”算法,文献［２］对此算法做了进一步研究,提出三种改进策略．本文根据算法分析理论,得出改进后的算法的时间复杂度仍不低于Ｏ（ｎ^３ｌｏｇｎ）,因而其阶仍高于常规算法的运算量的阶．     

半环上的三角矩阵乘法半群的自同构

设R是含有恒等元1的半环,C是R上的中心子半环.Tn(R)是R上的n阶上三角矩阵C-代数.证明了当R是一个幂等元都是中心元的半环时,映射Φ:Tn(R)→Tn(R)是乘法半群自同构当且仅当存在Tn(R)中的可逆矩阵G和R中的半环自同构τ使得A=(aij)n×n∈Tn(R),均有Φ(A)=G-1τ(A)G.这里τ(A)=(τ(aij))n×n,n2.     

为《简易快速乘法》增补模式

关于乘数为9的《简易快速乘法》，在《黑龙江珠算》1988年1、3、6期先后发表四篇(包括6期上“连续数乘9的速算”)有关算理算法的文章。速算任何数乘以9，大部按“扩十减一”(10—1)来运算的，实际计算程序、在于原数顺序的后位减前位的差数．即得所求之积。上列文章所述算法，是抽出特定数字的特殊固定模式，这样，确实给予计算者的规律明显，反映敏捷，提供计算更加快准的技巧。比如：相同数字在被乘数的首部或中间．其后位数大．其积为0；其后位数小、其积为9；如果相同数字在被乘数的末尾．其积肯定是9；而且所出现的“0”“9”的个数，一律是比相同数字的个数少1。     

r－轮换矩阵快速求逆算法的推广

ｒ－轮换矩阵快速求逆算法的推广成礼智（国防科技大学）ＴＨＥＧＥＮＥＲＡＬＩＺＡＴＩＯＮＯＦＴＨＥＦＡＳＴＡＬＧＯＲＩＴＨＭＦＯＲＩＮＶＥＲＴＩＮＧｒ－ＣＩＲＣＵＬＡＮＴＭＡＴＲＩＣＥＳ￥ＣｈｅｎｇＬｉ－ｚｈｉ（ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆ...     

广义延拓矩阵在乘法扰动下特征空间的相对扰动界

在矩阵A与其扰动矩阵A有相同分块的谱分解下,对于以A为母矩阵的广义延拓矩阵凡（A）及以A为母矩阵的广义延拓矩阵凡（A）,使用特征值双分离度方法,给出了广义延拓矩阵n（A）与其扰动矩阵n（A）的特征空间在乘法扰动下的相对扰动界．     

Vandermonde方程Hilbert方程及Vandermonde矩阵Hilbert矩阵逆的快速与并行算法

1.引言 众所周知,在并行数值代数研究中,降低矩阵求逆与线性方程组求解并行步是一个相当困难的问题。1976年Csanky证明了上述两问题均可在O(log~2n)并行步内完成,所用处理机台数为O(n~4)。然而能否找到时间步为O(logn)的并行算法,长期以来是人们极为关注的问题之一。对于特殊矩阵及方程的研究更是如此。目前除几个极其特殊的