使刚度矩阵带宽最小的节点标号算法_程序及应用

江 汉 石 油 学 院 学 报 198 9年3月 JO U 丑N A 乙 O F JIA N G H A N P刀r 天O L召U材 IN S刀T U TE 第1 1卷 第1期 使刚度矩阵带宽最小的节点 标号算法 、 程序及应用’ 余 雄 鹰 傲械系力学教研室) 摘 要 本文介绍了目前常用的总体刚度矩阵带宽最小化的 R C M 算法 , 开发出了可在 旧M / 尸C 及其兼容机上运行的 「O R下RA N 程序 丫x y, 它与现有程序相比具有输入简单和应用 范围广等优点, 可适用于对用任意类型单元 (包括组合单元 )离散的连续体进行优化节点标号 , 使得由此而形成的总体刚度矩阵的带宽为最小 . 关键词 刚度矩阵; 带宽; 最小化; 节点标号 八 启分 ,扮 U 目幼 口 在对连续体进行有限元分析时 , 若总体刚度矩阵以等带宽方式存贮 , 则总体刚度矩阵 的带宽是一个重要参数 , 其大小直接影响到所需存贮空间的大小 、 计算速度的快慢和计算 结果精度的高低 . 而总体刚度矩阵的带宽取决于对离散连续体的节点标号和节点自由 度数 , 它与所有单元节点差中的最大值成正比 , 与节点的自由度成正 比 . 当单元类型选定 后 , 节点的自由度数也就定了 , 因此带宽要取决于节点标号方案 . 也就是说 , 要使带宽最 小 , 就要进行这样的节点标号 , 它能使得所有单元节点标号的最大差值为最小 . 文献[l] 介 绍了 R CM 算法 , 并给出了用 A L G O L 语言编制的程序和算例 , 效果很好 . 但在使用该程 序时, 输人数据的准备工作较复杂 , 尤其对于具有大量单元和节点的情况更是如此 并且 它只适用于对用单一单元离散的连续体进行优化节点标号 , 对组合单元情况就不适用了 . 另外 , 目前 A L G O L 语言已用得很少 . 实际使用该程序不方便. 为了克服上述不足 , 采用 FO R T R A N 语言编制了前处理程序和带宽最小化节点标号程序 , 并拓宽了文献 [ll 中程序 的应用范围 , 使其能适合多种单元类型及其组合的情况 . 本程序输人简单 , 逻辑性强 , 计 算速度快而且易读 . 1 R C M 算法 ‘ R CM 算法是基于图论理论 , 由 C ut h ill 和 M ck ee 提出并由 G co rge 改进而得到的 . 实 际上 , 当一连续体被离散并标号后 , 该离散体即为一标号图 G . 为了说明问题 , 本文直接 引用文献【11 所描述的算法 , 涉及到的有关图论概念可参考文献【1】和[2] . 其步骤如下 : * 1 9 8 8年6月收稿 ; 江 汉 石 油 学 院 学 报 第 11 卷 (I) 选图 G 中低度的顶点 U 作根 , 形成根在 U 的层次结构 L u( 仍 . (2 ) 用连续正整数对 L u( G) 按如下步骤重新标号 : ¹ 取根 U 为第 1 层 , 编号为 l; º 对第 2 层各点 , 按度的增加次序编号为 2 , 3, ⋯ , 灿 ; » 对于第 i 层 , 先取 i = 3 , 按度的增加次序先对第 3层内邻接于点 2 的顶点编 号, 从护 1开始 , 直至邻接于 凡2 的顶点编完号为止 . 以后逐层进行 , 直至全部顶点编号结束 . (3 ) 对新的标号图G 计算其带宽、 (4) 重新选择 G 的其它低度顶点 U 作根 , 重复(l ) , (2) , (3) , 然后取带宽序列中达到 最小带宽的那个编序作为最终编序 . (5 ) 将 由(4 )所得最终编序反编号 , 即吞的顶点编号。 一 i + 1用 i代换 , 这里 1== 1, 2 一 , ‘ n 为G 的顶点数 . 需要指出的是 , 文献【1]所给出的、 确定标号图 G 中低度顶点 U 的方法较为复杂 , 实 际上在离散的周围或面上的节点一般均为低度顶点 . 2 程序框图及说明 程序 Y x Y 的框图如图 1所示 , 其中的变量名和数组名与程序中使用的相同 , 具体意 义见说明 . 2. 1 程序框图(见图 1) 2. 2 变量说明 (l) 输人数据 : 人心一一低度顶点个数 ; 万矛- 一单元数 ; 刃刃‘一节点数 ; 刃矛‘. 一节点自由度 (对组合单元 , 取最大值) ; 乃了一一所有节点度的最大值 ; 五了万一一全部单元节点个数的最大值 ; 万刀仍心)一一低度顶点标号数组 ; L O C (万E , 材扔一一每一单元节点的总体标号数组 , L O c( L 刀指的是第弹元第J个节点的标号 , 对组合单元 , 若单元 I 的节点数 IJ 小于 汤了万 , 则 数组 L O C 的第 I 行第 刀十1至 五r万列的元素均补以零 . (2 ) 输出数据 : 五了刀刀一一原始节点标号的总体刚度矩阵带宽 ; 五了刀一一新的节点标号的总体刚度矩阵带宽 ; 万尤(刃万)一一对应于原始节点标号的新的节点标号数组 . 3 算 例 有了程序 Y X Y , 就可以对任意离散结构进行任意标号 , 通过程序 Y x Y , 可得出使 第 , 期 余雄鹰 : 使刚度拒阵带宽最小的节点标号算法、 程序及应用 总体刚度矩阵带宽最小的节点标号 . 下面我们通过 3 ,个算例来加以说明, 这 3 个算例在 IS M / PC 机上均在 2 秒钟内完成. 例 1 . 空间受剪弯曲板 如图 2 所示 , 一其离散单元为四节点四边形单元和三节点三角 形单元 , 节点自由度为 6 , 新节点标号如图 3 所示 , 带宽分别为 54 和 30 , 减少 44 . 4 % ‘ 例 2 . 空间三维刚架 如图 4 所示 , 其离散单元为二节点三维空间刚架单元 , 节点自 由度为 6 , 新节点标号如图 5 所示 , 带宽分别为 54 和 24 , 减少 44 . 4% . 例 3 . 空间梁 、 析架及受剪弯曲板的组合结构 如图 6所示 , 板元为四节点四边形单 元 , 梁元为二节点兰维空间刚架单元 , 朽架元为二节点三维杆单元 , 最大节点自由度为 6 . 新节点标号如图 7 所示 , 带宽分别为 138 和 % , 减少 30 . 4 % . 输人原始数据 : 变量: 刃口,刀万 .入尹 .刃万 ,M .对万 数组洲刀(N0 ), L 口侧刃万 ,衬闭 用连续正整数对 L y 编号 求每一节点相邻的节点号并 存贮在一维数组 刃双万万 , 刃幻中 求新节点标号的总体 刚度矩阵的带宽M 7’ 对每一点的相邻节点号从 ,J倒大重新排列,产生矩阵 N注(刃万.川 M Z》M B护 求原始点标号的总体 刚度矩阵的带宽材刀B MB十M r 反编号 对每一节点的相邻节点 , 以 它们的度(即相邻节点个数) 的大小从小到大重新排列 低度顶点用完否? 取MB = I丫 取一低度顶点 U 为 抵形成层次结构 L 。 二 吸丫 愉出数据: 变量:材刀刀j f刀 教组 :刃双万幻 图 l 84 江 汉 石 油 学 院 学 报 第 11 卷 恤 尸 、、 、 一 / / . \奋 、色 图 6 系 第 1 期 余雄鹰 : 使刚度矩阵带宽最小的节点标号算法 、 程序及应用 8 5 4 源程序 h度IN IM件M P R O G R AM O F N O D A L S C H EM IN G N U MB E R Y X Y 矛 每 25 l5 爸 D IM E N SIO N LO C(2 8 , 4 ) , N A (3 3 , 8) , N D (3 3) , N l(1 12 ) , N B (2) , N P(33 ) , N K (3 3) O PE N (1 , FIL E , 乍IN G 勺 R E A D (l , * )N E , N N , M , N o s N F , M N , N B , ((LO C (I , J) , J= l,M N ) , I , l , N E ) M B B = 0 N 4 ~ M N * N E D O 10 1 = l , N N n 二 0 K K = 0 D O 2 5 11 = 1 , N 4 N l(I 1)二 0 C O N T IN U E D O 1S J = l , M N A (I , J) = 0 C O N T I] 阿U E D O 20 ) , l , N E L 二 0 D O 3 5 K = l , M N IF (LO C(J , K ) . E Q . 0 )T H E N G O T O 4 5 E L SE L = L十 l E N D IF C O N T IN U E D O 30 K = I , L IF (LQ C (J , M) , N E . I)G O T O 3 0 D O 4 0 L L ~ l , L N l(I I+ L L )“L OC (I , L L) C O N T IN U E n = 11+ L 3 0 C ON T IN U E 2 0 C ON T刀陌U E D O 50 ) = l , 11-- 1 D O 6 0 JJ = J+ l , 11 IF (N l(JJ 卜N l(J)) 13氏120 , 60 120 N l(JJ) = l G O T O 6 0 130 IF (N l(JJ ) . E Q二】) G O T O 60 IA 二 N l(J’) N l(J)= N’I (J乃 N l(J刀= IA 60 CO N T IN U E 50 CO N T I⋯N U E D O 70 JJ = l , 11 IF (N l(JJ ) . E Q . I)G O T O 70 IF(N l(JJ ) . E Q一 l)G O T O 70 K K = K K + l N A (I , K K )二 N l(JJ ) 7 0 C O N T I] 阿U E N D (D , K K M R R , N A (瓦N D (D卜1+ 1 IF (M R R . G T . M B B )M B B = M R R 10 C ON T IN U E M B B = M B B * N F C * T O C A LL SU B R OU T IN E BW M IN C A L L BW M IN (M , N N , N O , N F , 1 M B , N A s N D , N P , N K ) C * T O O U T PU T R E SU L T S W R IT E ( * , 140 ) 14 0 F O R MA T (/ 6X ,下O D A L 1 N U M B E R IN N E W SC H E M E 1 CO R R E SPO N D IN G T O O N E , l 生N O LD SCH EM E今 .曰、”勺飞一4 40 · 8 6 。 江 汉 石 ·油 学 院 学 报 第 11 卷 !60 50 又50 W R仃E (长 , 16 0)N K FO R MA T (/ gX , 1 114 ) W R 仃E (* , 150) M B B , MB F O R MA T( / IOx 。勺及璐IN 人乙 BA N D W 飞D l, H M B B , 恤6, 5x, 啊EW BA N D WID T H M B 二 ,, 16 ) ST O P E N D 印 N P(I Q(l)) 二 M S N A (IQ(l) , l), 一N A (I Q(1), l) D O 60 1 , l , IA 冲田 “IQm M T 二 O CO N T刃闻U E D O 7 0卜 l,认 D O 80 1 , l , N D (伊m ) M Q , IA B S(N A仃Pm ,乃) IF(N A (M Q , 1)工T . 0 )G O T O 80 M T 二M T + l 夏Q(M钓 “MQ M S 二 M S+ l N沪(MQ)留MS N A (M Q , l)二 ~ N A卿Q , ; ) CO N T刀阿U E CO N T 刀阿U E IA = M T ’ IF(MS . LT . N N )G O T 0 50 M T 二 O · D O 90 1‘ l , N N M卜呷田 MQ , N甲m N A氏 l)“L八B S伽A氏飞》 D O 10 0 ) , l , N D 仍 IF (N , 伽A a, 刀). G E ,M S)G O T O l0() M S 二 N P似A a, 刀) CO N 们困[U E IF (M Q · LE · M S)M R 只0 M R ‘M Q一MS + 1 IF (M E. G T. M劝M T “M R CO N T 刀阿IJE IF (MT . G E . M B )G O T O 4 0 M B 二M T D O 200 ) , 1 , N N N P(刀二 N N + lee N P(I ) N K (J’) 二砂(J) 、 CO N T I] 可U E 翅 OO 一谷,于 C * SU B R O U T刀阿E BW M】N SU B R O U T IN E BW M IN (M , N N , N O , N F , 1 M B , N A , N B , N D , N P o N K ) D IM EN SI ON IP (2 oo ), IQ(2 O。), 1 N A (N N , M) , N B伽 0 ), N D (茂哟 , 1 N K (N rN ) , N P(N N ) D O 10 1 , l , N N ID “ N D (D D O 20 )‘ l, ID 卜1 MQ“N A O , J) M R “ N D 似Q) M S 二J D O 3 0 IA “ J+ 笼,m . MT , N D 甲A n , IA )) IF (M L . G E . M R )G O T Q 30 M R 二 MT M S . IA M S 二 IA CO N T仆rU E · N人a ,刀= N A a ,M S) N A仃,M S), MQ CO N 们[N U E 、 C ON T刃阿U E M B 二 1 . E 4 D O 4 0 】D ‘ 1, N O M S = l IQ(l), N B (】D ) IA o l 、鱼 10 0 犯 息 90加l0 2 oo 第 1期 余雄鹰 : 使刚度矩阵带宽最小的节点标号算法卜 程序及应用 · 87 · C O N们[N U E M B . M B * N F R E T U R N E N D 参 考 文 献 1 徐次达 . 华伯浩. 固体力学有限元理论 、 方法及程序. 北京: 水利电力出版社 , 一 19 8 3 : 95 2 范逢曦 . 图论方法及应用 . 太原 : 山西科学教育出版社 . 19 8 7 : 55 ~ 60 呼 体文责任编挥 : 巫长瑚 N O D A L S CH EM E . A L G O R IT HM O F M IN n 4UM B AN D W ID T H O F R IG】】) MA T R IX A N D IT S A PPL ICA T 10 N Y u X io n gy in g (刀‘Pl . of 凡lro leum 材侧功加‘r夕 ) A俪tr a c t 万 T h is PaPo r in tr o d u ce s R CM a lg o r ithm o f n o d a l sc h em e u sed to b r o a d ly m in im iz e th e b a n d w id th o f to ta l rig id m a tr议 .竹e F o r tra n p r o g r a m Y x Y ru n o n th e IaM / PC e o m p认t- er 15 d e v elo Pe d , w h ic h h a s a d van ta罗5 o f si m Pllty ‘ o f d a ta in p u t a n d w id e a pPlie a ti o n ctc . o v er th e fo rm e r , 5 Pr o g ra m . It fi ts fo r o Pti m iz in g n o d a l sc h e m e to c o n ti n u ity id e a ll ze d w ith a n y k in d o f e le m e n ts in e lu d in g e o m li n e d elem en ts w hieh ean m a k e th e b a n d w id th o f to ta l ri g id m a tr议 m in im u m . . K eyw o r d s ri g id m a tr议; b a n d w id th ; m in im u m ; n o d al sc h e m e @