结构分析的并行预处理共轭梯度法.doc

结构分析的并行预处理共轭梯度法 张朝阳 孙炳楠 唐锦春 ( 浙江大学土木系, 杭州, 310027) 提 要 共轭梯度法 (C G 法) 和预处理共轭梯度法 (PC G 法) 由于其固有的并行性, 在有限元并行计算 中得到很大的重视. 本文对 C G 法和 PC G 法求解线性静力问题的并行算法给出了严密、清晰的数 学推导过程, 给出了适合于工程应用的简单有效的预处理矩阵, 并提出了单元预处理矩阵的概念, 有利于发展不同预处理矩阵的研究. 作者在局部内存式并行机 T ran sp u te r 上实现了该算法. 关键词: 有限元; 并行算法; 共轭梯度法 中图法分类号: O 242. 21 0 引 言 随着科学研究与工程技术的发展, 大规模科学计算变得越来越普遍, 计算机硬件的发展也 是日新月异, 计算机体系结构打破了传统的冯r诺依曼体系结构, 走向了并行化的道路. 相应 地, 适合于各种结构的并行算法和并行化软件也不断出现. 在有限元分析中, 经常遇到有限元方程组 K x = f 的求解问题. 在使用迭代法求解时, 并 行化的共轭梯度法及预处理共轭梯度法将传统迭代步中每一步的计算分解到各单元上进行计 算, 避免了形成总刚阵, 使得小型机求解大规模问题成为可能, 所以这种方法得到了广泛的重 视. 文献1 仅给出了 C G 法的推导, 本文给出 PC G 法的推导, 并提出单元预处理阵的概念, 不 需形成总体预处理阵, 为并行预处理阵的研究提供了一个有效的方法, 并解决了文献4 中的 并行算法仍需形成总体预处理阵的问题. 文献2 、3 论述了 C G 法与 PC G 法在共享内存式 并行机上的并行算法, 本文给出在局部内存式并行机上的并行算法及简明的数学推导. 另外, 很多文献 (如文献1 、4 、5 ) 中都未提到并行 C G 法和并行 PC G 法迭代初始值的选取, 本 文对这一问题作了论述. 1 有限元法公式 首先给出一些基本约定, 设:  V (e) — 相应于每个单元的单元向量, 即单元结点向量. V e — 各单元的V (e) 按单元编号顺序直接组合而未经装配的向量. V — 表示各单元的V (e) 经装配后的整体向量. V E 表示V 对各单元分配而形成的向量, 即V (e) 装配后再向各单元分配的量. V (E ) — 表示V E 相应于每个单元的单元向量, 即单元结点向量. 本文所说的“单元”的概念也包括“子结构”的含义. 注意本文约定的这些向量只是一种向 量定义, 不一定有物理意义, 但有限元方法中的结点力向量和结点位移向量也适用于这种定 义. 所以有限元原理的一些基本公式可表示如下: f (e) = K (e) x (E ) x E = A x f = A T f e f e = K eX E f e = K ex E f = A T KeA x = K x (1) (2) (3) (4) (5) 其中A 在有限元方法中称为局部化矩阵, 当取单元坐标系与总体坐标系一致时, A 是布尔阵, 其元素由 0 和 1 组成, 表达了单元间的连接信息; A T 称为整体化矩阵. 故有以下关系式成立: V E = AV V = A TV e V E = AA TV e (6) (7) (8) 根据局部化矩阵A 和整体化矩阵A T 的功能, AA TV e 显然等价于在整体上有关联的局部量求和 之后再将总体量向各单元分配, 即: ～ V E = 6  V (e)  (e)  i∈ad j. ( i) + V (e) (9) ～ 其中V (e) 表示单元 e 的相邻单元的结点向量, V (e) 表示单元 e 的结点向量, 6 也不是简单的向 ( i) (e) i∈ad j. 量相加, 而是按“对号入座”的原则相加, 即整体上相关联的局部量相加, 以装配成整体向量, i ∈ a d j. 表示单元 e 的所有相邻单元. 有了以上的约定, 我们就可推导C G 法与 PC G 法的并行算 法. 2 C G 法与并行 C G 法公式  的) : 众 所周知, 解线性方程组 Kx = f 的共轭梯度法迭代过程如下 ( 其中要求矩阵 K 是正定 u = Kp Α= rT r ?p T u n x new = x + Αp rnew = r - Αu Κ= rTew rnew ?rT r p new = rnew + Κp  (10) (11) (12) (13) (14) (15)