带状对称正定矩阵的并行Cholesky分解及其实现.pdf

带状对称正定矩阵的并行Cholesky分解及其实现 张健飞 姜弘道 (河海大学土木工程学院，南京，210098) zhj177间163.com 摘 要 带状对称正定矩阵的Cholesky分解在实际工程计算中占有重要的地位，其串行算法已经成 熟，但其并行算法由于对计算机体系结构的高度依赖性，仍受到广泛关注。对于稠密矩阵的并行分 解和向量机上的带状对称矩阵的并行分解，前人已经做了不少工作。本文基于网络机群这 一新的并 行计算环境和消息传递界面MPI给出了一种等带宽存储格式下的的并行Cholesky分解算法，算法采 用行卷帘存储方案和提前发送策略，从而减少了负载的平衡和通信时问，增加了计算通信的重叠。 数值试验表明，算法具有较高的并行加速比和效率。 关键字 带状对称正定矩阵;等带宽;并行计算:Cholesky分解;网络机群 引言 并行计算是近儿十年来随着并行计算机发展而发展起来的一门新兴学科，并且随着待求问题规 模的日益增大，越来越受到人们的重视，可以说并行计算是未来科学与工程计算的发展方向。目前 比较流行的并行计算机主要是分布式存储的多指令流多数据流 (MIMD)并行计算机，由于它是由 多台相互独立的处理机以一定的方式联结起来的新型计算机系统，因此无论是在运算速度方面还是 在存储空间方面，比起普通串行计算机都有了很大提高，从而极大地提高了解题能力。网络机群((PC Cluster)是近几年兴起的一种具有良好的性能价格比的并行环境，通常也可归为分布式存储的MIMD 并行环境. 在实际工程计算领域中，系数矩阵为带状对称正定矩阵的线性系统的求解是很常见的问题，例 如应用有限元求解结构力学问题时，如果节点编号按照一定的规则，则最后所归结出的线性方程组， 其系数矩阵大多具有对称正定和带状的性质。同时因为求解一个线性系统，其主要工作是计算系数 矩阵的分解。因此研究此类矩阵的并行分解算法有着重要的意义。 对于带状对称正定矩阵(SymmerticPositiveDefinitionMartix)，由于其自身的特点，采用稠密矩 阵的Cholesky分解方法显然是不经济的。因此需研究经济的存储方法和相应算法。对于这类矩阵通 常采用等带宽和变带宽两种存储方法。基于这两种存储方法的串行Cholesky分解已经有了很好的算 法，而其并行算法仍受到人们关注，这是因为并行算法对计算机体系结构的依赖程度远高于串行算 法。文[[1〕研究了向量机上基于等带宽存储的此类矩阵的Cholesky分解，文[2〕讨论了M工MD型并行 机上的此类矩阵在完全存储情况下的算法，文3【][4〕给出了分布式存储的MIMD型机器上的稠密矩阵 的并行分解算法。本文基于MPI和网络机群环境研究了带状对称正定矩阵在等带宽存储方式 卜的并 行Cholesky分解算法，并采用提前发送 ((SendAhead)的策略减少了通信时间。数值试验表明所得 的算法具有较高的加速比和效率。 1稠密矩阵的井行Cholesky分解算法 定理 超纷A是n淤对砂正龙宠洋,刀疙岔够一必男应一云三一舍矩群L,,P}魔h5屏一D,逆雳A=LDL, 索H刀劣 J旁元.清全力IF= 推论 窟黄A是。加对形卫)定矩阵，产侧声痊猫，时对房元0圣为F4l三房 禅L,逆撑A=L吸 、 珍 对于稠密矩阵适合在分布式存储的并行环境下运行的并行Cholesky分解算法，文[3][4]给出了 一部分算法，本文所给出方案的是在Cholesky分解的行格式算法上得出的。假设对称正定矩阵A, 只需其上三角部分。为减少负载不平衡，采用行卷帘分布存储。为节省内存，在 卜列算法中，上三 角矩阵L存放在A的相应位置。处理机联结拓扑结构为环形，如图I所示，这可以由MPI的虚拟进 程拓扑功能加以实现。下列算法给出的是第myid号处理机上的并行算法。 尸口 尸1 尸p-1 丁 图1处理机联结拓扑结构 算法 1押密笼洲劣产厅Cholesky分解