Jacobi矩阵特征值的并行算法

《Jacobi矩阵特征值的并行算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第24卷第1期纺织高校基础科学学报Vo1．24，No．12011年3月BASICSCIENCESJOURNALOFTEXTILEUNIVERSITIESMarch，2011文章编号：1006-8341(2011)01-0021-05Jacobi矩阵特征值的并行算法刘艳红，吕全义(西北工业大学应用数学系，陕西西安710129)摘要：提出了并行求解实三对角矩阵特征值方法，该方法主要针对Jacobi矩阵．应用求多项式根的Sturm法，将矩阵特征多项式的求根区间隔离成单根区间；对已隔离出的单根区间先用二分法求解，

2、达到一定精度后再用牛顿法精确求解．考虑到处理机负载平衡问题，将求根区间分成若干等分，然后按区间循环地将其分给各个处理机．各处理机并行地进行求根计算，它们之间无通信．通过此方法实现了处理机负载平衡，算法并行效率达0．85以上．数值算例表明了此并行算法的高效性．关键词：Jacobi矩阵；Sturm法；牛顿法；并行算法；并行效率中图分类号：0246文献标识码：A矩阵特征值问题不仅可直接解决诸如非线性规划、优化、常微分方程等各类数学计算问题，而且在结构力学、工程设计、计算物理和量子力学中具有广泛的应用．由于它具有

3、重要的理论和实际意义，所以矩阵特征值问题成为当前国内外高性能计算机的主要计算任务之一．国内外许多学者对矩阵特征值问题进行了深入研究，其大多可归结于计算三对角矩阵的特征值．目前，三对角矩阵特征值的求解方法主要有Qn法⋯、分而治之法]、分裂一合并法【3]、Sturm序列法L4等．文献[1]介绍了带Wilkinson位移的QR法；文献[2—3]基于分治思想将矩阵做降阶分块处理，然后并行求解；文献[4]基于二分法提出了并行求解算法，但负载平衡问题没有很好解决。关于大型三对角矩阵特征值的并行求解问题，实现负载平衡仍

4、然面临很大挑战．本文提出并行求解Jacobi矩阵全部特征值的方法，首先将求根区间分成幻(为正整数，P为处理机台数)等分，然后按区间循环地将其分给各个处理机．各处理机在明确自己的所有求根区问后，进行并行求根计算．计算过程中处理机之问不需通信，此方法有效地实现了负载平衡，且达到最小耗时效果．1预备知识定义1[5实系数多项式序列f0()()()，⋯()，如果满足条件(1)()在(a，6)内没有实根；(2)相邻的2个多项式一()()(1≤k≤m)在(a，6)内没有公共根；(3)如果是序列中某多项式()(1≤k≤m

5、一1)的根，则A一()和+。()异号；则称该多项式序列为)在区间(a，b)的Sturm序列．定义2【6设三对角矩阵收稿日期：2010-09-25基金项目：陕西省自然科学基金资助项目(2009JM1008)通讯作者：吕全义(1963一)，女，辽宁省沈阳市人，西北工业大学教授．E—mail；luquan@nwpu。cdu．cn纺织高校基础科学学报第2l4卷61c1口lbz白A：⋯’一Cl一I如果，，都是实数，且ci>D，则称A为Jaeobi矩阵．设Jacobi矩阵A的特征多项式为(入)=I八f—A1．记(^)

6、为4的前i阶主子矩阵的特征多项式，则有递推关系(A)=det(AJ—AI)=(J)L一6。)I】(入)一I／s~]C一】。-2(入)．(1)由式(1)得多项式序列)=，{】(A)=A—b】，‘I(A)=(A一6)1(人)一口k一1c★一1I-2(A)，后=2，3，⋯，，1．由S￡tl珊序列的定义知{，-l’⋯，，o}是{一∞，∞}上的Sturra序列．定义3c1实数列，a-．，口从左到右，若n口川

7、是一实数，则实数列()。的变号数称为此多项式序在孝点的变号数，记为y()．设膏)是序列f()，一。()，⋯，()，()}的变号数，则有定理】．定理1【6l给定口，b，若(口)≠0，(b)≠O，则V(口)一V(b)是(入)在Ca，6】上的根的个数．关于特征值的上下界问题有定理2：定理2(Gerschgorin圆盘定理)】设A=()⋯，nDl=：一口“l≤∑Inll，i=1，2，⋯，，lJlnt表示以为圆心，。。I为半径的圆盘，则A的特征值至少落在某一个圆盘内，即AE2新序列的构造2．1构造定理l给出了矩阵A

8、在[口，∞]内特征值的个数．在实际计算过程中，当矩阵阶数很高时，为了防止计算{，-1，⋯，，?的变号数)时上溢和下溢，考虑计算【5()=()．，(A)．由递推关系(A)=(A—)一l—Ilk_1一．2，得递推公式为(A)=入一6I一口¨cI-1／D¨(A)．通过计算D(A)，D：(A)，⋯，D(A)中的负数个数，即为Sturm序列{，，⋯，l，}的变号数)．在计算中，如果D1(A)，()，⋯，一：()都不为零，而一，()=O，