矩阵特征值的多核并行求解算法及设计研究

黄丽嫦 林结

摘   要：特征值及其特征向量的求解问题一直是现代数值分析的研究热点，在多核架构的微机中，文章基于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.