论文部分内容阅读
矩阵乘法的算法复杂度分析是计算理论中一个重要问题。我们首先介绍了这一方面的开创性工作—Strassen算法;接下来介绍了矩阵乘法的群论方法和其中的一些重要的概念、相关性质以及两个可以推出ω=2的猜想,给出了一些具体群的已有构造验证和新的构造并由新构造推导出一个ω的非平凡上界,然后介绍了搜索极大三乘积组的蚁群算法;接下来介绍5×5小矩阵乘法的群理论方法并研究了6×6小矩阵乘法的群论方法;最后研究了一种特定情形下三乘积组的构造原则及其在两个群结构上的具体应用。 本论文的主要结果总结如下:一是针对已有的例子(具体群结构及其三乘积组)进行扩充构建得出一些新的同时二乘积组或三乘积组,并由扩充构建的例子推导出一个ω的非平凡上界ω<2.9262。二是证明了群的西罗子群组的三乘积性质和二乘积性质。三是在6×6小矩阵乘法群理论方法的研究中,提出了若干群的<6,6,6>三乘积性质的必要条件,从而较大地缩减了问题的搜索空间。四是针对几个具体群给出了它们的三乘积组具体结构:构造证明了4阶偶置换群A4的<3,3,2>三乘积性质,给出并证明了该群的三乘积容量的确切值,然后由此结论抽象构造了群C6×A4的<6,3,3>三乘积组(这里C6是6阶循环群),接着给出了该抽象形式的一个具体解;构造证明了群C3×A4的<6,4,3>三乘积组(这里C3是3阶循环群)。五是从理论上探讨了抽象群B的三乘积性质与群C2×B、C3×B和Cn×B的三乘积性质之间的联系并将理论成果应用于两个具体群的<6,6,6>三乘积性质的研究(这里C2是2阶循环群),得到了有关1×B与2×B在群C2×B的<6,6,6>三乘积组中具体分布的一些结论(这里1,2∈C2且1是其中的单位元)。