您的论文得到两院院士关注文章编号:1008-0570(2009)10-3-0157-03
软件时空
一种面向大型矩阵运算的分布并行算法
Adistributedparallelmethodforlarge-scalematrixcomputing
(南京航空航天大学)
赵丽娜庄毅汪晓虹
ZHAOLi-naZHUANGYiWANGXiao-hong
摘要:针对大型矩阵广义特征值问题,提出了一种基于直接变换法的矩阵分解算法;在分析了矩阵存储技术的基础上给出了基于直接变换法的高阶矩阵存储方法。提出了一种基于直接变换法的面向大型带状正定矩阵运算的分布并行算法;运用mpi(MessagePassingInterface)和数学软件包CLAPACK实现了该算法;实验结果表明该算法是正确可行的,符合大型工程的计算要求。
关键词:直接变换法;分布并行算法;矩阵分解;矩阵存储中图分类号:TP301.6文献标识码:A
Abstract:Amethodofmatrixdecompositionbasedondirecttransformationmethodformodesynthesisispresented.Propermatrixstoragetechniquesfordirecttransformationmethodformodesynthesisareputforwardafterstudyingmatrixstoragetechniques.Adis-tributedparallelmethodbasedondirecttransformationmethodformodesynthesisisdesignedandimplemented.Theresultoftheex-perimentdemonstratesthatdirecttransformationmethodformodesynthesisiscorrectandtheaccuracyisuptothemustard.Keywords:Directtransformationmethodformodesynthesis;Distributedparallelcomputing;Matrixdecomposition;Matrixstoragetechniques
引言
广义特征值问题广泛应用于飞行器的设计、航天器设计、以及桥梁等大型工程设计和分析。此类问题随着矩阵阶数的扩大,计算量将会急聚增加,特别是应用有限元方法进行计算时,存储量与计算量非常大,因此,大型矩阵的存储与计算成为急需解决的问题。国内外已有多位学者对该问题进行研究,但多为串行算法或细粒度算法,不适用于基于普通网络的分布计算。
为子结构、2)计算出主模态和约束模态。设
的刚度、质量矩阵,主模态和约束模态计算过程如式(3)、(4)、(5)。
(3)(4)(5)
通过式(3)求出的主模态几个低阶模态,舍去约束模态。
中对应的,只取
中的高阶模态。通过(4)、(5)计算出的为
技术创新
1直接变换法
设某大型结构总体有限元模型的自由度数为n,结构的总体刚度矩阵和质量矩阵分别记为K、M,它们是n阶实对称正定矩阵,该结构的固有频率和振型满足
3)将步骤4)形成的子结构模态变换矩阵组装成模态变换矩
阵
。
4)形成模态矩阵:用式(6)做变换
(6)
得到模态矩阵
和
。
(1)
其中
为广义特征值,
为
的特征向量。采用直接变换法
时采用如下处理:
5)计算模态矩阵广义特征值,得到近似解。
1)将矩阵K、M分解为若干个子结构。每个子结构分为内部自由度(i表示)、上交界面自由度(h表示)、下交界面自由度(j表示)。其中,相邻子结构中前一个子结构的下交界面与后一个子
结构的上交界面数据由总体矩阵中相应位置的界面数据拆分而得。形式如下:
2基于直接变换法的矩阵分解
在进行大型矩阵分解时应注意以下问题:
1)每个子结构都应存在式(2-a)、(2-b)中的分块形式,分为界面自由度和内部自由度,而且内部自由度不应小于要求的主模态数量,否则,矩阵阶数小于要求无关向量个数,不能进行计算。
2)当各个机器负载不均衡时,计算量最大的机器上将会出
现瓶颈。
(2-a)(2-b)
3)各个处理机间通讯数据量与界面自由度紧密相关。界面自由度越大,约束模态数量越多,模态矩阵阶数越大,需要传递的
数据量越大。
赵丽娜:硕士研究生
基金项目:基金申请人:庄毅;基金颁发部门:中国人民总装备部(编号不公开)
其中,第1条是必须满足的。第2、3条是影响计算效率的因素,是算法优化需要考虑的问题。
算法1给出了基于直接变换法的矩阵分解算法,如图1:
邮局订阅号：82-946360元/年-157-
《PLC技术应用200例》
软件时空《微计算机信息》(管控一体化)2009年第25卷第10-3期
3)对称矩阵的广义特征值问题:设广义特征值问题为:(9)其中为n阶对称矩阵,采用对称矩阵存储;X为n×m(m≤n)矩阵,采用一般存储。在计算时,需要一个3*N工作空间。因此,存储量为:。
在直接变换法中,子结构矩阵为带状对称矩阵;计算过程中形成的模态变换矩阵是由各个模态组成,不能知道其数据分布状况和对称性质;形成的子结构模态矩阵具有对称性,但不能预测带宽;第二节中的模态矩阵是对称带状矩阵,可预测最大带宽。因此,根据(3)~(6)、(7)~(9),子结构矩阵、模态矩阵带状存储法,子结构模态矩阵采用三角存储,子结构模态变换矩阵、模态变换矩阵采用一般存储法,子结构模态矩阵采用对称存储方法。式
对称带状存储,为、(4)、(5)转换为矩阵求解问题,其中
一般存储。坐标存储法可以消除非零数据带来的空间浪费,所以
通信时矩阵转换为坐标存储法。
图1基于直接变换法的矩阵分解算法
基于直接变换法的矩阵分解算法:首先给定当前子结构首元素地址和子结构大小,确定一个原始子结构,令原始子结构最后一行r不变,列位置c从r-band+2向右移动,至最后一行r中找出不能覆盖的最外一列全部非零数据,确定为子结构下交界面边界所在的列c;然后,列c不变,将行向上浮动,直至列不能覆盖该行的所有非零值,确定下交界面边界所在的行r;最后,得到当前子结构的下交界面,完成该子结构的化分。相邻子结构中前
3.2DPC-DTM算法设计
在采用直接变换法进行计算时,分为子结构计算和模态矩阵计算两部分。模态矩阵的形成依赖于各个子结构的计算结果。其中涉及到的广义特征值计算,采用子空间方法。数据的传输过程通过引入MPI库实现。DPC-DTM算法如图2:
算法中首先各个slaver进程将子结构的基本数据———子结构在总体结构中的位置序号seq,子结构的上下交界面ucob,
技
术创新
一个子结构的下交界面与后一个子结构的上交界面数据位置重合,确定下一个子结构的上交界面;给定下一个子结构的首元素地址和大小,完成一次循环。返回第一步继续进行矩阵分解,直到总体矩阵分解完成。
在算法中每一个初始子结构的自由度是一个给定值,是相等的;并且对子结构进行了收缩;因此在一定程度上保证了负载平衡和界面尽量小的要求。
3DPC-DTM算法
3.1矩阵存储
矩阵计算中常用以下几种方法进行存储:
1)一般存储保留所有数据信息,计算方便,不需要知道矩
阵形态。
2)对称矩阵存储对称矩阵的上三角与下三角数据对称,存储矩阵的上三角部分或下三角部分,仅保留一半数据。
3)对称带状存储针对对称带状方阵的一种存储技术,只存储半带宽内的数据,适合于对称稀疏带状矩阵存储。
4)坐标存贮法保留非零数据信息,分别存储矩阵非零元素的行、列、元素值,记录非零数据所在的位置及数值。元素的获取需要对行列坐标的扫描。坐标存储法还存一些变种,如Knuths’方法等,目标是提高扫描效率。
除以上四种方法,还有变带宽存储,CSR等存储方法等。CLAPACK支持前三种存储方法的矩阵计算,其余的不支持。
直接变换法中的运算可归纳为以下三种问题:
1)对称正定带状矩阵的方程组求解问题:设求方程组:
(7)
其中A为n阶对称正定带状矩阵,半带宽为b,采用对称带状存储;B为矩阵,采用一般存储。求解时X将B覆盖。因此,矩阵求解的存储量为。
2)矩阵投影:用X对矩阵A进行投影:(8)其中A为n阶对称带状矩阵,半带宽为b,采用对称带状存储。X为矩阵,采用一般存储。则B为m阶方阵。在计算过程中,需要一个额外的阶矩阵Y存储的AX计算结果,因此,矩阵乘法的存储量为:。
-158-360元/年邮局订阅号：82-946
lcob以及子结构要求的主模态数量evnum发送给master,该过
程采用汇集函数MPI_Gather,它的功能是将各个进程发送的消息收集到master进程的数据区内。第二步master进程运用收集的数据预估出模态矩阵的大小及带宽,进行内存申请,同时各个slaver进程进行计算,获得子结构模态矩阵。第三步,各个slaver进程计算出子结构模态矩阵的非零数据个数nz,发送给master进程并将子结构模态矩阵非零数据打包,master进程非阻塞接收nz。在此过程中采用MPI_Irecv和MPI_Waitany函数实现数据nz的乱序接收。第四步,在等待到来自任何一个slaver进程发送的nz后,接收子结构模态矩阵数据并解包,存入相应的位置。返回第三步继续,直到接收到所有数据。其中,打包解包数据采用MPI_Pack和MPI_Unpack函数。第五步,master进程计算模态矩阵特征值,结束。
图2DPC-DTM算法
4实验
实验室pc机,内存512M,P4系列CPU。实验数据来源于
MatrixMarket的bcsstk06/bcsst-m06,bcsstk26/bcsstm26,bc-sstk27/bcsstm27,Boeing的crystk01/crystm01,crystk02/crystm02。
《现场总线技术应用200例》
您的论文得到两院院士关注自由度分别为420,1922,1224,4875和13965。实验时将矩阵crystk01/crystm01,crystk02/crystm02做如下变换使其正定化:将矩阵正定化。子空间算法中给定容忍值0.001。
表1中,为2个、3个、5个子结构时,求前20个广义特征值时与子空间方法的最大误差。其中bcsstk06/bcsstm06的阶数小,
软件时空
(上接第148页)在今后的工作中,将利用更加复杂的场景的视频数据检验算法的性能,并且希望能够进一步提高算法的执行效率,并加入多个目标,多向运动的跟踪,最终目标是建立一个能够准实时的,适合多种场景的人体跟踪系统。
本文作者创新点:本文在改进型混合高斯模型的基础上,引入粒子滤波器,并结合各自的优势进行人体目标跟踪,在光照干扰,树木摆动和阴影以及遮蔽干扰的条件下取得了良好的效果,证明了算法的有效性,验证了在有少量场景干扰的环境下仍然可以较好的完成跟踪的任务。
bcsstk26/bcsstm26的最大带宽相对应矩阵阶数较大,因此只做2、3个子结构的分解,不做5个子结构分解。
表2特征值误差
5结论
针对大型矩阵广义特征值问题,简要介绍了直接变换法;提出一种基于直接变换法的矩阵分解算法,该算法在一定程度上满足了优化条件;在分析了矩阵存储技术基础上给出了适合于直接变换法的高阶矩阵存储方式;设计DPC-DTM算法,并运用mpi和数学软件包CLAPACK实现了该算法;实验结果表明该算法误差小于3%,符合大型工程的计算要求。
本文作者创新点:提出并实现了一种面向大型带状正定矩阵运算的分布并行算法;给出了基于直接变换法的高阶矩阵存储方法;提出矩阵分解算法。
参考文献
[1]XJZhong.Arefinedsubspaceiterationalgorithmforlargesparseeigenproblems[J].AppliedNumericalMathematics,2000,32:35–52.[2]KSWu,HSimon.Aparallellanczosmethodforsymmetricgeneralizedeigenvalueproblems[J].ComputingandVisualizationinScience,1999,2:37–46.
[3]VHernandez,JERoman,ATomas.Parallelarnoldieigen－solverswithenhancedscalabilityviaglobalcommunicationsrear－rangement[J].ParallelComputing,2007,33:521–540.
[4]魏立峰.分布式环境下矩阵广义特征值问题的并行计算[D].博士论文.长沙:国防科技大学,2002.
[5]汪晓虹,陈怀海,等.模态综合的直接变换法[J].航空学报,2008待发表.
[6]汪晓虹,庄毅.基于直接变换法的并行算法[J].航空学报,待发表[7]吴建平,王正华,李晓梅著.稀疏线性方程组的高效求解与并行计算[M].长沙:湖南科学技术出版社,2004.5.
[8]GH戈卢布,CF范洛恩.矩阵计算[M].袁亚湘等译.北京:科学出版社,2001.8:177-178.
[9]DeinoSoftware©2006.MPIRoutines[EB/OL].[2008-08-06].http://mpi.deino.net/mpi_functions/index.htm.
[10]胡晓力田有先.混合编程集群研究及实现[J].微计算机信息,2007,11-3:252-253,233
作者简介:赵丽娜(1982-),女,汉族,硕士研究生,南京航空航天大学计算机应用专业,研究方向为分布计算;庄毅,(1956-),女,汉族,教授、博导,南京航空航天大学信息科学与技术学院,研究方向为网络安全、分布计算。
参考文献
[1]GRIMSONW,STAUFFERC,ROMANOR.Usingadaptivetrackingtoclassifyandmonitoractivitiesinasite[C]ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition.Washington,DC:IEEEComputerSociety,1998:22-31.
[2]STAUFFERC,GRIMSONW.Adaptivebackgroundmixturemodelsforrealtimetracking[C]ProceedingsofIEEEInternationalConferenceonComputerVisionandPatternRecognition.FortCollins:IEEEPress,1999,2:246-252.
[3]STAUFFERC,GRIMSONW.Learningpatternsofactivityusingreal-timetracking[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2000,22(8):747-757.
[4]毛燕芬,施鹏飞,基于采样理论的序列蒙特卡罗车辆跟踪算法[J].系统仿真学报,2004,(11)
[5]陈睿,刘国翌,赵国英,张俊,李华,基于序列蒙特卡罗方法的3D人体运动跟踪,计算机辅助设计与图形学学报2005.(1)
[6]张雷,刘冀伟,王志良,固定场景下的运动检测与运动跟踪,微计算机信息,2006,9-1:287-2
作者简介:张金花(1980-),女(汉族),甘肃金昌人,现就读于兰州大学信息学院,硕士,主要研究方向为视频中运动目标的检测与跟踪。Biography:ZHANGJin-hua(1980-),Female(han),GanSuProvince,studyinginInstituteofInformationScienceandEngineering,LanZhouUniversity,Master,researchmovingobjecttrackingofhu-man-body.(730000甘肃兰州兰州大学信息科学与工程学院电路与系统研究所)张金花薛峰李柏年王辉
(714200陕西渭南中国华阴兵器试验中心)朱望飞
通讯地址:(730000兰州大学信息学院电路与系统所)张金花
(收稿日期:2008.11.24)(修稿日期:2009.02.24)
技术创新
(上接第156页)[2]MengWan,Jean-YvesHerve.Adaptive,Region-based,Lay－eredBackgroundModelforTargetTracking[A].Proceedingsofthe18thInternationalConferenceonPatternRecognition(ICPR'06)[C].IEEEComputersocietyPress,2006.0-7695-2521-0/06.
作者简介:李德亮(1982-),男,江苏盐城人,硕士研究生,主要研究方向是信息融合技术、智能信号处理技术;林家骏,男,教授,博士生导师,主要研究方向为信息融合、图片隐藏信息检测、信息安
全、智能信号处理。
Biography:ZHAOLi-na(1982-),Female,Han,Master,NanjingUniversityofAeronauticsandAstronautics,ComputerApplicationTechnology,researchinDistributedComputing.(210016南京南京航空航天大学)赵丽娜庄毅汪晓虹通讯地址:(210016南京市御道街29号182信箱)赵丽娜
(收稿日期:2008.12.02)(修稿日期:2009.03.02)
(200237上海华东理工大学自动化研究所)李德亮林家骏(ResearchInstituteofAutomation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)LIDe-liangLINJia-jun
通讯地址:(200237上海华东理工大学自动化研究所)李德亮
(收稿日期:2008.11.22)(修稿日期:2009.02.22)
《PLC技术应用200例》
邮局订阅号：82-946360元/年-159-
