基于群论的矩阵乘法问题的搜索算法

发布时间：2017-08-02 23:12

  本文关键词：基于群论的矩阵乘法问题的搜索算法

  更多相关文章： 矩阵乘法 群论 搜索算法 TPP三元组

【摘要】：有史以来,矩阵乘法都是计算机领域的一个重要问题,可以说它在一定范围内限制了计算机的运行效率。在2003年,Cohn和Umans提出了一个实现矩阵乘法的群论方法,它需要在有限群上找出符合TPP条件的个子集或子群。它有效的利用了近似代数群论的知识,这是一个能降低矩阵乘法时间复杂度的全新方法。近些年,也有一些学者做了这方面的研究,但是其中的一些搜索算法还是过于简单和蛮力,受限于当时的条件,他们只找出24阶以内的群的能实现矩阵乘法问题的TPP三元组。本文针对有限群上的TPP三元组的存在情况,先后提出了快速搜索算法、随机搜索算法和进化算法,并分别搜寻群的给定类型的TPP三元组和能实现的最大乘法?(G)。快速搜索算法有效的融合了有利的限制条件,大大缩小了搜索空间,以致于在搜寻6-24群的?(G)时算法效率相比于当前最好的确定性算法而言提升了4-188倍。在此基础又研究了随机搜寻算法,实验结果发现除群上TPP三元组存在密度较低之外整体都优于快速搜索算法。进化算法另辟蹊径,专注于TPP三元组之间的相关性,使基础的TPP三元组(1,1,1)一步一步变换成(n,p,m),实验结果发现进化算法效率比较平稳,在高阶群上的表现较好,故最后利用进化算法搜寻了94阶以内的群的?(G)的存在情况。
【关键词】：矩阵乘法 群论 搜索算法 TPP三元组
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O152;TP301.6
【目录】：

• 摘要5-6
• Abstract6-9
• 第一章 绪论9-16
• 1.1 研究背景和意义9-11
• 1.1.1 群论的起源及发展9
• 1.1.2 矩阵及矩阵乘法的起源及发展9-10
• 1.1.3 搜索算法10-11
• 1.1.4 研究意义11
• 1.2 研究现状11-14
• 1.3 本文主要目的及论文结构14-15
• 1.4 本章小结15-16
• 第二章 基础知识16-20
• 2.1 矩阵及矩阵乘法的定义16
• 2.2 群论基础16-17
• 2.3 基于群论的矩阵乘法问题17-19
• 2.4 本章小结19-20
• 第三章 基于群论的矩阵乘法问题的快速搜索算法20-33
• 3.1 快速搜索算法简介20
• 3.2 算法原理20-21
• 3.3 给定类型 的TPP三元组的快速搜索算法21-27
• 3.4 针对 b(G)的快速搜索算法27-32
• 3.5 本章小结32-33
• 第四章 基于群论的矩阵乘法问题的随机搜索算法33-42
• 4.1 随机搜索算法研究现状33-34
• 4.2 算法原理34-35
• 4.3 给定类型 的TPP三元组的随机搜索算法35-37
• 4.4 针对 b(G)的随机搜寻算法37-41
• 4.5 本章小结41-42
• 第五章 基于群论的矩阵乘法问题的进化算法42-50
• 5.1 进化算法研究现状42-43
• 5.2 算法原理43-44
• 5.3 给定类型 的TPP三元组的进化算法44-46
• 5.4 针对 b(G)的进化算法46-49
• 5.5 本章小结49-50
• 第六章 进一步实验及结果分析50-62
• 6.1 快速搜索算法的确定性50-52
• 6.2 搜索算法的性能分析52-56
• 6.3 进化算法中参数Pop Size,Maxgen的影响56-58
• 6.4 高阶群的实验结果58-61
• 6.5 本章小结61-62
• 总结62-63
• 参考文献63-65
• 附录65-81
• 攻读硕士学位期间取得的研究成果81-82
• 致谢82-83
• 附件83

【参考文献】

中国期刊全文数据库 前4条

1 杨丽娟,张白桦,叶旭桢;快速傅里叶变换FFT及其应用[J];光电工程;2004年S1期

2 贺红;马绍汉;;随机算法的一般性原理[J];计算机科学;2002年01期

3 姚新，陈国良，徐惠敏，刘勇;进化算法研究进展[J];计算机学报;1995年09期

4 包芳勋，，付夕联，张玉峰，张召生;群的概念及其思想方法[J];曲阜师范大学学报(自然科学版);1994年04期

中国博士学位论文全文数据库 前1条

1 张宇山;进化算法的收敛性与时间复杂度分析的若干研究[D];华南理工大学;2013年

中国硕士学位论文全文数据库 前1条

1 邓生杰;2x2快速矩阵乘法问题的完全求解[D];华南理工大学;2011年

本文编号：611640