隐式重启动Arnoldi/Lanczos法的子区域并行算法
发布时间：2021-01-24 22:56
针对求解有限元分析的特征值问题,提出了一种隐式重启动Arnoldi/Lanczos方法的子区域并行算法。隐式重启动Arnoldi/Lanczos利用重启动技术以提高所需谱的收敛性,并能有效处理Krylov基形成问题、存储所需的内存问题、计算成本问题。并行算法中采取子区域接子区域方法、重叠和非重叠网格划分技术。采用压缩数据结构来储存系数矩阵。对Krylov的数值线性代数运算和隐式重启动法中的数值线性代数运算的并行化进行了研究。数值算例表明:该算法具有良好的适用性和效率,适合分布式储存体系的机群。
【文章来源】：应用力学学报. 2017,34(02)北大核心
【文章页数】：8 页
【部分图文】：
非重叠网格划分方式
226应用力学学报第34卷(N1)，位于划分界面上的节点分为主边界节点(N2)和从属边界节点(N3)，界面节点在第i个子区域中为主边界节点，而在共享该节点的所有其它子区域中为从属边界节点。不包含边界节点的单元为内部单元，而包含边界节点的单元为边界单元。区域划分如图3所示。图3非重叠网格划分方式Fig.3Anon-overlappingmeshpartitioningscheme图4重叠网格划分方式Fig.4Anoverlappingmeshpartitioningscheme3.2重叠划分对重叠区域划分，定义一组由其它分区的节点组成新节点，称为虚节点(N4)，由主边界节点N2和虚节点N4构成共享单元，将一组共享单元加到非重叠区域的网格形成重叠区域。图4表示重叠区域划分。3.3压缩数据结构压缩数据结构，如压缩稀疏行格式是基于图的数据结构。在有限元方法中，关联到网格的图总是无指向的，即，如果元素0ijk≠，那么元素0jik≠。文献[16]提出了一个CSR的变化格式，称为压缩稀疏行列格式(CSRC)。在CSRC格式中，对角线以下的非零元素存储在CSR格式，而对角线以上的非零元素存储在压缩稀疏列格式(CSC)。对角线的元素存储在一个单独的数组ad中、数组au存储上半部分，数组al存储下半部分。第i行的第一个元素用ia(i)定位，另一个数组ja存储元素ijk的列号。CSRC格式的主要优点是只需要存储数组ja所需内存的一半；用来存储非对角元素的两个数组能更快地进行内存访问。采取CSRC格式，算法3描述非对称情况下矩阵向量积的算法。doi=1，n/循环(loopover)ui=u(i)t=ad(i)*uidok=ia(i)，ia(i+1)－1/对方程i的下部非零项循环(loopoverthelowernonzeroentriesofequationi)jak=ja(k)t=t+al(k)*u(jak)p(jak)=p(jak)+au(k)*ui/上部列(uppercolumn)enddop(i)=tenddo图5非对称
，需要进行三级运算。Hk=QTHkQ，Tk=QTTkQ，Vk=VkQ(18)矩阵Q是Hk或Tk的一个因子，由于这些矩阵已复制，因而不需要进行通信。4数值算例本文数值计算是在DELL工作站机群上进行。该机群由4台双CPU的DELL工作站通过100.0Mbps以太网连接而成，共有8个CPU(2.4GHzXeonchips，512KBcache)，每个节点内存1.0GB。每台工作站都有真实的IP地址，使用消息传递接口(MPI)。操作系统为RedHatLinux9.0。4.1对称问题算例为测试算法的性能，以坝体及地基的二维平面应变模型作为算例，如图9所示，计算其特征值和特征向量。采用两个隐式重启动，建立一个50步的Lanczos分解，特征值收敛容许值取为1×10-10。进行重叠和非重叠区域划分，整个区域划分为与处理器数相等的子区域，每个子区域有大约相等的单元数。每个子区域映射到各相应的处理器。各处理器得到子区域单元数据后，相应子区域中的计算在各处理器中进行。划分的网格包含273827个8节点二次单元、1647436个自由度。图9坝体及其地基的计算模型Fig.9Themodelofdamandfoundation为评价并行性能，分别用1个、2个、4个、6个、8个处理器对所求问题进行求解。图10和图11分别显示了非重叠和重叠划分的算法加速比和效率，可见非重叠划分较重叠划分的加速比要大，计算性能更好。从中也可发现，随着处理器数的增加，计算性能变差，这是由于出现大部分数据通信和同步的PCG迭代部分增加，以及问题的粒度减小而造成，因而通信开销增加。图10对称问题算例的并行加速比Fig.10Parallelspeedupforsymmetriccase图11对称问题算例的并行效率Fig.11Parallelefficiencyforsymmetriccase图12非对称问题算例的并行加速比Fig.12Parallelspeedupfornon-symme
本文编号：2998082
【文章来源】：应用力学学报. 2017,34(02)北大核心
【文章页数】：8 页
【部分图文】：
非重叠网格划分方式
226应用力学学报第34卷(N1)，位于划分界面上的节点分为主边界节点(N2)和从属边界节点(N3)，界面节点在第i个子区域中为主边界节点，而在共享该节点的所有其它子区域中为从属边界节点。不包含边界节点的单元为内部单元，而包含边界节点的单元为边界单元。区域划分如图3所示。图3非重叠网格划分方式Fig.3Anon-overlappingmeshpartitioningscheme图4重叠网格划分方式Fig.4Anoverlappingmeshpartitioningscheme3.2重叠划分对重叠区域划分，定义一组由其它分区的节点组成新节点，称为虚节点(N4)，由主边界节点N2和虚节点N4构成共享单元，将一组共享单元加到非重叠区域的网格形成重叠区域。图4表示重叠区域划分。3.3压缩数据结构压缩数据结构，如压缩稀疏行格式是基于图的数据结构。在有限元方法中，关联到网格的图总是无指向的，即，如果元素0ijk≠，那么元素0jik≠。文献[16]提出了一个CSR的变化格式，称为压缩稀疏行列格式(CSRC)。在CSRC格式中，对角线以下的非零元素存储在CSR格式，而对角线以上的非零元素存储在压缩稀疏列格式(CSC)。对角线的元素存储在一个单独的数组ad中、数组au存储上半部分，数组al存储下半部分。第i行的第一个元素用ia(i)定位，另一个数组ja存储元素ijk的列号。CSRC格式的主要优点是只需要存储数组ja所需内存的一半；用来存储非对角元素的两个数组能更快地进行内存访问。采取CSRC格式，算法3描述非对称情况下矩阵向量积的算法。doi=1，n/循环(loopover)ui=u(i)t=ad(i)*uidok=ia(i)，ia(i+1)－1/对方程i的下部非零项循环(loopoverthelowernonzeroentriesofequationi)jak=ja(k)t=t+al(k)*u(jak)p(jak)=p(jak)+au(k)*ui/上部列(uppercolumn)enddop(i)=tenddo图5非对称
，需要进行三级运算。Hk=QTHkQ，Tk=QTTkQ，Vk=VkQ(18)矩阵Q是Hk或Tk的一个因子，由于这些矩阵已复制，因而不需要进行通信。4数值算例本文数值计算是在DELL工作站机群上进行。该机群由4台双CPU的DELL工作站通过100.0Mbps以太网连接而成，共有8个CPU(2.4GHzXeonchips，512KBcache)，每个节点内存1.0GB。每台工作站都有真实的IP地址，使用消息传递接口(MPI)。操作系统为RedHatLinux9.0。4.1对称问题算例为测试算法的性能，以坝体及地基的二维平面应变模型作为算例，如图9所示，计算其特征值和特征向量。采用两个隐式重启动，建立一个50步的Lanczos分解，特征值收敛容许值取为1×10-10。进行重叠和非重叠区域划分，整个区域划分为与处理器数相等的子区域，每个子区域有大约相等的单元数。每个子区域映射到各相应的处理器。各处理器得到子区域单元数据后，相应子区域中的计算在各处理器中进行。划分的网格包含273827个8节点二次单元、1647436个自由度。图9坝体及其地基的计算模型Fig.9Themodelofdamandfoundation为评价并行性能，分别用1个、2个、4个、6个、8个处理器对所求问题进行求解。图10和图11分别显示了非重叠和重叠划分的算法加速比和效率，可见非重叠划分较重叠划分的加速比要大，计算性能更好。从中也可发现，随着处理器数的增加，计算性能变差，这是由于出现大部分数据通信和同步的PCG迭代部分增加，以及问题的粒度减小而造成，因而通信开销增加。图10对称问题算例的并行加速比Fig.10Parallelspeedupforsymmetriccase图11对称问题算例的并行效率Fig.11Parallelefficiencyforsymmetriccase图12非对称问题算例的并行加速比Fig.12Parallelspeedupfornon-symme
本文编号：2998082
本文链接：https://www.wllwen.com/kejilunwen/yysx/2998082.html
