davidson是什么意思idson在线翻译读音例

求解大型矩阵特征值问题的并行精化Davidson方法

王顺绪;戴华

【摘要】针对共享主存的并行计算环境和微机网络并行计算环境,本文给出了求解

人型稀疏对称矩阵的部分极端特征对的并行精化Da恍惚的意思是什么 vidson方法,分析了该法的内

在并行性.各处理器利用矩阵的行块和投影了空间的正交皋所组成矩阵的行块进行

运算,结合重新启动策略求解矩阵多个特征对的近似值,并用以计算某型号机翼的固

有频率,在微机网络并行计算环境和拥有共享土存并行计算环境IBM-P650上进行

了数值试验.

【期刊名称】《工程数学学报》

【年(卷),期】2009(026)005

【总页数】7页(P922-928)

【关键词】并行计算;特征值问题;Dayidson方法;精化方法

【作者】王顺绪;戴华

【作者单位】南京航空航天大学理学院,南京,210016;淮海工学院数理系,连云

港,222005;南京航空航天大学理学院,南京,210016

【正文语种】中文

【中图分类】O241;O246

1引言

在科学和工程技术领域中，经常需要计算大型稀疏对称矩阵的若干个特征对。解决

这一问题的有效方法是正交投影方法，包括子空间迭代法，Lanczos方法，

Arnoldi方法，Davidson方法和Jacobi-Davidson方法[1,2]。为进一步提高

Lanczos方法和Davidson方法的可靠性，Underwood提出了块Lanczos方法

[3]，戴等提出了预处理块Lanczos方法[4]，Crouzeix等人提出了块Davidson

方法[5,6]。

用正交投影方法计算特征值问题

的部分特征对时，Ritz向量xi可能收敛很慢甚至发散，针对这一问题，贾提出了

保留Ritz值i，用满足

的精化向量xi代替Ritz向量xi的精化思想[7-12]，并继而指出其中xi=Vizi,zi

是矩阵(A−iI)Vi的最小奇异值min对应的右奇异向量，且即

不难证明xi=Vizi是对应于Ritz值的使本次迭代的残量范数最小的向量，此时的

残量范数为min，特征值的近似可取为

大型矩阵特征值问题的计算是一项很耗时的工作，尽管人们采用多种方法降低计算

量，但终因串行思想的限制难以有更大的提高，采用并行计算是一条必由之路。多

年来，很多科技工作者对特征值问题的并行计算进行了大量的研究。Balle和

Cullum、Nool和VanderPloeg分别讨论了并行Lanczos方法和并行Jacobi-

Davidson方法[13,14]，取得了满意的效果。为提高求解大型矩阵特征值问题块

Davidson方法的计算效率，本文提出并行精化块Davidson方法，并分别在微机

网络并行环境和并行计算机IBM-P650上进行了数值试验。

2精化块Davidson方法

设A是n阶稀疏对称矩阵，Davidson方法利用Galerkin-Ritz投影技术，计算矩

阵的Ritz值和Ritz向量，使用预处理技术拓广投影子空间V的基[1]，在新的迭代

步中，Davidson方法充分利用已经获得的信息扩充新的子空间，因而在很少的迭

代步内得到满足精度要求的解。Davidson方法通常和重新开始技术结合使用。

算法1(块Davidson方法[5])

1)选取正整数m和l，列正交规范矩阵V1=[v1,v2,,vl]，精度；

2)对k=1,2,，执行以下各步；3)Wk=AVk；4)Hk=VTkWk；

5)计算Hk的l个最大(或最小)特珊组词语 征对(k,i,yk,i),i=1,,l；

6)计算Ritz向量xk,i=Vkyk,i,i=1,,l；

7)计算残量rk,i=(k,iI−A)xk,i,i=1,,l；

8)收敛性检查，若∥rk,i∥2<,i=1,,l，则停止，否则转9)；

9)求解校正方程Ck,itk,i=rk,i,i=1,,l；

10)若dim(Vk)+l6m，则Vk+1=MGS(Vk,tk,1,tk,2,,tk,l)，转3)，否则转11)；

11)V1=MGS(xk,1,,xk,l,tk,1,tk,2,,tk,l)，转2)重新开始。

算法1中的MGS代表修正的Gram-Schmidt正交化过程，其数值稳定性优于经

典的Gram-Schmidt正交化过程，假设Vk=(v1,,vs)列正交规范，

vj=tk,j−s,j=s+1,,s+l，则算法1中的Vk+1=MGS(Vk,tk,1,tk,2,,tk,l)的过程如

下。

第k次迭代的预处理矩阵Ck,i是k,iI−A的近似，当Ck,i接近k,iI−A时，校正

方程Ck,itk,i=rk,i(i=1,,l)的解tk,i接近xk,i(i=1,,l)，在这种情况下将tk,i(i=1,,l)

加入到基中会使新的基底线性相关，为克服这个缺点，可使用Olsen预处理[15]，

此时校正方程为

由tTk,ixk,i=0得到

