三维问题的局部块分解及并行.pdfVIP

三维问题的局部块分解及其并行 吴建平 007 (国防科技大学计算机学院，长沙，邮：413) comcn) (Email：州p2000cn@yahoo 李晓梅 01 (总装指挥技术学院，北京，邮：1416) net (Email：Ixm@cctincn) 摘要文中首先利用块三对角矩阵的嵌套局部块分解构造了一类三维问题的不完全分解 预条件子，并针对模型矩阵，分析了预条件后的实际条件数，分析表明局部块分解是三维问 题的一种有效预条件。其次在考虑其高效并行实现的同时，分析了影响并行计算加速比的几 个因素。采用较大局部分解步长的预条件时，尽管迭代次数有较大减少，但由于每次迭代所 需时问较长，使得总时间反而增长，从而说明对三维问题，当取简单的局部块分解时效率最 高。最后，文中将所述预条件方法与传统预条件在某超节点MPP并行机上进行了实验比较， 结果表明文中方法具有高效性与较好并行性的特点。 关键宇对称正定矩阵，^f矩阵，条件数，不完全分解．预条件子 1．引言 许多物理应用问题归结为求微分方程数值解，其核心是高效求解线性方程组。直接解法 存储量与计算量一般很大，为此，迭代法越来越受重视，但迭代法面临不收敛与收敛速度慢 两个主要问题，构造预条件子是解决这些问题的有效途径。 不完全分解预条件是串行计算时最有效的方法之一。对从二维问题离散得到的线性方程 组，文献[1]中首先提出了利用块三对角矩阵块分解因子估值构造预条件子的方法，并在文 献[2]中对其加以改进，提出了一类局部块分解预条件子，分析与实验表明在串行计算时其 效率优于对角预条件【3]，块对角预条件[3]，SSOR预条件[41，以及基于阶矩阵思想的不 完全分解预条件[5][6]等常用的预条件。同时分析表明，该预条件能有效并行实现，实验结 果表明其并行性较好。 文中利用块三对角阵的嵌套局部块分解构造了一类三维问题的局部块分解预条件子，并 分析了模型矩阵预处理后的条件数，分析结果表明了该预条件的有效性。同时，文中分析与 实验表明，无论是串行还是并行，采用简单局部块分解的预条件CG计算时间均小于步长较 大的预条件。 2．三维问题的基本局部块分解预条件 考虑由m×m个块组成的块三对角矩阵 (1) A=tridiag(E(0，c(j)，F(i+1))， 其中每个E(f)，c(0，F(f)都是nxk阶矩阵且 C(i)=tridiag(G(i，，)，r(i，，)，H(i，，+1))， 解因子 L=tridiag(E(i)，D』(f)，0)， U=tridiag(O，I，97,。(f)F(f+1))， D。(f)=工。(Ou。(f)， 魄≯ 三，(f)=tridiag(G(i，，)，Dc(f，／)，0)， U，(f)=tfidiag(0，I，D；1(f，j)H(i，J+1))， 在且非奇异， U=tridiag(0，1，Djl(i)F(i+1))亦然，故此时可知B存在且非奇异。 阵的A为七点差分矩阵，特别地，当E(f)，F(f)，G(i，，)，H(i，，)均为单位矩阵，且 T(i，／)iT=tridiag(一1，6，一1) 时，称A为模型七点差分矩阵。 在以F分析中，将频繁利用与文献[2】中定理1类似的一个结论，即如果A=B-R，A对称 正定且凡对称半正定，则 r。(B一·一、≤!±旦!生：!!旦!墨!。 ‘