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

《矩阵特征值的多核并行求解算法及设计研究.pdf》由会员分享，可在线阅读，更多相关《矩阵特征值的多核并行求解算法及设计研究.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、矩阵特征值的多核并行求解算法及设计研究 黄丽嫦;林结【期刊名称】无线互联科技【年(卷),期】2019(016)020【总页数】3 页(P58-60)【关键词】Householder 变换;特征值;正交三角分解;多核并行计算【作 者】黄丽嫦;林结【作者单位】佛山职业技术学院 广东 佛山 528137【正文语种】中 文 1 矩阵特征值及其牲向量介绍 工程技术和科学研究中的诸多问题，通常可以归结为求解某一矩阵的特征值及其对应的特征向量。设给定的矩阵 ARnn，若存在非零向量 xRn 及常数 R，使得：若式（1）成立，则称常数 为矩阵 A 的特征值，而非零向量 x 则为对应于 的特征向量。在实际应用中

2、，求解矩阵的特征值及其对应的特征向量的数值算法可以分为分解法和迭代法两种1。分解法将原矩阵分解为较容易求出特征值的形式，该类方法的优点是算法的计算效率较高，而缺点就是受舍入误差的影响，导致计算精度不高。迭代法则是将特征值及其对应的特征向量作为一个无限序列的极限来计算，由于以逼近误差来控制迭代的次数，故算法在严格收敛的条件下具有较好的计算精度，而缺点就是迭代过程中需要消耗一定的计算成本。矩阵的 QR 分解是工程应用中最广泛的一种矩阵分解，是矩阵特征值的重要求解方法，注意到目前的微机普遍具有多核架构计算环境，为此本文拟采用 Householder 变换的方法，在多核微机中设计实现了一种基于 QR

3、分解并行的矩阵特征值求解算法。2 基于 QR 分解的特征值求解及 Householder 变换 2.1 基于 QR 分解的特征值和求解矩阵的 QR 分解原理 引理 1：若 ARmn，且 mn，则存在正交的矩阵 QRmn 和上三角矩阵RRmn，使得式（2）成立2：A=QR （2）引理 2：若 A 和 B 是任意两个 mn 矩阵，则：AHA=BHB （3）当且仅当一个 mm 酉矩阵 Q，使得式（4）成立3：QA=B （4）根据矩阵的 Schur 分解定理，对于一般的实矩阵 ARnn，通过正交相似变换后，总酉相似于一个三角矩阵，即有：式（5）中，Q 为正交矩阵，对角块 Rii(i=1,2,m)为一阶

4、或二阶方阵，每一个对角块即为 A 的实特征值，每一个二阶对角块的两个特征值是 A 的一对共轭复特征值。2.2 基于 QR 分解的特征值求解原理 于是，A 和 B 有相同的特征值。继续对 B 作 QR 分解，进而得到一系列矩阵，令 A=A1，有如下的迭代算法：利用式（8）进行 QR 迭代分解，若矩阵序列An的对角元收敛，且严格下三角部分元素均收敛到 0，则迭代分解结束，而迭代分解结束时所对应的矩阵序列的特征值即为矩阵 A 的特征值。2.3 矩阵的 Householder 变换 常用的 QR 分解算法有基于 Gram-Schmidt 正交法的 QR 分解、基于Householder 变换的 QR

5、分解以及采用 Givens 旋转的 QR 分解，相对而言，由于 Householder 变换具有较少的计算量，为此本文拟采用基于 Householder 变换来实现矩阵的 QR 分解。定义：设向量 Rn，2=1，则称：H()=I-2T （9）为 Householder 矩阵变换。从 Householder 矩阵变换的定义出发，易知，对于=(1,2,n)T0，则存在 Householder 矩阵 H，使得：H=1 （10）式（10）成立，其中，=-sign(1)2，1=(1,0,0)，而矩阵 H 则可通过式（11）求得：2.4 基于 Householder 变换的 QR 分解 基于 Househ

6、older 矩阵变换，可以实现任意 mn 矩阵 A 的 QR 分解，其核心思想是运用变维向量的 Householder 矩阵变换，保证变换后的向量除第一个元素以外，其他元素均为 0。具体的分解过程如下4-5：（1）依照列分块的方式划分矩阵 A，有 A=a1,a2,an，令：（2）将式（13）中的 B 继续依照列分块的方式划分，有B=b2,b3,bn，令：（3）继续进行 Householder 矩阵变换，求得第 n-1 个 Householder 矩阵 Hn-1，使得：令 Q=(Hn-1H2H1)-1，根据 Householder 矩阵的特性，易知 Q 为一正交矩阵，故式（17）可写成 A=QR

7、，于是便完成矩阵 A 的 QR 分解。3 基于 Householder 变换的特征值多核并行求解算法设计 综上所述，可设计如下的特征值多核并行求解算法。算法名称：基于 Householder 变换的特征值多核并行求解算法；输入：矩阵 ARnn；输出：1,2n。算法描述：（设 CPU 的核数为 p）应用式（12）和（14）求出对应的 Householder 矩阵，将 Householder 的矩阵变换运算 Hi(i)=Hi1(i),Hi2(i),Hin(i),(i)=a,b,c,均匀分配至各个计算核中；在核 1 中计算：Hi1 在核 2 中计算：Hi2；核 1核 p 并行计算，待所有核计算完毕后

8、，析出后续需要迭代 QR 分解的矩阵(i+1)；从 R 矩阵提取 a11,b21,nn1，并对应赋值给 1,2,n，进而完成矩阵 A 的特征值求解。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 按如下规则产

9、生：实验将在单核和四核环境中进行 Householder 变换的特征值求解，并在四核环境中运行本文的并行算法，而矩阵 A 的阶数将分别选取1 000,2 000,3 000，具体的实验结果则如图 1 所示。图 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.