这样经过MGS过程后得到的子空间的基标准正交。

将精化思想应用于块Davidson方法，就k,i而言，

假设

得到精化块Davidson方法，以算法2表示。

算法2(精化块Davidson方法)

1)选取正整数m和l，列正交规范矩阵V1=[v1,v2,,vl]，精度；

2)对k=1,2,,执行以下各步；3)Wk=AVk；4)

5)计算Hk的l个最大(或最小)特征对(k,i,yk,i),i=1,,l；

6)计算Ritz向量xk,i=Vkyk,i,i=1,,l；

7)计算残量rk,i=(k,iI−A)xk,i,i=1,,l；

8)收敛性检查，若则停止，否则转9)；

9)若dim(Vk)+l6m，求解Ck,itk,i=rk,i,i=1,,l，Vk+1=MGS(Vk,tk,1,,tk,l)，转

3)；

10)若dim(Vk)+l>m计算Sk,i=,l的最小特征

11)计算精化向量xk,i=Vkzi,i=1,,l；

12)V1=[xk,1,,xk,l]，转2)。

3并行精化块Davidson方法

3.1精化块Davidson方法的并行计算

将n阶方阵A按行划分，使得各处理机平均分配A的行数，若n不是处理机数p

的整数倍，则前面的处理机比后面的多拥有一行。假设处理机Pi中存放矩阵的部

分为Ai，Ai共有mi行，假设这mi行是从A的第i1行到A的第i1+m1−1行，

根据算法2得到并行精化块Davidson算法。

算法3(并行精化块Davidson方法)

1)选取正整数m和l，列正交规范矩阵V1=[v1,v2,,vl]，精度；

2)对k=1,2,，执行以下各步；3)Pi计算Wk,i=AiVk；

11)若dim(Vk)+l>m则Pi计算矩阵到WTkWk，从而

计算Sk,j(j=1,,l)的最小特征对

12)并行计算精化向量xk,j=Vkzj,j=1,,l；

13)V1=[xk,1,,xk,l]，转2)。

3.2并行特性分析及数据分配

算法3的计算过程主要是矩阵和向量乘，因此具有良好的并行性，其中6)计算低

阶矩阵Hk的特征对及11)中最小奇异对的运算量较小，各处理机可分别从事该过

程的计算。

Wk=AVk及Hk=的并行计算。Pi中Wk,i=AiVk，从而Pi可以独立计算Wk的

mi行。假设，其中各子块的规模同A的行分块，因此各处理机可以独立计算的列

子块和Wk的行子块的乘积，处理机Pi计算整体求和或主节点机求和得到

各节点机(或主节点机)计算Hk的全部特征对，确定Hk的l个特征值k,j(j=1,,l)，

若由主节点机计算，必须将结果发送给各子进程。

Wk的并行计算。Pi计算，得到

主节点机或各节点机同时计算Sk,j的最小特征对,j=1,,l。

Ritz向量xk,j(j=1,,l)的并行计算。假设

将Xk行分块，行分块的情况同A的行分块，那么则

也即处理机Pi独立计算Xk,i，同样的方法用于并行计算精化向量xk,j,j=1,,l。

假设Tk=(tk,1,,tk,l)，则Pi中含有Tk的一个行数为mi的行块。

经过上述各步，各结点机中可得到Vk+1的相应行块，然后进行相应的正交化过

程。

3.3正交化过程的并行计算

算法3中Vk+1各列的正交化过程，采用行分块的形式，Pi负责Vk+1的mi行

的运算。Vk+1各列向量的范数以及各向量和其后面向量内积的计算，则由各处理

机分别负担一部分，为减少通讯，将经典的Gram-Schmidt(CGS)正交化过程和

MGS过程相结合，记为CMGS过程。CMGS过程的一部分环节使用CGS过程，

另一部份使用MGS过程。当m−dim(Vk)>l时，使用并行CGS方法，对处理机

中的tk,j(j=1,,l)相应的部分进行正交修正，该过程只需一次整体求和，然后对修

正过的tk,j(j=1,,l)自身进行MGS标准正交化过程。

4数值试验及结论

假设p代表节点机的数量，tp代表使用p个节点机计算的时间(单位：秒)，

Sp=t1/tp表示加速比，表并行效率(以百分比表示)，迭代精度=干净的反义词 10−6。数值

试验在IBM-P650和微机网络并行计算环境上进行，微机网络并行环境由安装

MPI的PII300微机组成，内存64M。IBM-P650是拥有8个1.45GHz的

Power4CPU、16GB内存、FastT磁盘阵列的并行计算机，在IBM-P650并行机

上用Fortran编译器编制使用共享内存进行通信的MPI程序。

算例1n阶矩阵A=(aij)的元素定义为i=j时aij=i，|i−j|6w并且i=j时

aij=∆|i−j|，其它情况aij=0。w为A的半带宽。本算例取n=7000，w=262，

∆=0.75[16]，在两种并行环境下，使用精化块Davidson方法和非精化块

Davidson方法并行计算A的5个最小特征对，结果见表1-3。

