本文關(guān)鍵詞：基于群論的矩陣乘法問(wèn)題的搜索算法

  更多相關(guān)文章： 矩陣乘法 群論 搜索算法 TPP三元組

【摘要】：有史以來(lái),矩陣乘法都是計(jì)算機(jī)領(lǐng)域的一個(gè)重要問(wèn)題,可以說(shuō)它在一定范圍內(nèi)限制了計(jì)算機(jī)的運(yùn)行效率。在2003年,Cohn和Umans提出了一個(gè)實(shí)現(xiàn)矩陣乘法的群論方法,它需要在有限群上找出符合TPP條件的個(gè)子集或子群。它有效的利用了近似代數(shù)群論的知識(shí),這是一個(gè)能降低矩陣乘法時(shí)間復(fù)雜度的全新方法。近些年,也有一些學(xué)者做了這方面的研究,但是其中的一些搜索算法還是過(guò)于簡(jiǎn)單和蠻力,受限于當(dāng)時(shí)的條件,他們只找出24階以內(nèi)的群的能實(shí)現(xiàn)矩陣乘法問(wèn)題的TPP三元組。本文針對(duì)有限群上的TPP三元組的存在情況,先后提出了快速搜索算法、隨機(jī)搜索算法和進(jìn)化算法,并分別搜尋群的給定類型的TPP三元組和能實(shí)現(xiàn)的最大乘法?(G)。快速搜索算法有效的融合了有利的限制條件,大大縮小了搜索空間,以致于在搜尋6-24群的?(G)時(shí)算法效率相比于當(dāng)前最好的確定性算法而言提升了4-188倍。在此基礎(chǔ)又研究了隨機(jī)搜尋算法,實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)除群上TPP三元組存在密度較低之外整體都優(yōu)于快速搜索算法。進(jìn)化算法另辟蹊徑,專注于TPP三元組之間的相關(guān)性,使基礎(chǔ)的TPP三元組(1,1,1)一步一步變換成(n,p,m),實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)進(jìn)化算法效率比較平穩(wěn),在高階群上的表現(xiàn)較好,故最后利用進(jìn)化算法搜尋了94階以內(nèi)的群的?(G)的存在情況。
【關(guān)鍵詞】：矩陣乘法 群論 搜索算法 TPP三元組
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O152;TP301.6
【目錄】：

• 摘要5-6
• Abstract6-9
• 第一章 緒論9-16
• 1.1 研究背景和意義9-11
• 1.1.1 群論的起源及發(fā)展9
• 1.1.2 矩陣及矩陣乘法的起源及發(fā)展9-10
• 1.1.3 搜索算法10-11
• 1.1.4 研究意義11
• 1.2 研究現(xiàn)狀11-14
• 1.3 本文主要目的及論文結(jié)構(gòu)14-15
• 1.4 本章小結(jié)15-16
• 第二章 基礎(chǔ)知識(shí)16-20
• 2.1 矩陣及矩陣乘法的定義16
• 2.2 群論基礎(chǔ)16-17
• 2.3 基于群論的矩陣乘法問(wèn)題17-19
• 2.4 本章小結(jié)19-20
• 第三章 基于群論的矩陣乘法問(wèn)題的快速搜索算法20-33
• 3.1 快速搜索算法簡(jiǎn)介20
• 3.2 算法原理20-21
• 3.3 給定類型 的TPP三元組的快速搜索算法21-27
• 3.4 針對(duì) b(G)的快速搜索算法27-32
• 3.5 本章小結(jié)32-33
• 第四章 基于群論的矩陣乘法問(wèn)題的隨機(jī)搜索算法33-42
• 4.1 隨機(jī)搜索算法研究現(xiàn)狀33-34
• 4.2 算法原理34-35
• 4.3 給定類型 的TPP三元組的隨機(jī)搜索算法35-37
• 4.4 針對(duì) b(G)的隨機(jī)搜尋算法37-41
• 4.5 本章小結(jié)41-42
• 第五章 基于群論的矩陣乘法問(wèn)題的進(jìn)化算法42-50
• 5.1 進(jìn)化算法研究現(xiàn)狀42-43
• 5.2 算法原理43-44
• 5.3 給定類型 的TPP三元組的進(jìn)化算法44-46
• 5.4 針對(duì) b(G)的進(jìn)化算法46-49
• 5.5 本章小結(jié)49-50
• 第六章 進(jìn)一步實(shí)驗(yàn)及結(jié)果分析50-62
• 6.1 快速搜索算法的確定性50-52
• 6.2 搜索算法的性能分析52-56
• 6.3 進(jìn)化算法中參數(shù)Pop Size,Maxgen的影響56-58
• 6.4 高階群的實(shí)驗(yàn)結(jié)果58-61
• 6.5 本章小結(jié)61-62
• 總結(jié)62-63
• 參考文獻(xiàn)63-65
• 附錄65-81
• 攻讀碩士學(xué)位期間取得的研究成果81-82
• 致謝82-83
• 附件83

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前4條

1 楊麗娟,張白樺,葉旭楨;快速傅里葉變換FFT及其應(yīng)用[J];光電工程;2004年S1期

2 賀紅;馬紹漢;;隨機(jī)算法的一般性原理[J];計(jì)算機(jī)科學(xué);2002年01期

3 姚新，陳國(guó)良，徐惠敏，劉勇;進(jìn)化算法研究進(jìn)展[J];計(jì)算機(jī)學(xué)報(bào);1995年09期

4 包芳勛，，付夕聯(lián)，張玉峰，張召生;群的概念及其思想方法[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1994年04期

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 張宇山;進(jìn)化算法的收斂性與時(shí)間復(fù)雜度分析的若干研究[D];華南理工大學(xué);2013年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 鄧生杰;2x2快速矩陣乘法問(wèn)題的完全求解[D];華南理工大學(xué);2011年

本文編號(hào)：611640