（计算数学专业论文）非结构网格自动分区算法研究.pdf

摘要 本文从计算流体力学并行计算的区域分解方法静背景出发，研究了菲结构网格的 自动分医算法，从算法的瑷论到具体的应用作了较为深入的研究。 本文将网格分区问题转化为无向赋权图的分区，在图上研究分医算法。首先通过 图的顶点和边的收缩将图邂层缩小，然后在小圈上用初始分区算法将它划分为给定数 目的予隰，最后剥用映射鄹多分区调整策路将，l 、霾上懿分区绥化隧麴到原始曩。算法 结台了多层次瑟戆窝谱分嚣方法、k l 月f m 鹣纯箨法帮多分区谣熬爨貉等技术，霞保 持负载平衡和减小处理器之间的通信复杂度为霸标，具有高效、爱活、简便等特点。 本文还给出了几个非缭构网格分区算例，从简单的二维网格到复杂的三维网格， 在给出分区结果之后分析了算法的优越性。试黢表明，无论从分医时间还是从分区质 量上，都比传统的网梧分隧算法要合理一些。本文还结合e u l e r 方程的有限体积格式 积区域努瓣雾法对文孛熬繁法在滚薅力学并纷诗算中送行了遴一步貔验证，获数篷诗 算结莱可敬看出，本文撬獭豹算法能够穰好地缴用于诗算流体力学并行计算，具有 定的科举应用价值。 关键诵：并行计算、区域分辫、网格分区、圈分区、多层次方法、k l f m 精化算法、 负载乎衡、有限体积格式 a b s t r a c t b a s e do nt h ed o m a i n d e c o m p o s i t i o no f p a r a l i e lc o m p u t i n g i nf l u i dd y n a m i c s ，t h i st h e s i si s d e d i c a t e dt ot h er e s e a r c ho fa u t o m a t i cp a r t i t i o n i n ga l g o r i t l u mo nu n s t r u c t u r e dm e s h e s ， c o v e r i n gc o m p u t i n g t h e o r i e sa n dt h e i rp r a c t i c a la p p l i c a t i o n i nt h i st h e s i s ，g r i dp a r t i t i o n i n gi sc o n v e r t e dt oa r tu n o r i e n t e da n dw e i g h t e dg r a p h ，o nw h i c h p a r t i t i o n i n ga l g o r i t h mi ss t u d i e d 。f i r s t l y , t h es i z eo f t h eg r a p hi sr e d u c e db yc o l l a p s i n g v e r t i c e sa n d e d g e s t h e n ，e a c h s m a l l e r g r a p h i sd i v i d e di n t oac e r t a i nn u m b e ro f s u b d o m a i n sb ym e a f i so fi n i t i a l p a r t i t i o n i n ga l g o r i t h m f i n a l l y , t h e s es u b d o m a i n sa r e r e f i n e db a c kt ot h eo r i g i n a l g r a p ht h r o u g hm a p p i n ga n dm u l t i - p a r t i t i o n i n g r e f i n e m e n t s t r a t e g y c o m b i n i n gm u l t i l e v e ls c h e m e ，s p e c t r a lb i s e c t i o nm e t h o d ，k l f mr e f i n e m e n t ，a s w e l la sm u l t i - p a r t i t i o n i n gr e f i n e m e n ts t r a t e g y , t h ec o m p u t i n gm e t h o di sc h a r a c t e r i z e db y 蠢i 彝e f f i c i e n c y , f l e x i b i l i t y , a n ds i m p l i c i t yb e c a u s ei tb o t hm a i n t a i n sl o a db a l a n c i n ga n d m i n i m i z e st h ec o m p l e x i t yo f c o m m u n i c a t i o n a m o n gp r o c e s s o r s s e v e r a l p a r t i t i o n i n ga l g o r i t h m i ce x a m p l e si nu n s t r u c t u r e dm e s h e s ，r a n g i n gf r o ms i m p l e2 d m e s h e st oc o m p l i c a t e d3 do n e s 。a r ea l s og i v e ni nt h et h e s i s a n dt h ep a r t i t i o n i n gr e s u l t s a r ef o l l o w e db ya na n a l y s i so ft h es u p e r i o r i t yo ft h i sc o m p u t i n gm e t h o d 。e x p e r i m e n t s p r o v et h a t i ti sm o r ee f f e c t i v ea n dr e a s o n a b l et h a nt r a d i t i o n a lm e t h o d si nt e r m so f t i m ea n d q u a l i t yi np a r t i t i o n i n g t h em e t h o d i sa l s ot e s t e db yf i n i t ev o l u m es c h e m ea n d p a r t i t i o n i n g a l g o r i t h mo f e u l e re q u a t i o ni np a r a l l e lc o m p u t i n gi nf l u i dd y n a m i c s t h et e s t i n gr e s u l t s d e m o n s t r a t et h a tt h e s u g g e s t e dm e t h o di n t h i sm e t h o di so fp r a c t i c a la n ds c i e n t i f i c s i g n i f i c a n c ei np a r a l l e lc o m p u t i n g i nf l u i dd y n a m i c s 。 k e yw o r d s ：p a r a l l e lc o m p u t i n g ，d o m a i nd e c o m p o s i t i o n ，g r i d p a r t i t i o n i n g ，g r a p h p a r t i t i o n i n g ，m u l t i l e v e ls c h e m e ，k l f mr e f i n e m e n t ，l o a db a l a n c i n g ，f i n i t ev o l u m es c h e m e + i i + 南京航空航天大学硕士学位论文 1 1 研究背景和选题依据 第一章绪论 本论文的研究内容是非结构网格的静态分区算法，是为了适应国家计算流体力学 并行计算发展的需要，对国家的国防经济建设有着非常重要的意义。 随着计算机的飞速发展和数值计算方法的不断改进，计算流体力学越来越广泛的 应用于飞行器性能分析及飞行器设计领域中，而跨、超和高超音速复杂形状流场的空 气动力学数值模拟方法的研究，成为当前国内外计算流体力学领域一个重点研究方 向。实践中的问题规模异常巨大，计算区域往往是高维的、大范围的，其形态可能很 不规则，给计算带来很大困难，单靠计算机硬件的发展是远为不够的。因此，研究高 效率的计算方法在过去、现在和将来都是提高计算能力的重要途径。回忆二十世纪六 十年代有限元素法的出现、七十年代多重网格法的出现，无不如此。 区域分解算法是二十世纪八十年代崛起的新方向，由于该方法能将大型问题分解 为小型问题、复杂边值问题分解为简单边值问题、串行问题分解为并行问题，因此， 1 9 8 5 年以后研究渐趋活跃。1 9 8 7 年之后，每年召开一次国际会议，美、苏、法、意、 中国等数值分析学家竞相参加此项研究。如今，区域分解算法已成为当今计算流体力 学的热门领域，其趋势方兴未艾。 事实上，并行机的研制与应用水平已成为衡量一个国家科技、经济与国防综合实 力的一个重要标志，而经典的串行计算格局已不适应于并行计算机，传统的算法受到 挑战。如何构造高度并行的算法是提高计算速度的关键，我们面临的科学与工程问题 是如此之浩大，计算能力的提高有赖于计算机与计算方法两方面的发展，而区域分解 算法正是在这种背景下应运而生的。 作为区域分解方法的重要组成部分，灵活高效的网格划分算法对并行计算有着非 常重要的意义。目前针对网格划分算法的软件包主要有c h a c o 伫3 1 、j o s t l e 2 “、 m e t i s 2 ”、p a r m e t i s 30 1 、p a r t y l 3 ”、s c o t c h t 3 2 】和s - h a r p 3 3 】等，它们从静态划 分、动态划分、并行划分等角度提出了自己的算法，并都有一定的科学应用价值。 本文提出的算法也是一种静态网格划分方法，对给定的任何形状的非结构总体网 格，划分为适于计算的任意数目子区，并使用并行化程度对跨音速空气流场进行数值 模拟，该方法具备灵活、高效等特点，适用于二维复杂气动外形及三维状态，具有一 定的应用价值。 目前主要的静态网格划分方法主要有以下四种：几何分区法 9 , 1 0 , 1 2 , 1 9 1 ( g e o m e t r i c ) 、 组合分区法，1 7 ，3 4 3 5 1 ( c o m b i n a t o r i a l ) 、谱方法【1 3 ，1 4 t 2 0 ，2 1 2 2 1 ( s p e c t r a l ) 和多层次分区方 法5 ”，l ( m u l t i l e v e l ) 。本文中提出的是一种基于多层次思想的分区算法，无论从分 非结构网格自动分嚣算法研究 区效率还是并行化程度分析都体现了较高的科学计算价值。 l 。2 本文戆研究重点及凌容综述 本文的研究重点是构造一种高效灵活的网格分区算法，使得对于给定的非结构总 体网格，运用这种分区方法，能够将它划分为邋于计算的任意数目予区，并且适用于 二维复杂气动外形及三维状态。本文的主要内容如下： 1 瞬的l a p l a c e 谱理论 童溪疆究了无自蘧权瓣鹣l a p l a c e 矩薅犟羹它懿特征蓬、跨鏊淘爨翡篷蒺，疆及在 图的分嚣中的所起静作用。这一部分跌无向赋权图以及l a p l a c e 缀阵的基本概念入手， 简单地阐述了l a p l a c e 矩降和f i e d l e r 向量的几个基本性质，其目的熄为后面的图的谱 分区算法作一些准备。 2 。圈的分区算法 蓠笼簿摹奔绥了咫辫分嚣法、缝会分送法、遴分区法窝多屡次分嚣法等且耱常溺 分区冀法豹寡瑾，其中对零文算法孛溺至l 豹鞠荧算法徽了一定撼分析，然后详细给出 了本文中的图分区算法，从算法的理论到具体的实现作了详尽的阐述。 3 非结构网格分区 首先给出了非结构网格的数据结构以及如何构造网格的对偶豳，接着将图的分区 算法殿髑于 结构网格，农，并进幸亍了分析。 4 。在著行诗算孛豹疲麓 焱蕊一部分内容是将零文的网格分区算滋斑用于计算流体力学并行计算并给如 了计冀结果。 本文的主要贡献是提出了一种高效的网格囱动分区算法，该算法结合了多层次思 想和谱分区方法、k l f m 糟化算法、多分区调羧策略等。并且编制了谱二分法、多层 次谱= 分法帮本文中算法的诗雾瓠添程痔，黠港予二缝露三缝非缝掬藏稳遴霞了分嚣 测试，这鬻了毙较瑾意豹缀莱。 1 3 本文主要特色 本文在一些原有的理论及簿法的基础上，掇融了一种新的组合簿法，算法针对静 态嚣绥憨霹臻戆睡意数嚣貔分区透嚣疆究，德爨了鞍秀理怒熬效暴，茨主要特色如下： 1 算法执行速度辍快，努区质量较高； 2 算法思想非常简单，实现过程通俗易懂； 3 算法可移植能力强，程序可作为通用的分区软件。 南京航空航天大学硕士学位论文 第二章图的l a p l a c e 谱理论简介 在介绍图的分区算法之前，首先简单介绍一下无向赋权图以及它的l a p l a c e 矩阵 的一些基本概念和性质，作为文中谱分区算法的理论基础。 2 1 基本概念 2 1 1 无向赋权图 性质2 1 如果图g ( v ，e ) 是无向赋权图，i v i = n ，i e i = m ，并且对于每一对顶点”、 v 赋权值d 一则以下三个条件成立 ( 1 ) a 。，= a 。，“，v 矿( g ) ； ( 2 ) a 。0 ，当且仅当u 、v 是相邻顶点 ( 3 ) 口。o ，u ，v v ( g ) 图2 1 就是一个7 阶无向赋权图 图2 1 无向赋权图 矩阵a = 爿( g ) = 【口。，k 州。) 称为图的邻接矩阵。图2 1 的邻接矩阵如下 罄绥掏惩捂垂动势区算法磷褒 41 l1 l2 o 2 03 l3 02 oo 23 2 o 4o e 4 o3 1i l0 32 00 ol 3l 4 0 0 4 以上可以蒋出，无向赋权图的邻接矩阵为实对称矩降。 2 ， 。2l a p l a c e 矩阵 图的l a p l a c e 矩阵和它的特征值在数学、物理、化学理论研究中有潜十分广泛的 应用，从某种意义上说，l a p l a c e 矩阵的谱性质比图的邻接矩阵的谱性质更为重要。 定义2 1 绘定无向赋权图g ( 矿，嚣) ，它的邻接矩阵a = 爿( g ) = 【口。，】。州g ，定义图的顶 熹v 豹痉麓； 矗( v ) = 拜。 ( 2 1 ) “ 定义2 2 给定光向赋权图g ( v ，露) 及它的邻接矩阵爿= “( g ) = 口。l 。r ( g ) ，定义图的 l a p l a c e 矩孵为： q = q ( g ) = d ( g ) 一蠢( g )( 2 。2 ) 其中，d ( 囝怒由图的各个顶点的度组成的对角矩阵。 对于图2 1 ，它的l a p l a c e 矩降为： 缀嗳显，l a p l a c e 矩薛是靖稼靛，瓣塞它兹每一行露豢_ 乏嚣势0 。 下一节将描述匿的l a p l a c e 矩障以及它的特征值的慕零性质。 o 也e o o o 4 叫。蛰o q 7 o o o o 7 o o o屯t，o o o o之；屯o o o o 好乇以o o 屯 3 o o o o o o 鸯窳靛空靛天大学 囊圭攀像论文 2 2l a p l a c e 矩阵的性质 2 1 2 1 1 基本性质 定理2 1 1 。l 黼g 是一个无向赋投隘，联g ) 是它的l a p l a c e 矩阵，剐 ( a ) q ( 回只有实特征值： ( b ) 烈g ) 熄对称正半定矩阵； ( c ) q ( 国的最小特征值 = 0 ，其楣应的特征肉掇为( 1 , 1 ，。，1 ) 7 ，0 僚为矩阵g g ) 豹特征篷豹纛数等于缓袋匿g 瓣嚣不楣连鼹部谨令数。 矩阵烈的正半定性可由( 2 3 ) 给出。对于任意绘定的向量x r ”，霄 ( q ( g ) 冀，x ) = d 。，( x 。一x ，) 2 ( 2 3 ) u v e e ( g ) 设五五g 五是联g ) 的2 个特钲值，璺 i 五= 0 ，且五 0 当虽仅警髫g 是 连遥豹。 定理2 2 ，4 】给定具有鼯个顶点的图g ，有 ( a ) a 2 。a l “l m i n d ( v ) ；v 矿( g ) ) ： ( b ) 五m a x d ) + d ( v ) ；u v ( g ) ； ( c ) 鲡蒙g 是一个簿单蠢，期五作，等式成立警显仅当g 静 窝不遴遂； ( d ) 善 = 2 1 e ( g ) l = ，d ( ： ( 。) 磊怠惫m a x f d ( v ) ；v y ) ) ； 回五m a x i i f 乏i 两f i 石i 碍“e 矿( g x v 毋群) 。 2 2 2 图的代数连通度和f i e d l e r 向量 l a p l a c e 缒簿戆第二个最小黪锺篷磊在宅魏瘿蠢耱链篷孛占有最隽纛癸熬莛怠， 它已经受到人们的广泛关注。大部分的研究结果均来自著名的c o u r a n t f i s c h e r 原理f 5 】 鏊缝稳矮捂叁动分嚣冀法骥究 郴) 2 案紫 ( 2 4 ) 其中，o = ( o 0 。o ) 7 ，1 = ( 1 t ，1 ) 7 是对应 = 0 的一个特征向量。f i e d l e r 例给出了如 懿另一令表达式： 命题2 1 嘲 f i e d l e r g ( e 目是一个光向赋权图，它裔非负权值口则 d 。( 一氐) 2 郴冲”磐蓄专f 玎 8 5 ) 箕中，啦是所有非常向量x 每f 2 ( y ) 组成的集合。 f i e d l e r 将 ( g ) 称为图g 的代数涟通度，在这里不蹲详细描述。 同时，f i e d l e r 发现，x a g ) 对应的特征向量( 我们称之为f i e d l e rn i t ) ，尤其 是宅豹善个分塞懿镣号结魏，鸯麓箨霉骞趣匏整蒺，下嚣翻鑫足令与藏鞠荧熬往屡。 定理2 3 嘞设g 是一个连通的咒向赋权图，_ y = ( y ，) 州是它的f i e d l e r 向量，集合 s ( r ) = v v ( g ) i y 。一，) ，r 惫0 ； 则由联力中的元索构成的g 的予鞠是连通的。 蕹谂2 1 竣g 楚一个连逶懿茺隆鼷获錾，y = 咒) 。嘴) 楚宅蕊f i e d l e r 两爨，给定零 数c 0 ，并殿有 y ，c ，v v y ( g ) 令s 。= ( v l y ，。) ，s 2 = y ( g ) s l ，划分剐由s l 翻& 巾的元素构成的g 黪嚣个子图 熬是连逶鳃。 定理2 4 f 6 l 设g 是一个连通圈，y = ( y ，) w ( 。) 是它的f i e d l e r 向量，v 熙g 的一个顶 点( 切顶点) ，记图g - _ v 的各个部件分别为g l ，g 2 ，g ，则 ( a ) 如果虬 0 ，则恰有一个部件g 含有使彳导儿 0 。 ( b ) 如果y ，= 0 ，而且一些部件中含有正的和负的y 值的顶点的话，其它剩余 南京航空航天大学硕士学位论文 的部件中顶点的y 值均为0 。 定理2 5 6 1 设g 是一个连通图，y = ( y ，) 。是它的f i e d l e r 向量，则会出现两种可 能： ( a ) 图g 中存在唯一的块占o ，它里面的顶点的y 值既有正的又有负的，其它块 中顶点的y 值要么全是正的，要么全是负的，要么全是零。 ( b ) 图g 中没有这样的块，它里面的顶点的y 值既有有正的又有负的。在这种 情况下，存在唯一一个y 值为0 并且有一个y 值非零的邻接顶点的切顶点。 f i e d l e r 向量能够有效地应用于获得各种问题的好的试探性算法。在本文的研究 过程中主要应用f i e d l e r 向量对图进行分区，目的是得到较好的分区性能，具体细 节将在后面的章节中描述。 2 3 小结 本章简单介绍了无向赋权图的概念以及它的l a p l a c e 矩阵的一些性质，主要目 的是为本文后面的图的谱分解作一些准备工作，在文章的后续章节将详细介绍分区 算法以及图和它的l a p l a c e 矩阵的应用。 饕终擒翔捂垂囊分区舞滚蟒定 第三章图的分区算法 上一章简单介绍了无向赋权图的概念以及它的l a p l a c e 矩阵的一姥性质，本章将 在熨举一些避有豹算法之爱谨缁分绍无囱赋权霉的分医算法。 3 1 引言 图的分区( g r a p hp a r t i t i o n i n g ) 问题是将图的顶点集合分为p 个大小几乎相等的 子集，使德连接不同子集的边的数目最小。这个瓣鼷在许多领域中都礴嫩用，包括并 露秘学谤箨( p a r a l l e ls c i e n t i f i cc o m p u t i n g ) 、l 王务璃发( t a s ks c h e d u l i n g ) 戮及怒大鬟 模集成电鼹( v e r yl a r g es c a l ei n t e g r a t i o n , v l s i ) 设计等，图的分区闯麓可以庵如下 的定义描述： 定义3 1 对于给定的n 阶无向赋权图g ( 以毋，图的分区问题定义为将g 的顶点集y 分为k 个予集，记为“，n ，收，使得 k0 矿，= ，v i 歹， 嚣| = n k ，u ，致= 矿， 而且，g 的边集茁中两个顶点分潮位于不同的子集中的边的数露( 称为边切度) 蕞少。 图的分隧问题是n p 完全的1 ( n o n d e t e r m i n i s t i cp o l y n o m i a lt i m ec o m p l e t e ) ，然而 由于问题的麓要性，很多人试图去寻找一种合理的算法去解决，从而出现了很多比较 好的分区算法【t 8 ，9 ，1 0 ，1 2 ，1 3 ，1 4 ，1 5 ，1 6 ，1 7 ，1 8 ，1 9 瑚0 1 丑2 4 0 5 , 2 7 , 2 9 , 3 4 0 靶，大致有以下几类：几何法 b 1 0 , 1 2 , 1 9 、缎会法 7 , 1 t , 1 7 3 4 3 翻、谱方法【1 3 , 1 4 , 2 0 , 2 1 矧黧多鬃次方法 1 5 , 1 6 , 1 8 , 2 7 1 ；农遽喾情况下， 图静分区避簇是逶遗不繇的二分褰现懿。下嚣蓄巍麓擎奔绥一下这尼耱舞法。 3 2 图的几种分区算法 我们知邋，圈的分区阀题怒n p 完全的，因此，一般情况下，不可熊找到一种台 理懿多矮鼓辩羯算法去求簿一个爨豹绘定数嚣戆分滋，毽由予润题蕊熬黉缝，嚣奏参基 经发展了檄多解决这一向瑟静试探性算法，主要w 淤分为凡何法、缀合法、谱方法帮 多层次方法等。在这一节，我们将简单介绍一下这魑算法的原理，对予本文中用到的 算法，我们会较为详细地描述。 所谓的n p - 竞仝问题也就是完全多项贰非确定问题这种问题的解无法通过直接计算得到只能通过问接的 “猜算”来得刹，同时，这种问题的所商可能的解都可以在多项式时间内进行正确与否的判断。 8 南窳簸空藏天大学颞圭学锭论交 3 2 1 几何分区法( g e o m e t r i cp a r t i t i o n i n g ) 几何分医方法 9 , 1 0 , 1 2 , 1 9 1 是基于图的顶点坐标信息的一种分区方法，由予这种方法没 有考虑瑟瓣边翁连逶蛙，因我墩鹱没有透甥菠兹壤念。这秘方法一般誊接疲鼹于弼接 缒势区。梵了袋小纯并行计雾过程中处瑾器之淹的逶穗复杂度，尼簿分聪方法通常会 考虑最小化一个相关的量，比如说子区域边界的大小。 几何分鼷法只适用于给定网格结点坐标信息的情况，当然，大部分的科学问题中 涉及到的网格都会给出结点的溅标信息。这种方法的优点在于它的分隧速度非常之 快。然而，濑予没有考虑到嘲横单元之闼的邻接燕系，导致分区的质爨鞠蹲较差。 主要熬a 麓努嚣方法毒鞋下足耱： 坐标嵌套分解法( c o o f d i n a t en e s t e dd i s s e c t i o n ， q d ) 坐标嵌套分解法，也称循环嫩标二分法，它试图通过将网格沿坐标方向一分为二 来最小化予区域的边界长度。c n d 格式的分区过程如下：首先计算网格每个元素的 形心坐标，然后沿具有较长区域的坐标方向将网格元綮排序，并将网格一分为二产生 嚣个具有秘弼元素个数款子区，每个子嚣雾垂环按照这一方法分薅。魏下辫3 ，| 繇示： a )蝴 图3 1c n d 分区方法的8 分区过程演示 图( 鑫) 豹黑患代表嚣揍每个元豢麴澎心，营先滠蜜线方淘薅嚣霹揍一分必二，然嚣 再将每个予馘分鄹澄虚线方向分解；图渤给出了8 令分区的结果。 循环惯性= 分法( r e c u r s i v ei n e r t i a lb i s e c t i o n ，r i b ) c n d 格式的一个限制是它仪仅根据坐标轴方向进行分裂，在许多情况下，这种限 制会极大始终寒网穆分区的质爨。箍r i b 方法则对它进行了改进，将分嚣的方蠢定 秀露穆熬餐瞧蹩东方岛。蓬3 2 飨密了这嚣耱分区方法戆不露之楚。 嚣缝软弱捂耋动套区霎法臻究 矽矽 圈3 2c h r d 格式和砒b 擦戏慰嗣一弼播的分区，最然话者具有较小的分区边界 空闯馥线壤究技术 c n d 和r j b 格式对图的分区是将网格元素按其形心坐标投影到菜一坐标方向， 从而对网格谶行分区。空间曲线填充技术则更为灵活，它的思想是将网格元素按照其 形心坐标投影到空间一条填充曲线上，这条曲线填充了整个网格的所有元素。一旦构 造了这撩靛象馥线h9 】，整个阏疆裁萄鞋划分为县商稳同元素个数豹饪意令子嚣。如 下蚕3 3 掰示： 球体切割方法 详见 i o 。 罄3 3 零j 塌空润鏊线壤充技寒将霹耪划分藏8 个子区 3 , 2 。2 组会分区法c o m b i n a t o r i a lp a r t i t i o n i n g ) 在计算分区的时候，几何方法试图将那些在空问中横互之间距离较激的顶点组合 在一起，而并不考虑这些顶点嫩谮高度邻接。组合分区方法 7 , 1 1 , 1 7 , 3 4 , 3 5 】则恰恰相反，它 试图将高媵邻接的顶点组合在一起，而不考虑它们襁空间中相互之间的距离。也就是 南京航空航天大学硕士学位论文 说，组合分区方法是一种基于图的邻接信息的分区方法，而不是基于顶点坐标的。这 样，通过组合分区法生成的分区有较小的边切度，而且生成不连续子区域的可能性也 比几何分区方法要小。当然，由于组合分区方法的特性，使得其分区速度相对几何分 区法要慢，而且并行化程度也相对较低。 层次嵌套分解法( l e v e l i z e dn e s t e dd i s s e c t i o n ，l n d ) 如果分区中相邻顶点处于同一个子区域中，那么这样的分区就会拥有较小的分区 边切度。l n d 算法试图将一个仅含有单个顶点的区域通过增加邻接顶点的方法逐渐 扩大形成一个子区。具体过程如下：首先选取一个初始顶点，标记为0 ，然后将顶点 0 的所有相邻顶点标记为1 。接着，将那些同顶点l 邻接而且还未被标记过的顶点标 记为2 ，依次下去，直到将图的一半顶点标记完成。这样，已标记的顶点就被划分到 一个子区，未标记的顶点便位于另一个子区。图3 4 给出了l n d 算法的分区过程。 图3 4 l n d 算法生成的2 分区 l n d 算法生成的分区保证至少有一个子区是连通的，而且生成的分区质量要比几何 方法好一些，但是，即使选定了一个好的初始顶点，有时候未必能得到好的分区结果。 比如上图中的分区就不是最好的。目前，已经有一些算法对它进行了改进【7 , 1 1 1 。 k e r n i g h a l i n f i d u c c i a m a t t h e y s e s 算法( k l f m ) 一类跟图分区问题非常接近的问题是图分区的精化( p a r t i t i o n r e f i n e m e n t ) 问题。 给定一个图的初始分区，这类问题是要在保持负载平衡的条件下，通过调整策略减小 分区的边切度以改善分区的质量。本质上这类问题同图分区问题的区别仅仅在于它需 要有一个初始分区。当然，一个精化格式可以作为图的分区算法，只需给定一个随机 的初始分区。 给定一个图的两个分区4 和b ，它们将原图一分为二，精化算法的目的是要分别 从爿、口找到两个相同大小的顶点集合且y ，使得交换x 和b 、y 和a 中的顶点使得 能够最大程度地减小分区边切度，这样的交换过程一直执行到不能再对分区有所改进 为止。然而，这样的问题同图分区问题本是一样也是非常困难的。在这种情况下， 非结构网格自劝分区算法研究 k e m i g h a n 和l i n 【 1 在1 9 7 0 簪提出了一种解决这一问题的贪婪算法，我们稼之为l 文 葵法。 k l 算法由少数量的几步顶点传递过程组成。在每步传递过程中，算法重鬓找 到对分别来囱两个子区的顶点，并且交换它们所在的区域。找这样的顶点对的目的 怒为了最终能最大程度地致罄二分法豹分嚣震量( 即使肖的顶点对豹交换过程增热了 边饬度) 。一曼一对顶点被移动，则它翻就不会在这一步传递过程中被再次移动。警 所有的顶点都被移动过，这步传递过程结柬。在整个遂一步传递过程中，使得边切度 达到最小的状态被记录下来，当然，这一状态之后的所有移动将被阐滚。这一步传递 j 毫稷兹努区结鬃将终灸下一褥递过程匏拐戆分区。遂豢淫嚣下，k l 箨法在攫少懿咒 步之内就会收敛。k l 算法每一步传递过程的时闻复杂艘为o ( 1 1 2 ) 。下图3 5 显示了 k l 算法如何移幼找到的一对顶点： 滔冷 疆辫 豳3 5k l 算法对分区的调熬 1 9 8 2 年，f i d u c e i a 窃醚a 链酝y s 1 3 4 】挺臻彳k l 篓法貔一摹孛变葵 舔之为f m 算法) ， 它在不影响分酝效果的前提下改善了算法的运行时间。f m 算法同k l 算法本质上的 区别在于前者谯每一时间步仅仅移动一个顶点而并非个顶点对。f m 算法为每个子 酝域均设置了一个优先权队捌，由这个队列来决定顶点移动豹次序。在每一步传递道 穗之前，善宠诗算每个壤纛鹣“获稠( g a i n ) ”僮( 等予移动这个礤赢嚣勇一个予区 域的边切度的减小量，可能怒负值) ，然厢根据这个值的大小顺序依次将各个顶点放 入相对应的优先权队列中。谯某一步传递过程中，首先检查位于每一个优先权队列的 第一个顶点，热暴其孛只有一个臻点憨够转移到另一个予区域著旦不羧嚣受载乎鬻祭 髂，就将这个顶点移动弼这个子区域；如柒两个队尉的两个头顶点都满足移动条件， 则移动其中“敬利”值较大的顶点。当一个顶点从自己的区域移动到另外一个区域之 殿，它将从原来的优先权队剐中删除，同时还要修改它的邻接顶点的“获利”值。整 令一步簧递过髹褥在嚣令谯兔投酞剜中确定没有霉移动憨臻点之囊绥寒。嚣器，焱魏 期间，质量最商的分区结聚将被保存下来。f m 算法每步传递过稳的时间复杂鹰为 1 2 南京航空航天大学硕士学位论文 o ( i e i ) 因为k l f m 算法在执行过程中允许移动一些会暂时增加边切度的顶点，所以它 解除了某些局部最小( 所谓分区达到局部最小，是指将任何一个顶点从一个子区移动 到另一个子区都不会减小分区的边切度，意即每个顶点的获利值均为负数) 状态的约 束。 图3 6 演示了利用k l f m 精化算法调整一个初始二分区的过程。无向赋权图具有 2 0 个权值为1 的顶点，并且分区过程允许有1 0 的非平衡度。图中空白顶点表示将 要被移动的顶点，上面的数字代表各个顶点的获利值。可以看出，经过( c ) 和( d ) 两步 的调整，分区的边界度增大了，但是正因为如此，整个过程把图的原始分区从一种局 部最小状态调整到另一种局部最小状态，同时减小了分区边切度，提高了分区的质量。 虽然k l f m 格式能够避免局部最小，但仍然存在一定的局限性，利用k l f m 算 法构造的二分区严重依赖于初始二分区。又有许多技术试图通过移动一个顶点集合 ( 而不仅仅移动一个或者一对顶点) 去改善这些算法【3 5 】，结果显示这些技术在付出了 增加时间复杂度的代价下改善了k l f m 算法的分区效率。k l f m 类精化算法在图的 平均度较大的情况下效果更好【2 4 l ，而且，当平衡约束条件减弱的情况下，也显示出了 更高的效率。 非结构网格自动分区算法研究 ( a ) 边切度= 6 ( c ) 边切度= 7 ( e ) 边切度= 7 鼬 边切度= 4 图3 6k l f m 分区调整算法 边切度- 2 , 1 4 南京航空航天大学硕士学位论文 3 2 3 谱分区法( s p e c t r a lp a r t i t i o n i n g ) 另一种求解二分问题的方法是将分区问题转化为一个离散最优化问题，通过求解 它的最优解来达到分区的目的。然而，即使这样的离散最优化问题构造出来了，问题 的求解还是相当有难度的。正是由于这个原因，一类叫谱方法 1 3 1 4 2 0 2 1 t 2 2 】的分区方法 通过将这样的离散最优化问题转化为连续最优化问题来简化问题的求解。而连续最优 化问题的求解最终转化为对图的f i e d l e r 向量的计算。算法步骤如下： 算法3 1 谱二分算法 1 ) 计算图的l a p l a c e 矩阵； 2 ) 计算上的特征值和特征向量，在本文中采用块l a n c z o s c h e b y c h e v 算法1 ： 3 ) 将特征值从d , n 大排序： 五也 4 ) 选取最小的非零特征值记为旯r ，相应的特征向量记为x ，( f i e d l e r 向量) ： 5 ) 排序f i e d l e r 向量x ，中的元素； 6 ) 将x ，中的元素同图的顶点对应起来，寻求一条分界线将原网格图一分为二。 拌 谱分区方法比几何方法能够产生更高质量的分区，但是由于要计算矩阵的特征值 和特征向量，这样大大提高了计算的时间，尤其针对大规模问题，更是如此。因此， 发展产生了很多针对这种问题的加速算法，包括l a n e z o s 算法、多层次谱方法等等。 3 2 4 多层次分区法( m u l t i l e v e lp a r t i t i o n i n g ) 近来，一类基于多层次范例的分区算法 1 5 , 1 6 , 1 8 , 2 7 1 产生了。这种范例由三个过程组 成：图的粗化、初始分区和分区的细化回归。在粗化过程中，用顶点收缩的方法构造 了一个层次化的图的序列，最粗的图的顶点数目足够小。这样，在初始分区过程中， 对最底层的图的分区就非常快。最后，利用k l f m 类精化算法将分区从底层涂映射 回归到原始图。下图描述了这样的一个范例： 本部分块l a n c z o s - c h e b y c h e v 算法由南京航空航天大学理学院戴华教授提供。 非结构网格自动分区算法研究 租 化 过 程 初始分区过程 图3 7 多层次分区方法示意图 细 化 回 归 过 程 由于本文提出的算法也是基于这一思想，所以将在下一节详细给出整个过程的算 法实现。 3 3 本文中的分区算法 这一节是本文的重点内容，本文提出的分区算法是一种基于多层次思想的算法， 算法结合了多层次思想和谱分区方法、k l f m 精化算法以及多分区调整策略。算法主 要分三个过程：图的粗化( 图序列的构造) 、图的初始分区( 构造底层图的分区) 以 及分区的细化回归( 利用精化算法将分区逐层映射回原始图) ，整个算法的过程如图 3 8 。下面详细给出这些过程的算法实现。 3 3 1 图的计算机存储结构 在研究具体的分区算法之前，首先给出无向赋权图的计算机存储结构，见下表 南京航空航天大学硕士学位论文 表3 1 无向赋权图的计算机存储结构 变量名称变量描述 n n o d e s整型变量，存储图的顶点数 n e d g e s整型变量，图的边数的两倍( 即所有顶点的度的和) 整型数组，长度为n n o d e s + l ，依次记录每个顶点的邻接顶点在数组 i n e d g c se d g e s 中的起始位置，可以看出，i n e d g e s i + 1 - i n e d g e s i 即为顶点i 的度 e d g e s整型数组，长度为h e d g e s ，依次记录每个顶点的所有邻接顶点 n o d e w g t s整型数组，长度为n _ n o d e s ，记录每个顶点的权值 e d g e w g t s整型数组，长度为n e d s ，记录每条边的权值 按照这样的存储结构，图2 1 在计算机中存储如下： n n o d e s ：7 n e d g e s ：2 4 i n e d g e s ：0391 21 51 82 l2 4 e d g e s ：21 52 30654013162615104 4l3 n o d e w g t s ：4l 44 4 44 e d g e w g t s ：1 l 122l233122212l3331312l 下面分三个过程详细介绍本文中的分区算法。 。盎髅装法、 船。i m 村削也簟注， 图3 8 文中的分区方法示意图 1 7 吲 非结构网格自动分区算法研究 3 3 2 粗化过程的实现 粗化过程是一个循环过程，主要是边的收缩将原图一层一层缩小至预定大小。对 给定的图g ( d ，需要构造一个小图序列g ，( k ，e ) ，使得i e i i k 小大部分的粗化格 式都是将g 的一个顶点集合合并收缩为下一层的图g i + l 的一个顶点。 设k 是图g 。中收缩为图g + l 的顶点v 的顶点集合，为了最后能将分区很好的映 射回原图，需要在粗化过程中将一些顶点和边的信息一层一层传递下去。我们把顶点 v 的权值设置为集合吖中所有顶点的权值之和，把顶点v 的关联边设置为集合k ”中 顶点的关联边的联合。这样，粗化过程保证了以下两个性质： ( a ) 粗图上的分区的边切度等于细图上同一分区的边切度； ( b ) 粗图上一个平衡的分区映射到细图上时仍然保持平衡性。 这一过程每一步实际上就是实现一个边的收缩过程，这个过程的关键在于找到这 样的一个边的集合，也就是寻求图的一个最大匹配。所谓图的最大匹配，是一个最大 数目的边组成的集合，在这个集合中没有两条边与同一个顶点关联。然后将这些边收 缩形成下一层图的顶点。如下图3 9 所示： 图3 9 图的粗化过程 + 边的收缩算法有很多，本文引用的是h e a v ye d g em a t c h i n g ( h e m ) t ”】算法，这种算 法的基本思想是找到一个含有较大权值的最大匹配，这样能够使对粗化后的图的分区 具有较小的边切度。算法访问顶点的顺序是随机的，对于某一个被访问的顶点，h e m 算法根据它的关联边的权值的大小去搜索它的匹配顶点，也就是说，算法会找到一条 权值较大的边。算法不能保证找到的最大匹配具有最大的总权值，但是试验结果表明， 这样的算法效果不错。计算一个最大匹配的时间复杂度为d ( 旧) 。 在我的h e m 算法的实现过程中用到了两个数组，m a t c h 和m a p 用来分别存储每 个顶点的匹配顶点和每个顶点在下一层图( 粗图) 中的序号，对于一对匹配顶点( 1 l ，v ) ， 显然有m a p u = m a p v 1 。下面是具体的算法描述： 南京航空航天大学硕士学位论文 算法3 2 h e m 算法 ( 图的数据结构如表3 1 ) 初始化临时变量：n = 0 ，m a x i n d e x = 一i ，m a x w g t = 0 ； 初始化向量m a t c h 和m a p ，m a t c h i _ u n m a t c h e d ，m a p i 】= 一1 ，i = o ，n n o d e s 1 ； 生成一个由0 - n n o d e s 一1 组成的具有n n o d e s 个元素的随机向量p e r m 。 f o r m i o t on _ n o d e s 一1d o i = p e r m 【m ； i f m a t c h i 】- u n m a t c h e dt h e n ( 第i 个顶点未匹配) m a x i n d e x = i ； m a x w g t 2 0 ； f o r j = i n e d g e s i 】t oi n e d g e s i + 1 d o k = e d g e s u ； i fm a t c h k 2u n m a t c h e da n d m a x w g t e d g e w g t s j 】t h e n m a x w g t = e d g e w g t s u ； m a x n d e x = e d g e s j ； e n d i f e n d f o r m a p c i = n ； m a p m a x