表1:算例1的前5个最小特征值kk−4.093132610−2210.58047103

1.016409741.728426252.2801648

表2:微机并行环境下并行计算算例1的情况并行精化块Davidson方法并行块

Davidson方法ptSpptSp1100222.4511001304.13114.481.55

77.52187.11.6381

表3:IBM-P650上并行计算算例1的情况并行精化块Davidson方法并行块

Davidson方法ptSpptSp110026.2811001103.38185.543.88

1.6281260.461.7169.382.332.767.4437.322.771.434.3954.9822.19

4.6658.2

算例2使用并行精化块Davidson方法和非精化块Davidson方法，并行计算如

图1所示机翼的前10阶频率[17]。假设K和M代表结构的√刚度矩阵和质量矩阵，

是特征值问题Kx=Mx的特征值，则结构相应的固有频率，将广义特征值问题

转变成，其的近似

在IBM-P650上的计算情况如表4所示。

图1:某型号机翼的上翼面

表4:IBM-P650上并行计算算例2的情况并行精化块Davidson方法并行块

Davidson方法ptSpptSp110028.27110017.63193.544.481.85

92.324.081.8782.982.533.2781.742.303.321.585.2365.481.435.34

66.7

计算结果表明，算例1中非精化方法和精化方法的迭代次数分别为101次和6次，

精化方法比非精化方法迭代次数减少了许多，节省了计算时间；算例2的预处理

矩阵的修正效果非常好，两种方法的迭代次数都是5次，精化方法的运行时间比

非精化的稍多，加速比稍低，这是由于在本算例中两种方法都重新启动一次，精化

方法需要额外计算Sk,j(j=1,,l)及其相应的最小特征对(21,j,zj)(j=1,,l)，增加了

计算量和相应的通讯开销。精化方法的迭代次数不会超过非精化方法的迭代次数，

其减少计算时间的原因在于其可能减少迭代步。由于涉及到的运算基本上都是矩阵

向量乘，并行计算的效果是明显的。

参考文献：

【相关文献】

[1]rativecalculationofafewlowesteigenvaluesandcorresponding

eigenvectorsoflargereal-symmetricmatrices[J].JournalofComputational

Physics,1975,17(1):87-94

[2]SleijpenGLG,i-Davidsoniterationmethodforlinear

eigenvalueproblem[J].SIAMJMatrixAnalAppl,1996,17(2):401-425

[3]ativeBlockLanczosMethodfortheSolutionofLargeSparse

SymmetricEigenproblems[D].Stanford:StanfordUniversity,1975

[4]DaiH,ditionedblockLanczosalgorithmforsolvingsymmetric

eig求经典下句 envalueproblems[J].Journalof红袖读书免费阅读 ComputationalMathematics,2000,18:365-374

[5]CrouzeixM,PhilippeB,idsonmethod[J].SIAMJSci

Comput,1994,15(1):62-76

[6]SadkaneM,entationofavariableblockDavidsonmethodwith

deflationforsolvinglargesparseeigenproblems[J].NumericalAlgorithms,1999,20:217-240

[7]diterativealgorithmbasedonArnoldi’sprocesssforlargeunsymmetric

eigenproblems[J].LinearAlgebraanditsApplications,1997,259:1-23

[8]edsubspaceiterationalgorithmforlargespar赞美诗歌全集 se

eigenproblems[J].AppliedNumericalMathematics,2000,32(1):35-52

[9]ysisoftheRayleigh-Ritzmethodforapproximating

eigenspaces[J].MathematicsofComputation,2000,70(234):637-647

[10]贾仲孝，张萍.计算大规模矩阵最大最小奇异值和奇异向量的两个精化Lanczos算法[J].计算数

学，2003,25(3):293-304

[11]JiaZX,edresidualiterationmethod[J].NumericalMathematicsa

JournalofChineseUniversities,2004,26(2):146-155

[12]iteorthogonalprojectionmethodsforlargematrix

eigenproblems[J].ScienceinChina(A),1999,42(6):577-585

[13]BalleS,lelalgorithmforcomputingeigenvaluesofverylargereal

symmetricmatricesonmessagepassingarchitectures[J].AppliedNumerical

Mathematics,1999,30(2):341-365

[14]NoolM,lelJacobi-Davidson-typemethodforsolvinglarge

generalizedeigenvalueproblemsinmagnetohydrodynamics[J].SIAMJournalonScientific

Computing,2000,22(1):95-112

[15]OlsenJ,JorgensenP,gtheone-billionlimitinfullconfiguration-

interaction(FCI)calculations[J].ChemicalPhysicsLetters,1990,169(6):463-472

[16]ShepardR,WagnerAF,TilsonJL,spaceprojectedapproximate

matrix(SPAM)modificationoftheDavidsonmethod[J].Jour欢欣鼓舞 nalofComputational

Physics,2001,172(2):472-514

[17]王顺绪.微机网络并行环境下杆壳组合结构动力特性并行计算[J].计算力学学报，2005,22(1)：

38-41