矩陣特征值的多核并行求解算法及設(shè)計(jì)研究

黃麗嫦 林結(jié)

摘? ?要：特征值及其特征向量的求解問題一直是現(xiàn)代數(shù)值分析的研究熱點(diǎn)，在多核架構(gòu)的微機(jī)中，文章基于Householder變換提出了一種高效的矩陣QR多核并行分解方法，在此基礎(chǔ)上，設(shè)計(jì)實(shí)現(xiàn)了矩陣特征值的多核并行求解算法。數(shù)值實(shí)驗(yàn)驗(yàn)證了新設(shè)計(jì)算法的可行性和有效性。

關(guān)鍵詞：Householder變換;特征值;正交三角分解;多核并行計(jì)算

1? ? 矩陣特征值及其牲向量介紹

工程技術(shù)和科學(xué)研究中的諸多問題，通常可以歸結(jié)為求解某一矩陣的特征值及其對應(yīng)的特征向量。設(shè)給定的矩陣A∈Rn×n，若存在非零向量x∈Rn及常數(shù)λ∈R，使得：

Ax=λx（1）

若式（1）成立，則稱常數(shù)λ為矩陣A的特征值，而非零向量x則為對應(yīng)于λ的特征向量。在實(shí)際應(yīng)用中，求解矩陣的特征值及其對應(yīng)的特征向量的數(shù)值算法可以分為分解法和迭代法兩種[1]。分解法將原矩陣分解為較容易求出特征值的形式，該類方法的優(yōu)點(diǎn)是算法的計(jì)算效率較高，而缺點(diǎn)就是受舍入誤差的影響，導(dǎo)致計(jì)算精度不高。迭代法則是將特征值及其對應(yīng)的特征向量作為一個(gè)無限序列的極限來計(jì)算，由于以逼近誤差來控制迭代的次數(shù)，故算法在嚴(yán)格收斂的條件下具有較好的計(jì)算精度，而缺點(diǎn)就是迭代過程中需要消耗一定的計(jì)算成本。矩陣的QR分解是工程應(yīng)用中最廣泛的一種矩陣分解，是矩陣特征值的重要求解方法，注意到目前的微機(jī)普遍具有多核架構(gòu)計(jì)算環(huán)境，為此本文擬采用Householder變換的方法，在多核微機(jī)中設(shè)計(jì)實(shí)現(xiàn)了一種基于QR分解并行的矩陣特征值求解算法。

2? ? 基于QR分解的特征值求解及Householder變換

2.1? 基于QR分解的特征值和求解矩陣的QR分解原理

引理1：若A∈Rm×n，且m≥n，則存在正交的矩陣Q∈Rm×n和上三角矩陣R∈Rm×n，使得式（2）成立[2]：

2.3? 矩陣的Householder變換

常用的QR分解算法有基于Gram-Schmidt正交法的QR分解、基于Householder變換的QR分解以及采用Givens旋轉(zhuǎn)的QR分解，相對而言，由于Householder變換具有較少的計(jì)算量，為此本文擬采用基于Householder變換來實(shí)現(xiàn)矩陣的QR分解。

2.4? 基于Householder變換的QR分解

基于Householder矩陣變換，可以實(shí)現(xiàn)任意m×n矩陣A的QR分解，其核心思想是運(yùn)用變維向量的Householder矩陣變換，保證變換后的向量除第一個(gè)元素以外，其他元素均為0。具體的分解過程如下[4-5]：

3? ? 基于Householder變換的特征值多核并行求解算法設(shè)計(jì)

綜上所述，可設(shè)計(jì)如下的特征值多核并行求解算法。

4? ? 算法的性能測試

在Intel Xeon E5450四核3.0 GHz CPU（每個(gè)核心的一級緩存各由32 KB數(shù)據(jù)緩存和32 KB指令緩存組成，二級緩存容量為12 MB）、KingSton DDR3 1 333 MHZ 4 GB內(nèi)存及Red Hat Enterprise Linux 6.1操作系統(tǒng)的環(huán)境中對上述算法進(jìn)行了模擬[6]，程序采用OpenMP和C++語言進(jìn)行編寫[7]。

為了節(jié)省存儲空間，式（1）中矩陣A按如下規(guī)則產(chǎn)生：

實(shí)驗(yàn)將在單核和四核環(huán)境中進(jìn)行Householder變換的特征值求解，并在四核環(huán)境中運(yùn)行本文的并行算法，而矩陣A的階數(shù)將分別選取{1 000， 2 000， 3 000}，具體的實(shí)驗(yàn)結(jié)果則如圖1所示。

從圖1可以發(fā)現(xiàn)，四核環(huán)境的特征值多核并行求解比單核串行求解在運(yùn)算速度上提高了約45%。

5? ? 結(jié)語

本文在PC多核微機(jī)上設(shè)計(jì)實(shí)現(xiàn)了一種基于Householder變換的特征值多核并行求解算法，新算法具有易于實(shí)現(xiàn)且并行性高的特點(diǎn)。理論分析及相關(guān)實(shí)驗(yàn)均表明它的可行性和有效性。

[參考文獻(xiàn)]

[1]黃鐸，陳蘭平，王風(fēng).數(shù)值分析[M].北京：科學(xué)出版社，2000.

[2]張賢達(dá).矩陣分析與應(yīng)用[M].北京：清華大學(xué)出版社，2004.

[3]時(shí)寶，劉孝磊，蓋明久，等.實(shí)用矩陣分析基礎(chǔ)[M].北京：國防工業(yè)出版社，2018.

[4]張華民.矩陣方程迭代求解方法研究[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，2019.

[5]徐樹方.矩陣計(jì)算的理論與方法[M].北京：北京大學(xué)出版社，1995.

[6]趙輝，王振奪.基于OpenMP的多核系統(tǒng)中并行優(yōu)化研究[J].北華航天工業(yè)學(xué)院學(xué)報(bào)，2004（6）：11-13.

[7]周偉明.多核計(jì)算與程序設(shè)計(jì)[M].武漢：華中科技大學(xué)出版社，2009.