资源描述：
《解高阶Hermitian矩阵特征值问题的并行块消去迭代法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、年月数值计算与计算机应用第期解高阶矩阵特征值问题的“’并行块消去迭代法孙家艇邓健新曹建文中国科学院软件研究所入五扭入五度了,‘叻。,,‘。二夕‘议一一,’一,,七经引言在现代计算物理、计算化学、计算生物以及许多科学研究与工程计算中都涉及很高阶的矩阵特征值问题对这个问题已有许多,的研究成果和计算方法但是现有的方法或者是不能并行执行或者是仅能计算少量的特征值对于很高阶的矩阵,要求不是太少量的特征值的问题还没有一个好的并行算法本文工作的目的是给出,一个粗粒度的并行算法能充分利角高性能大规模分布式存贮的并行计算机巨大潜力解决实际应用的计算问题本文给出的并行分块消去迭代法
2、把在单处理器上串行求解矩阵特征值问题的解“”,,算器看作黑盒子来使用解算器的方法可以是任意的有效方法例如算法年月日收到国家自然科学基金资助项目,国家基础性攀登项目支持数值计算与计算机应用年在中曾提出过块算法,它是算法的推广由于算法在本质上并,,没有改变因而仍然停留在一般的并行算法的水平计算量与数据传输量比值小,实用效率不高关于用分块逐次消去迭代的算法在中提出过用来解奇异值问题,但对于算法的收敛性和误差分析以及并行设计等等问题都还没有系统研究,给出,也给本文对于并行块消去迭代算法了总体收敛性和渐近二次收敛性的证明出算法的误差分析、并行实现与分析最后在国家智能计算机
3、研究开发中心研制的大规模并行计算机曙光上进行数值实验,文中附有数值结果愁并行块消去迭代算法假设矩阵特征值问题是入毛其中是二矩阵,,入分别是求解的特征向量与对应的特征值首先划分为块矩阵‘,,,,,二。为叙述方便假定可被整除人都是阶的方阵并行分块消去迭代法可表示如下︸并行分块消去迭代法步按照某种并行消去迭代次序,以分块数。,处理器个数二为例,常用的并行计算的次并行变换为,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,“”,‘,,‘,其中“力表示用黑盒子解子问题子问题的矩阵由人人,街力组成计算的,,、,‘,结果是入被化为零人化为对角形矩阵上述次并行变换称为
4、一次扫描每一个非对角块都被消去迭代过一次以变换,为例,消去迭代过程的变换可记为了、、‘、、,才、、、︸宁一’‘嵘期孙家褪等解高阶矩阵特征值问题的并行块消去迭代法其中式、,、表示该位置上,并且丸的矩阵的当前值一“‘,,‘,、,一,号幼护,,一,“,。步计算一、,’艺’,,其中矩阵范数川定义为川一,若川‘则停止否则继续迭代艺笼,执行步和步,其中石是给定的精度控制参数算法的工作以用黑盒子解子问题为例,由,可知,每次变换的工·作量如下解子问题一哟”,矩阵乘积一一的“,特征向量累积一劝,一次扫描有斌一次变换,其中一因此一次扫描的工作量为一护妒“通常用次扫描可,以使计算解达
5、到很高的精度需要的无,,,,,,,计算量为一以即为例算,,,,该算法不是法的工作量分别相当于的倍由此可见一个好的串行算法,但它容易并行实现,算是一个好的并行算法见互、算法的收敛性并行块消去迭代算法的收敛性证明基,于矩阵范数压缩的原理基本思想如下‘,‘对于任给阶的“‘矩阵一,川,一“‘,其中“、是艺的特征值矩阵范数,即若,酉变换不变则尸到尸二尸若分块消,最终化为对角形,则其对角元必是去迭代变换使得助逐渐压缩的特征值并行块消去迭代,子问题。,的对角化使法的总体收敛性由式可知,,两个非对角子块被化零因此矩阵的非对角元范数减少了人川即任且一。仔且‘且、全例如算法使得每一
6、个子问题,那么的人川不少于所有非对角子块范数的平均值。·“。,,‘,。、卜卜舟数值计算与计算机应用年其中,一若用个处理器并行迭代,加速接近,实,并行执际计算表明行上述并行块消去迭代法所用的通信时间不多算法的渐近收敛性引理对于形如下式的矩阵等式一口、了、声、急黝之劲会劲含劲了上会之会之一,,,,⋯,二,二,二,,,拼,拼,,拼,⋯。鳍⋯,拼,,,,,拼。⋯拼二,,盆,盆证明设向量是式中的第,,篡列由式有总黝一三乞三,于是拼‘,‘一户‘一,一‘一‘,一拼·三。日,其中是一个相对定数,由下式确定,一拼‘。三三。由引理假定可得三期孙家翅等解高阶矩阵特征值问题的并行块消去
7、迭代法注意到’“一,,””‘,,一‘从而可推得从类似地可证明。由式可得出,二盆盆凡盆耀凡乙从而,、一扛尤墓定理解矩阵特征值问题的并行块消去迭代算法一是渐“”近二次收敛的证,二‘,,,,明假设并行块消去迭代算法迭代到这样的阶段人川⋯,‘,,二笋为了叙述简明我们以的例子来表示假若一次扫描的次序为,,,,,,,,,,,,我们考察某一非对角块,例如的变化历程对于,的变换,,的改变如下,城、、、,、、誉。由引理可得,,、退卜梦卜类似地对于所有非零化的变换,的影响都是数量级的我们现在观察被化零之后重新变为非零的情,例如,二,况变换之后接着变换使恢复为非零,翻一文之哟于是,‘
8、‘,二,’仇扎哥引仇符由
