矩陣特征值的多核并行求解算法及設計研究

黃麗嫦 林結

摘? ?要：特征值及其特征向量的求解問題一直是現代數值分析的研究熱點，在多核架構的微機中，文章基于Householder變換提出了一種高效的矩陣QR多核并行分解方法，在此基礎上，設計實現了矩陣特征值的多核并行求解算法。數值實驗驗證了新設計算法的可行性和有效性。

關鍵詞：Householder變換;特征值;正交三角分解;多核并行計算

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

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

Ax=λx（1）

若式（1）成立，則稱常數λ為矩陣A的特征值，而非零向量x則為對應于λ的特征向量。在實際應用中，求解矩陣的特征值及其對應的特征向量的數值算法可以分為分解法和迭代法兩種[1]。分解法將原矩陣分解為較容易求出特征值的形式，該類方法的優點是算法的計算效率較高，而缺點就是受舍入誤差的影響，導致計算精度不高。迭代法則是將特征值及其對應的特征向量作為一個無限序列的極限來計算，由于以逼近誤差來控制迭代的次數，故算法在嚴格收斂的條件下具有較好的計算精度，而缺點就是迭代過程中需要消耗一定的計算成本。矩陣的QR分解是工程應用中最廣泛的一種矩陣分解，是矩陣特征值的重要求解方法，注意到目前的微機普遍具有多核架構計算環境，為此本文擬采用Householder變換的方法，在多核微機中設計實現了一種基于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旋轉的QR分解，相對而言，由于Householder變換具有較少的計算量，為此本文擬采用基于Householder變換來實現矩陣的QR分解。

2.4? 基于Householder變換的QR分解

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

3? ? 基于Householder變換的特征值多核并行求解算法設計

綜上所述，可設計如下的特征值多核并行求解算法。

4? ? 算法的性能測試

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

為了節省存儲空間，式（1）中矩陣A按如下規則產生：

實驗將在單核和四核環境中進行Householder變換的特征值求解，并在四核環境中運行本文的并行算法，而矩陣A的階數將分別選取{1 000， 2 000， 3 000}，具體的實驗結果則如圖1所示。

從圖1可以發現，四核環境的特征值多核并行求解比單核串行求解在運算速度上提高了約45%。

5? ? 結語

本文在PC多核微機上設計實現了一種基于Householder變換的特征值多核并行求解算法，新算法具有易于實現且并行性高的特點。理論分析及相關實驗均表明它的可行性和有效性。

[參考文獻]

[1]黃鐸，陳蘭平，王風.數值分析[M].北京：科學出版社，2000.

[2]張賢達.矩陣分析與應用[M].北京：清華大學出版社，2004.

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

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

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

[6]趙輝，王振奪.基于OpenMP的多核系統中并行優化研究[J].北華航天工業學院學報，2004（6）：11-13.

[7]周偉明.多核計算與程序設計[M].武漢：華中科技大學出版社，2009.