求矩陣特征值的GPU并行算法的研究.pdf

1、求解矩陣特征值是科學(xué)計(jì)算中經(jīng)常涉及到的問(wèn)題。隨著矩陣規(guī)模不斷增大，串行算法在計(jì)算時(shí)間上無(wú)法滿足人們的需要。采用并行機(jī)或者集群系統(tǒng)可以縮短求解大規(guī)模矩陣特征值的時(shí)間，但是因此會(huì)帶來(lái)設(shè)備成本及耗電量的增加。
　　 為了解決上述存在的問(wèn)題，本文提出了基于CUDA(Computer Unified Device Architecture)的雅可比迭代法求解對(duì)稱矩陣特征值的GPU(Graphic Process Unit)并行算法Hybr

2、id Algorithm(簡(jiǎn)稱HA)，從而克服了傳統(tǒng)串行算法計(jì)算時(shí)間較長(zhǎng)的問(wèn)題。HA算法是結(jié)合本文提出的兩個(gè)并行雅可比迭代法PA-1和PA-2這兩個(gè)算法而提出的。PA-1和PA-2的主要思想都是把串行雅可比算法的求對(duì)稱矩陣非對(duì)角線元素中絕對(duì)值最大者和矩陣更新這兩步利用CUDA并行實(shí)現(xiàn)。PA-1與PA-2算法的唯一不同之處在于求對(duì)稱矩陣非對(duì)角線元素中絕對(duì)值最大者時(shí)采用的算法。HA算法則是結(jié)合了PA-1和PA-2這兩個(gè)算法的優(yōu)點(diǎn)產(chǎn)生的。實(shí)驗(yàn)

3、結(jié)果表明，HA算法比傳統(tǒng)的串行算法運(yùn)行時(shí)間要短，加速比為9.85～13.71。通過(guò)實(shí)驗(yàn)結(jié)果可以看到：隨著矩陣規(guī)模的增加，加速比的總體趨勢(shì)呈上升狀態(tài)；隨著迭代次數(shù)的增加，加速比非常穩(wěn)定。因此，傳統(tǒng)的串行算法的運(yùn)行時(shí)間被顯著減少了。
　　 本文同時(shí)也提出了基于CUDA的求解一般矩陣特征值的QR并行算法PA-QR。但是利用QR算法求解矩陣特征值要先把一般矩陣轉(zhuǎn)化成上H矩陣，因此本文先提出了把一般矩陣轉(zhuǎn)化成上H矩陣的并行算法PA-H。P

4、A-H算法的主要思想是利用CUDA并行實(shí)現(xiàn)一般矩陣轉(zhuǎn)化為上H矩陣的串行算法中的求出第k-1列的第k-1個(gè)以下的元素中絕對(duì)值最大的元素和行交換、列交換以及進(jìn)行變換時(shí)對(duì)行和列進(jìn)行消元變換。PA-QR算法的主要思想就是利用CUDA并行實(shí)現(xiàn)串行QR算法中的4個(gè)一重循環(huán)。實(shí)驗(yàn)結(jié)果表明，PA-H算法的加速比為1.79～7.81，而PA-QR的加速比可以達(dá)到3.24～118.9。并且隨著矩陣規(guī)模的增加，加速比在不斷增加。隨著迭代次數(shù)的增加，加速比非常