有限元方法历史简介
我的图书馆
有限元方法历史简介
有限元方法历史简介取自Wikipedia的免费百科全书数学有限元方法（FEM）是用来求偏微分方程式（PDE）的近似解，也求积分方程式，例如热传输方程式。求解方法是基于完全取消微分方程式（稳态问题），或把偏微分方程式（PDE）译成等效的常微分方程式，然后采用像有限差等标准的技术求解。在解偏微分方程式时，主要的挑战是创建近似研究的方程式，但数字稳定，这意味着在输入数据和中间计算都不会聚集错误，并造成无意义的输出结果。有许多这么做的方法，它们都有各自的优缺点。对于求解复杂域（像汽车和油管道）偏微分方程式，或当希望在全部范围精确变化时，有限元方法是好的选择。例如，在模拟地球气候模式时，在土地和完全开放的海域之上有着准确的预测是非常重要的，采用有限元方法，这个要求是可以做得到的。1&&历史有限元方法起源于需要解决市政工程和航空工程方面复杂的弹性结构分析问题。它的开发可以追溯到A.Hrennikoff（1941）和R.Courant（1942）的工作。虽然这些先驱者使用这些方法，并且引人注目的不同，但他们都共享一个基本的特性：把连续域的网格离散化进入一组离散的子域里。Hrennikoff的工作是采用格子使域离散，而与之类似，为了求解起源于汽缸扭转的问题的二阶椭圆的偏微分方程式（PDEs），的方法是把域划分成有限的三角形子域。对于由，和开发的偏微分方程式（PDEs），的贡献是改进，绘制了大量的早期结果。针对机身和结构分析的有限元方法的开发最早开始于1950年代中期，并且用于市政工程的有限元方法许多是1960年代在伯克利开始启动（见伯克利早期有限元研究）。在1973年和Fix出版的《有限元方法的分析》里，提供的方法采用了严格的数学基础，并且已经在广泛变化的工程学科，即电磁和流体力学里，针对物理系统的数字建模，归纳成为应用数学的分枝。在结构力学里，有限元方法的开发常常是基于能量理论，即虚功原理或最小总潜能原理，对于结构工程师来说，早就强烈要求提供综合的，直觉的和物理的依据。2&&技术讨论我们将从可以推断的普通方法里取二个简单问题来举例说明有限元方法。我们假设读者是熟悉微积分学和线性代数。我们将采用一维空间&式中f是假设的，而u是x的未知函数，并且u〞是与x有关的u的二阶导数。二维空间取样问题是狄利克雷问题式中Ω是在（x，y）平面内连接开区域，那些边界是“和谐的”（即平滑流形或多边形），并且uxx和uyy，分别表示与x和y有关的二阶导数。通过计算不定积分，可以“直接”求解问题P1。然而，只有当只有一个维度空间时，才使用这个方法求解边界值问题，并且不推广到更高空间的问题，或像u+u”=f问题。出于这个原因，我们将针对P1开发有限元方法，并且略微叙述它对P2的广义性。我们的解释将发生在二个步骤里，反映出二个本质的步骤，第一步必须采用有限元方法（FEM）求助于求解边界值问题（BVP）。在第一步，在它的弱或变分形式上重新描述初始的边界值问题（BVP）。通常这一步几乎不需要作计算，只是在纸上手工进行转换。第二步是离散化，在有限的维度空间里，把弱形式离散化。在这个第二步之后，对于大的，但是有限空间的线性问题，我们有具体的公式，那些解将近似解答初始的边界值问题（BVP）。然后就在计算机里执行这个有限的空间问题。3&&&变分公式化第一步是把P1和P2转换为它们的变分公式。如果u求解P1，那么对于任何平滑函数v，我们有反过来，如果对于假设的u，⑴控制每个平滑函数v(t)，那么一步就可以显示这个u将求解P1。（证据是非平凡的，并且采用Sobolev空间）通过在⑴的右边采用部分积分法，我们获得式中我们已经做了另外的假设v(0)=v(1)=0。4.1&&&&&存在的证据概要和解的唯一性我们可以定义是有界变分的(0，1)的函数，在x=0和x=1是0。这样的函数是“一次可微分的”，并且它产生出相对称的双线性图Φ，然后把定义的内积转换成为Hibert空间（详细的证据是非平凡的）。在另一方面，左侧 也是内积，这次在Lp空间L2(0，1)。针对Hibert空间的Riesz表示法则显示有一个唯一的u解⑵和因此的P1。4.2&&&&&P2的变分形式如果我们采用Green的理论做部分积分，我们看到如果u求解出P2，那么对于任何v：式中表示梯度，并且·表示二维平面里的点积。一旦在Ω的“一次可微分的”函数的匹配空间&里，能够把更多的Φ转换成为点积，那么 就是0。我们也已经假设&。空间 可能不再按照有界变分来定义，而是看Sobolev空间。也可以显示解的存在和唯一性。4&离散化&在里端点（蓝色）带有0值的函数和分段线性近似法（红色，参见直接强度图说里的彩图）。&在二维里的分段线性函数&基本函数vk（蓝色，参见直接强度图说里的彩图）和它们的分段线性线性组合。基本思想是替代有限空间的线性问题&采用有限空间的版本：(3)式中V是的有限空间子空间。V有许多可能的选择（一种可能导致spectral方法）。然而，对于有限元方法，我们取V为分段线性函数的空间。对于问题P1，我们取间隔（0，1），选择nx值0＜x1＜…＜xn＜1，并且我们定义V为&式中我们定义x0=0，和xn+1=1。依照微积分学的初步定义，观察V里的函数是不可微的。确实，如果 ，那么在任何x=xk，k=1，…，n处，通常是不定义导数的。然而，在x的每个其它数值里存在着导数，以及为了部分积分法的目的，同样可以使用这个导数。对于问题P2，我们需要V是Ω的一组函数。在右边的算式里，我们已经在平面里（三维图的下面）把15边多边形区域Ω划分成三角形，并且这个多变形的分段线性函数（上面带颜色的三维图）在三角系的每个三角形都是线性的；在选定的三角系的每个三角形上，空间V由线性函数组成。在文献里，经常用V代替Vh。原因是希望把下面的三角形格栅变得好上加好，离散问题（3）的解将在某种意义上聚集到初始边界值问题P2的解。那么就由取值很小的，h＞0的真实数值参数分成三角系。这个参数将涉及到最大，或三角系里的平均三角形的空间。正如我们定义的三角系，分段线性函数的空间V也必须改为h，因此没有符号Vh。由于我们没有执行这样的分析，我们将不使用这个符号。4.1&选择基础完成离散化，我们必须选择V的基础。在一维空间情况里，对于每个控制点xk，我们将选择分段线性函数vk，在xk，V里那些数值是1，在每个，V里那些数值是O，即&对于k=1，…，n。对于二维情况，我们按照平坦区域Ω的三角系的最高点的xk，再次选择一个基本函数vk。函数vk是V的唯一函数，在xk，那些数值是1，并且在每个，那些数值是0。根据作者的意思，在“有限元方法”里的“元”字，既涉及到领域里的三角形，也涉及到分段线性基本函数，或二者都涉及。作为例子，作者的兴趣在于采取舍弯取直，可以把曲线域改为三角形，在哪个情况里，他可以把他的元作为曲线描述。在另一方面，一些作者用“分段二次方程式”，或者甚至“分段多项式”来取代“分段线性”。那时作者可能说，“高次元”代替“更高程度的多项式”。有限元方法是不受三角形限制的（或在三维空间里的四面体，或者在多维空间里的更加高次的单形体），但是可以在四边形子域上定义（在三维空间里的六面体、棱柱、或者棱椎，如此等等）。可以采用多项式，以及甚至非多项式形状（即椭圆或圆）来定义更高次形状（曲线要素）。常常把采用更高程度分段多项式基本函数的方法称为光谱元方法，尤其如果多项式的次数增加，当三角系空间h趋于0。更加高级的执行（适用有限元方法）利用方法，（基于错误估计理论）评估结果的质量，并且在求解期间，根据连续问题的“精确”解，在某些限度之内，瞄准达到近似解来修改网孔。可以利用各种技术来适应网孔，最流行的是：移动节点（r-自适应性）精炼（和非精炼）元（h-自适应性）改变基本函数的次序（p-自适应性）上述组合（即hp-自适应性）4.2&基础的小支撑这个基础的选择的主要优点是内积&并且&几乎所有的j，k都将是0。在一维情况里，vk的支撑是间隔[xk?1，xk+1]。因此，只要|j?k|＞1，和φ(vj，vk)的被积函数同样是0。同样，在平面情况里，如果xj和xk，不共享三角系的边缘，那么积分&和&二个都为04.3&问题的矩阵形式和 ，那么问题（3）变成。(4) &&&对于j=1，…，n。如果我们用u和f表示列向量(u1，…，un)t，和(f1，…，fn)t，并且如果让L=(Lij)和M=(Mij)是那些输入为Lij=φ(vi，vj)和 的矩阵，那么我们就可以改写（4）为。(5).正如我们之前已经讨论的，因为基础函数vk有小支撑，所以大多数L和M的输入都是0。所以我们必须在未知u里求解线性系统，哪儿大多数矩阵L的输入都需要我们改为0。这样的矩阵就是著名的稀疏矩阵，并且针对这样的问题，有不同的解（比实际转化矩阵更加非常有效）。另外，L是相对称的，所以共轭梯度方法这样的技术就有用武之地了。对于不太大的问题，稀少的承载单元分解和分解仍然工作良好。例如，对于带有成百上千顶点的网格，的反斜杠算子（基于稀少的承载单元）就足够了。矩阵L通常是涉及到劲度矩阵，而矩阵M称为质量矩阵。5&&&&&&&&&&比较有限差方法对于求解偏微分方程（PDEs），是可以选择有限差方法（FDM）的。在有限元法（FEM）和有限差分法（FDM）之间的差异是：n&有限差分法（FDM）是近似于微分方程式；有限元法是近似于它的解。n&有限元法（FEM）最吸引人的特色是它能够相当容易的处理复杂的几何参数（和边界条件）。而在它的基本格式里的有限差分法（FDM）处理矩形形状是受限制的，并且简单的把它改造一下，在有限元法（FEM）里，几何参数的处理是理论上简单明了的。n&有限差分法（FDM）最吸引人的特色是它能够很容易的执行。n&有几种方法，一种可以把有限差方法（FDM）考虑为有限元法（FEM）的子集。一种可以选择基本函数作为分段持续函数或迪拉克三角函数。在二种方法里，在整个域定义近似值，但是必须不是连续的。作为选择，一种可以在离散域定义函数，结果连续的微分算子不再有意义，然而，这个方法不是有限元法（FEM）。n&有理由认为有限元近似值的数学基础是更加合理的，例如，在有限差方法（FDM）里，因为在格子点之间的近似值的质量是差的。n&有限元法（FEM）近似值的质量常常是比相应的有限差方法（FDM）高的，但是，这个是极端的问题，并且可以提供相反的个别例子。通常，有限元法（FEM）是在结构力学所有类型的分析里选择的方法（即在固体或结构动力学里求解变形和应力），而计算流体动力学（CFD）趋向于使用有限差方法（FDM）或其它的方法（即有限体积方法）。计算流体动力学（CFD）问题通常需要把离散化的问题分成大量的单元/格栅点（数百万和更多），因此，求解的成本偏于简单，在每个单元之内近似。对于“外部流”问题，比如像围绕着汽车或飞机的空气流，或在大范围内的气候模拟，这个是尤其正确。现在有大量的有限元软件包，有些免费，有些要付费。
TA的最新馆藏[转]&[转]&[转]&[转]&[转]&[转]&
喜欢该文的人也喜欢第１７卷第８期；２００５年８月；计算机辅助设计与图形学学报；ＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲ―ＡＩＤＥＤＤ；ｖ０１．１７，Ｎｏ．８Ａｕｇ．，２００５；有限元并行计算自动分区方法的优化；琥李光耀钟志华；长沙４１００８２）；（湖南大学机械汽车工程学院现代车身技术教育部重点；（ｗａｎｇｈｕｅｎｙｉｎｇ＠ｈｏｔｍａｉｌ．ｃｏ；摘要针对集群系统下动力学问题的大规模显
第１７卷第８期
２００５年８月
计算机辅助设计与图形学学报
ＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲ―ＡＩＤＥＤＤＥＳＩＧＮ＆ＣＯＭＰＵＴＥＲＧＲＡＰＨＩＣＳ
ｖ０１．１７，Ｎｏ．８Ａｕｇ．，２００５
有限元并行计算自动分区方法的优化
琥李光耀钟志华
长沙４１００８２）
（湖南大学机械汽车工程学院现代车身技术教育部重点实验室
（ｗａｎｇｈｕｅｎｙｉｎｇ＠ｈｏｔｍａｉｌ．ｃｏｒｎ）
摘要针对集群系统下动力学问题的大规模显式有限元并行计算的特点，在对多层次谱二分分区方法各个阶段
的算法进行分析和试验的基础上，对其相关阶段的分区策略和算法进行了优化和调整，提出了一种多层次谱二分优化分区方法，并应用该方法对不同几何类型的有限元模型进行了分区测试，得到了满意的结果．与多层次谱二分分区方法相比，多层次谱二分优化分区方法的分区效果和分区效率都得到了明显改善．
关键词分区；多层次谱二分优化分区方法；边权重优先匹配优化；顶点平衡策略；Ｌａｇｒａｎｇｉａｎ矩阵中图法分类号ＴＰ３３８．６
ＯｐｔｉｍｉｚａｔｉｏｎＣｏｍｐｕｔａｔｉｏｎ
ＡｕｔｏｍａｔｉｃＭｅｓｈＰａｒｔｉｔｉｏｎＭｅｔｈｏｄｉｎＰａｒａｌｌｅｌＦｉｎｉｔｅＥｌｅｍｅｎｔ
ＬｉＧｕａｎｇｙａｏ
ｏｆＡｄｖａｎｃｅｄ
ＺｈｏｎｇＺｈｉｈｕａ
Ｔｅｃｈｎｏｌｏｇｙ
ＬａｂｏｒａｔｏｒｙｆｏｒＶｅｈｉｃｌｅＢｏｄｙ
Ｄｅｓｉｇｎ＆ＭａｎｕｆａｃｔｕｒｅｏｆＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，ＣｏｌｌｅｇｅｏＪＭｅｃｈａｎｉｃａｌａｎｄ
Ａｕｔｏｍｏｔｉｖｅ
Ｅｎｇｉｎｅｅｒｉｎｇ，ＨｕｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ
４１００８２）
Ａｂｓｔｒａｃｔ
Ａｃｃｏｒｄｉｎｇ
ｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｌａｒｇｅ―ｓｃａｌｅｃｌｕｓｔｅｒｅｘｐｌｉｃｉｔＦＥＭｐａｒａｌｌｅｌｐｒｏｃｅｓｓｆｏｒｄｙｎａｍｉｃｓ
ｐｒｏｂｌｅｍ，ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓ
ｉｍｐｒｏｖｅｄａｕｔｏｍａｔｉｃｐａｒｔｉｔｉｏｎｍｅｔｈｏｄｍｏｄｉｆｉｅｄｍｕｌｔｉｌｅｖｅｌｒｅｃｕｒｓｉｖｅｓｐｅｃｔｒａｌ
ｂｉｓｅｃｔｉｏｎ（ＭＭＲＳＢ）ｂａｓｅｄ
ｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｔｏｔｈｅｍｕｌｔｉｌｅｖｅｌｒｅｃｕｒｓｉｖｅｓｐｅｃｔｒａｌ
ｂｉｓｅｃｔｉｏｎ（ＭＲＳＢ）ｍｅｔｈｏｄ
ｔｈｒｏｕｇｈｅｘｐｅｒｉｍｅｎｔｓａｎｄａｎａｌｙｓｉｓ．ＴｈｉｓａｐｐｒｏａｃｈｐａｔｃｈｅｓｓｏｍｅｄｅｆｉｃｉｔｏｆｔｈｅＭＲＳＢｍｅｔｈｏｄａｎｄｄｅｖｅｌｏｐｓｓｅｖｅｒａｌｐａｒｔｉｔｉｏｎｉｎｇｓｔｒａｔｅｇｉｅｓａｎｄａｌｇｏｒｉｔｈｍｓｉｎｔｈｅｐｈａｓｅｓｏｆｐａｒｔｉｔｉｏｎｉｎｇ
ｐｒｏｃｅｓｓ．Ｔｈｅｐａｐｅｒａｌｓｏａｄｏｐｔｓ
ＭＭＲＳＢａｌｇｏｒｉｔｈｍｐｒｏｇｒａｍ
ｔｏｃｏｄｅ
ｐａｒｔｉｔｉｏｎ
ｐｒｏｇｒａｍ
ａｐｐｌｉｅｄｆｏｒｄｉｆｆｅｒｅｎｔｇｅｏｍｅｔｒｙｓｔｙｌｅｓ．ＴｈｅＭＭＲＳＢ
ｐｒｏｖｉｄｅｂｅｔｔｅｒｐａｒｔｉｔｉｏｎｓｔｈａｎＭＲＳＢｍｅｔｈｏｄ，ａｎｄｐｒｏｖｅｓｉｔｓｈｉｇｈｅｆｆｉｃｉｅｎｃｙ．
Ｋｅｙｗｏｒｄｓ
ｖｅｒｔｅｘ
ｐａｒｔｉｔｉｏｎ；ｍｏｄｉｆｉｅｄｍｕｌｔｉｌｅｖｅｌｒｅｃｕｒｓｉｖｅｓｐｅｃｔｒａｌｂｉｓｅｃｔｉｏｎ；ｍｏｄｉｆｉｅｄｈｅａｖｙｅｄｇｅｍａｔｃｈｉｎｇ；
ｂａｌａｎｃｉｎｇｓｔｒａｔｅｇｙ；Ｌａｇｒａｎｇｉａｎｍａｔｒｉｘ
能满足需求．近年来，并行计算已经成为大型的有
引言限元模型计算的主流．
并行计算是可同时求解的多进程集合，这些进程相互作用和协调动作，并最终获得问题的求解．对于动力学问题的显式有限元求解来说，区域分裂法作为一种粗粒度的并行算法，以其对分布式可扩展并行计算环境的良好的适应性得到了广泛的应用．而有限元网格的划分方式，即并行计算任务的分
随着工程技术领域的不断拓展，出现了各种各样复杂的超大型结构．这些复杂的结构不仅具有庞大自由度，并且含有非线性本构关系、随机载荷和复杂边界条件等多种因素．这样复杂结构的有限元模型的计算量是非常巨大的，传统的串行算法已经不
收稿日期：２００４０３―１０；修回日期：２００４
基金项目：国家“八六三”高技术研究发展计划（２００３ＡＡ４１１２３０）；高等学校博士点基金（２００２０５３２０２１）；教育部优秀青年教师资助项目
（２００２０５３）；福特一中国研究与发展基金（５０１２２１５４）
８期王琥等：有限元并行汁算自动分区方法的优化
配方式对最终并行计算的效率高低有着决定性的影响［１］．
早期的有限单元分区方法是几何分割方法，该方法完全根据有限单元网格的空间几何特性来进行网格分割．由于几何分割方法仅考虑有限单元网格的几何特性，对于单元与节点间的相连情况与节点问的关联性（即其拓扑信息）则毫无考虑，因此实际工程应用中，几何分割方法的分割结果在边切数（指子区域的相邻单元或节点数目）的控制方面表现通常并不理想．
Ｆａｒｈａｔ在１９８８年提出任何自动有限单元网格分割的算法至少应满足以下三个基本的需求＿２Ｊ：
（１）能应付任何不规则的有限单元网格；（２）能达到各子结构运算量的平衡；
（３）能将各子结构问的边界节点数目减至最小．根据以上三个基本需求，Ｆａｒｈａｔ提出贪婪网格分割算法（ＧＲ）．由于ＧＲ分割法起始节点的决定与其分割结果有很大的关系【，Ｊ，不好的起始节点甚至可能使子结构产生分离的情况，所以当采用ＧＲ方法进行分区时，子区域之间的边界可能会很长，使并行计算的通信量大大增加．
Ｐｏｔｈｅｎ等于１９９０年提出了谱分割算法【４｜．该割与稀疏矩阵重排问题＿５Ｊ．虽然图分割的解空间为一离散空间，而且图分割为一个ＮＰ―ｃｏｍｐｌｅｔｅ问题，际上采用比较多的谱二分分割（Ｒｅｃｕｒｓｉｖｅ
Ｓｐｅｃｔｒａｌ
的计算时间．
为了避免因图过大而导致图分割算法耗费太多多层次算法将原来的图简化为一个较小但仍大万方数据
方法进行分区时，我们称其为多层次谱二分分区方法
（ＭｕｌｔｉｌｅｖｅｌＲｅｃｕｒｓｉｖｅ
Ｓｐｅｃｔｒａｌ
Ｂｉｓｅｃｔｉｏｎ，ＭＲＳＢ）．
ＭＲＳＢ方法和ＲＳＢ方法相比，处理器的开销大大减小，速度也有大幅度提升，是目前国际上比较通用的方法．但是由于粗化过程导致了结构拓扑信息的丢失，以至于出现各个分区的元素不均衡和边界过长等不良结果．为此Ｋａｒｙｐｉｓ等旧１提出ＲＭ（Ｒａｎｄｏｍ
Ｍａｔｃｈｉｎｇ），ＨＥＭ（ＨｅａｖｙＥｄｇｅ
Ｍａｔｃｈｉｎｇ），ＬＥＭ
（Ｌｉｇｈｔ
Ｍａｔｃｈｉｎｇ），ＨＣＭ（Ｈｅａｖｙ
Ｃｌｉｑｕｅ
Ｍａｔｃｈｉｎｇ）４种不同的粗化方法，但在实际的运用中还存在很多问题．
为了克服ＭＲＳＢ方法的缺陷，本文在ＭＲＳＢ方法的基础上，对该方法的粗化和还原阶段进行了优化，并对分区阶段采用的ＲＳＢ方法的存储模式进行
了修改，提出了一种新的分区方法――多层次谱二分
优化分区方法（Ｍｏｄｉｆｉｅｄ
ＭｕｌｔｉｌｅｖｅｌＲｅｃｕｒｓｉｖｅ
Ｓｐｅｃｔｒａｌ
Ｂｉｓｅｃｔｉｏｎ，ＭＭＲＳＢ），通过和ＭＲＳＢ方法相
比较，对其有效性进行了验证．
在讨论分区方法之前，先讨论有关衡量分区和时问ｆ。计算方法，在不考虑内存开销对计算时间影响的情况下，
ｔＤ＝ｒｓｔ＾＋ｆ∞＋ｆ。
Ｅｌｅｍｅｎｔ，
通常ｆ。，为所有ＰＥ执行并行化部分消耗时间最ｆ加＝篙ｆ。
＿；Ｎ为执行的ＰＥ个数，
ｔ，＝ｆ’（Ｎ，Ｍ）
ｓ广毒＝去
ｓ｛蓑＋了
式（１）中，由于＿在通常情况下总是满足０＜＿
方法是一种稀疏矩阵分割算法，同样也应用于图分但是谱分割算法将其解空间由离散转为连续，进而使图分割问题转化成为矩阵的特征值问题．目前国２分区方法对并行计算效率的影响
并行计算效率的一些概念．首先给出并行计算执行其中，ｆ。表示一个处理器单元（Ｐｒｏｃｅｓｓｉｎｇ
ＰＥ）上的执行时间；ｔ。表示并行部分的执行时间；ｔ，表示通信所耗费的时问；＿表示用一个ＰＥ执行时不可并行化部分所耗时间占ｆ。的百分比．
长者，当各个进程任务均衡时，并行部分的执行时问
Ｂｉｓｅｃｔｉｏｎ，ＲＳＢ）方法由谱分割方法发展而来．ＲＳＢ方法同前几种方法相比，有着严格的图形学基础，但是ＲＳＢ方法所形成的Ｌａｇｒａｎｇｉａｎ矩阵大小与总的单元数量成平方关系，这就消耗了大量内存；同时ＲＳＢ方法需要求解Ｆｉｅｄｌｅｒ特征向量，这也需要大量时间，多层次方法的技术被应用于图分割与网格分割的问题上．Ｂｕｉ等１６１首先将此概念应用于稀疏矩阵分解问题与图分割问题，Ｈｅｎｄｒｉｃｋｓｏｎ等。刊将ＲＳＢ方法稍作修改以更适合于图分割问题，Ｋａｒｙｐｉｓ等旧Ｊ还提出了几种改进的方法．
致保持原图的整体架构的小图，将该小图进行分割，此后再将小图还原．整个多层次算法大致可分为粗化、分割与还原三个阶段旧ｊ．在分割阶段，当采用ＲＳＢ
间占ｔ，的百分比，ｒ。＝１
其中，ｒ．为用一个ＰＥ执行时，可并行化部分所耗时
通信所耗费的时问ｆ，是ＰＥ数Ｎ和最大相邻ＰＥ数Ｍ的函数，并随着Ｎ和Ｍ增加而增大，即
计算机辅助设计与图形学学报
２００５正
＜１且总有通信开销，因此理论上加速比ｓ。总是小于ＰＥ数Ｎ，即有
但是在实际计算中可能会出现加速比Ｓ。非常近似于甚至大于ＰＥ数Ｎ，即可能出现超线性的加速比，这主要是由于实际的计算效率要受到内存开销的影响．在分区后，各个进程的计算规模大幅度减少，从而大大提高了各个进程的计算性能．
单位ＰＥ性能发挥比率７７定义为
由于在采用区域分割的并行计算中，需要预先给每个ＰＥ分配相应的计算任务，通常第一部分ｒ，ｔ。是固定的，此时要提高并行计算效率就是要设法减小并行部分的执行时间ｔ。和通信时间ｔ。．
在第１节曾提到Ｆａｒｈａｔ忪Ｊ对分区方法三条准则的定义，但是这三条准则仅仅考虑到并行程序的计算效率，而实际上网格自动分区的效率也是很重要的．如当采用ＲＳＢ方法进行分区时，由于建立Ｌａｇｒａｎｇｉａｎ矩阵需要消耗大量的内存，而计算特征量同时也需要占用大量的ＣＰＵ资源．为此，在以上三个基本需求的基础上，有限单元网格自动划分还必须满足以下两个条件：
（１）系统内存资源的最优化；（２）分区时间最优化．
ＭＭＲＳＢ方法
本节将针对ＭＲＳＢ方法的三个阶段进行分析，
并提出改进的策略和方法．３．１粗化阶段的优化
首先引进一个新概念：粗化因子．当粗化因子为１时，两个顶点合二为一；当粗化因子为２时，顶点集合的个数为４；依次类推，得到
Ｖ。＝２４
其中，Ｖ，，为顶点集合数目，（：厂为粗化因子系数．在该阶段将构建一个比原图小的小图，但仍大致保持假设粗化前和粗化后的图分别用Ｇ；＝（ｕ，万方数据
分别为ｗ，（Ｅ，）和ｗ，＋。（Ｅｉ＋１）．在理想的状态下，粗化前图的顶点数目为粗化后的２倍，即ｌＶ；ｌ＝
Ｉ，减少的权重数目可以表示为ｗ（Ｍｉ）＝
艿叫一÷ｌ，其中叫ｉ为平均权重，ｄ为粗化方法的系
数．对于ＲＭ方法，艿＝１；对于ＨＥＭ方法，艿＞１．根据以上假设，可以得到粗化图权重前后的关系为Ｗｉ（Ｅｉ）＝Ｗｉ＋Ｉ（Ｅｉ＋１）＋Ｗｉ（Ｍ，）．
在实际运用中，不同的粗化方式对于具有不同拓扑信息的图形粗化的效果是不一样的，根据我们
的测试，ＨＥＭ方法和ＨＣＭ方法的效果比较好，同上述理论分析吻合．由于结合点的权重和几何特征发生了变化，当继续下一次粗化时，效果并不理想．
本文在ＨＥＭ粗化方法的基础上，对其进行了
改进，提出了一种新的粗化方法――ＭＨＥＭ
（ＭｏｄｉｆｉｅｄＨｅａｖｙＥｄｇｅＭａｔｃｈｉｎｇ）．由于粗化前后的
权重和几何拓扑信息发生了变化，初始权重和几何信息已经不能成为粗化的依据，因此每一次粗化后，程序对粗化的图的权重和几何拓扑信息进行更新，建立更新的相关信息数组，再进行新一轮的粗化，可以达到较好的效果．
此外，在粗化过程中，粗化初始点的选择是很有学公式来表达，因此初始点的选择已经成为粗化方法的瓶颈．当初始点选择不当时，可能会引起以下问题：设点７．１ｉ和可，点是最优组合，如果在搜寻的过口，）必然会丢失，从而使得原图失去部分几何特性；图１
粗化造成孤立点实例
ＭＨＥＭ方法采用一种顶点结合策略――顶点
Ｂａｌａｎｃｉｎｇ
Ｓｔｒａｔｅｇｙ，ＶＢＳ）对初始
讲究的．初始点作为粗化的一种影响因子很难用数程中点训ｉ和点ｕ，均没有分配，那么程序可以获得最佳组合（训ｉ，口，）；反之，如果在搜寻过程中点ｕ，已经被分配了点７ｄ。作为优先组合，那么最优组合（口，，最差的可能是ｕ，找不到合适的配对点，必然形成孤立点（这种情况是很普遍的），会导致粗化图的新元素包括的元素不均等，在后续的分区中，会使二分的子区域所包含的单元有很大的差异，如图１所示．
原图的架构和形状．对小图进行粗化的过程中，选取数个顶点，将它们配为一个顶点，如此继续进行将使原图变为一个较小的图．粗化阶段中，粗化的动作可能不只进行一次，而是一次接着一次进行，直到图的顶点数目达到某个标准为止．
Ｅｉ）和Ｇｉ＋ｌ＝（Ｖｉ＋ｌ，Ｅｉ＋１）来表示，图的权重函数
平衡策略（Ｖｅｒｔｅｘ
点进行搜索，即在权重相同的前提下，子单元较多的
粗化单元和子单元较少的粗化单元进行结合，从而
王琥等：有限元并行计算自动分区方法的优化
满足单元边切数目的平衡，同时满足单元个数在各个分区的平衡性．此外，根据边切数目最小化的原则，对于起始点的选择采用权重优先原则，保持了原始单元图的几何特性．ＭＨＥＭ算法步骤如下：
Ｓｔｅｐｌ．获得图中各顶点的初始权重；
Ｓｔｅｐ２．对顶点权重进行排序，将权重最大顶点作为粗化初始点，并根据权重的大小来判断粗化顺序（权重大的优先）；
Ｓｔｅｐ３．得到当前粗化顶点集合的相邻顶点集合编号以及该顶点集合所包含的顶点数目；
Ｓｔｅｐ４．根据权重（权重大的优先）和顶点集合内的顶点数目（数目小的优先）ｉｇ择粗化集合；
Ｓｔｅｐ５．更新集合拓扑关系；Ｓｔｅｐ６．更新顶点集合权重；
Ｓｔｅｐ７．判断是否达到所要求的粗化度，是则结束，否则转Ｓｔｅｐｌ．
在该算法中，点集合是指粗化顶点结合的总称，当没有进行粗化时，顶点集合即为单个顶点．该算法的特点是将权重和计算量的平衡度的因素同时进行评估，找到一种相对最优的选择，从而大大降低了孤立点的出现频率，为后续阶段做好准备．３．２分区阶段的优化
在分区阶段，理论上可以采用任何一种分区方法，但为了使分区的结果基本满足分区的５点要求，本文采用ＲＳＢ方法进行分区．ＲＳＢ有着严格的图形学基础，但是ＲＳＢ方法所形成的Ｌａｇｒａｎｇｉａｎ矩阵大小与总的单元数量成平方关系，会消耗大量内存；同时ＲＳＢ方法需要求解Ｆｉｅｄｌｅｒ特征向量，也会耗费大量的计算时间．而且该方法是一种回归迭代算法，存储空间和计算时问进行合理的分配对该方法的为提高分区效率的瓶颈．为此，我们提出了一种全新的存储模式：二分三角形，对ＲＳＢ方法现有的存储模ＭＲＳＢ方法的分区阶段结束后，由于粗化过程以及ＲＳＢ方法本身的缺陷（见第２．１节），可能会产图２所示的粗化结果，如果对该图进行分区，可能会从图２不难看出，粗化后图分成Ａ，Ｂ两个区万方数据
图２粗化后分区效果
为了改善粗化分区效果，在图还原的过程中，必须对粗化后的分区进行优化．为此，我们引入了ＫＬ（Ｋｅｒｎｉｇｈａｎ―Ｌｉｎ）局部优化算法．ＫＬ算法【９Ｊ是一种图分割的最佳化算法，已有数十年历史，一般用于集为了避免执行时间过长，ＫＬ算法并不以所有的顶当子分区顶点数目存在差异时，会有部分单元不会中的单元渗透（即属于子分区Ａ的某单元或单元集ＫＬ）局部Ｓｔｅｐｌ．设有Ｇ（Ｖ，Ｅ）已被分割为两个子图，分别拥有Ｓｔｅｐ２．对两个子图进行平衡化
ａ．分别计算两个子图的相对于对方顶点集合的权重
（简称相对权重）眠．６＝砜．。，下标（ｎ，ｂ）表示子域Ａ中的
ｂ．对二个子域的顶点数目进行排序，（Ｍ，Ｎ。）分别
Ｍ―Ｎ。ｆ＞１时，对二子域进Ｃ．最终获得平衡条件ｌＭ―Ｎ６ｌ≤１．
Ｓｔｅｐ３．分别从Ａ与Ｂ集合中挑选交换可行性较高的顶Ｓｔｅｐ４．列出所有可能作为顶点交换的配对｛ｚ，，弘｝，其ｓｔｅｐ５．将该序列之前＾个配对，进行顶点交换的动作．
成电路的分区．其基本原理为：尝试子图之间的顶点交换动作，取其中能使边切数减少者，逐渐修饰其分割结果，重复执行直到终止条件成立为止．然而，点作为其尝试交换的范围，只取交换后使其边切数减少的可能性较高的顶点，作为其尝试交换的范围．经过这些顶点交换动作之后，通常能使修饰后的分割结果比原来的分割结果有较少的边切数．采用ＫＬ算法有一个前提：子区域中的顶点数目必须相同．进行优化处理，从而产生超长边界以及各个子分区合出现在子分区Ｂ的内部，可参见算例２）．因此，不能对粗化分区结果直接进行ＫＬ优化．本文对ＫＬ算法进行了改进，提出了ＢＫＬ（Ｂａｌａｎｃｉｎｇ优化算法，ＢＫＬ算法步骤如下：
顶点集合Ａ和Ｂ．
计算效率至关重要，传统的ＲＳＢ方法的存储模式成式进行了改进，取得了不错的结果，将另文撰述．３．３还原阶段的优化
生顶点集合不平衡甚至产生孤立点的情况．针对如产生以下分区效果．
域，在理想的状态下，Ａ区域的顶点数目应该和Ｂ区域的顶点数目相等，边切数目达到最小．而实际上Ａ子域的顶点数目为６，仅仅是Ｂ子域数目的一半，更谈不上边切数目的最小化．
顶点集合相对于子域Ｂ的权重，同理（ｂ，。）表示相应含义．
代表子域Ａ和Ｂ的顶点个数，ｆ行平衡化，将顶点个数较大的子域为Ａ时，相对权重最大的（Ｎｄ―Ｎ。）个顶点由Ａ子域并归到Ｂ子域，记为Ａ―Ｂ．
点集合ｘ与ｙ，作为尝试交换的范围．
中Ｘｉ∈Ｘ，拂∈Ｙ，并将交换后的边切数目按减少数目排序（降序排列）．
汁算机辅助设计与图形学学报２００５年
ＳＩｅｐ６．重复执行Ｓｔｅｐ３，直到ｋ＝０为止．Ｓｔｅｐ７．当Ｎ。
Ｎ＾＝１时，由于不满足ＫＩ。算法的条
件，必须对最后一个顶点进行判断．分别求出该顶点相对于二子域的权重，选择权重大的子域作为该顶点的并归域．
４算例与比较
为了验证本文提出的ＭＭＲＳＢ方法对ＭＲＳＢ优化的效果，下面分别对平面、三维曲面以及三维实体三种不同的几何结构进行分区测试，比较分区的优劣．以下算例为８分区测试，粗化因子为２．
算例１．图３ａ所示为ＭＲＳＢ对原始有限单元
ＭＲＳＢ分区效果
ＭＭＲＳＢ优化效果
的分区效果，图３ｂ所示为采用ＭＭＲＳＢ方法对该问题的分区．对两种效果进行对比，图３ａ所示的边
界明显长于图３ｂ，子分区还出现了单元渗透（黑框
图４算例２分区效果
标识处），这就大大增加了有限元计算的通信量．而采用ＭＭＲＳＢ方法则避免了这种现象的产生．
ＭＲＳＢ分区效果
ＭＭＲＳＢ优化效果
图５算例２分区局部边切效果
ＭＲＳＢ分区效果ｂＭＭＲＳＢ优化效果
很明显，本文提出的ＭＭＲＳＢ方法边界光滑，明显优于ＭＲＳＢ方法．二者边切数目之比为１２：１５．
算例３．对实际工件的有限元模型进行分区．
图６ｂ，６Ｃ所示为分别采用ＭＲＳＢ和ＭＭＲＳＢ方法
图３算例１分区效果
算例２．图４ａ所示为ＭＲＳＢ对原始有限单元的分区效果，图４ｂ所示为采用ＭＭＲＳＢ方法对该问题的分区．该算例从两个方面对ＭＭＲＳＢ方法的优化特点进行了验证，图４中部的小图是由ＭＲＳＢ分区所造成的孤立区域，这对于该问题进行并行计算程序的运算效率影响很大．为了方便对二者分区后的边切数目进行对比，我们取出局部区域，对其进行比较，如图５所示．
的分区效果．观测放大后的效果图７（位于整体图的黑框处）可见，在工件中部和端部，采用ＭＲＳＢ方法分区明显会导致产生较长部分的边界以及单元渗透（在放大图中的圆环区域内），而ＭＭＲＳＢ方法则基本避免了这种情况的出现．
ａ有限元网格模型
ＭＲＳＢ分区效果
ＭＭＲＳＢ优化效果
ＭＲＳＢ分区效果
ＭＭＲＳＢ优化效果
图６算例３有限元模型及其分区效果图７算例３局部放大图
比较以上算例的分区效果图，从平衡和通信的角度上看，本文提出的ＭＭＲＳＢ方法均优于ＭＲＳＢ
方法．为了比较二者分区的优劣，我们引进两个评
价参数对以上分区效果进行比较：平衡度和平均边
三亿文库包含各类专业文献、幼儿教育、小学教育、外语学习资料、专业论文、高等教育、应用写作文书、中学教育、有限元并行计算自动分区方法的优化_图文71等内容。　
　数学公式推理的方式, 由有限元问题的微分方程表达式及其求解算 法自动产生有限元...有限体积并行程序自动生成系统 ? 任意物理场自动并行耦合系统 ? 并行自动分区系统... 　基于MPI+FreeFem++的有限元并行计算_信息与通信_工程科技_专业资料。基于 MPI+FreeFem++的有限元并行计算 摘要:有限元方法是一种灵活而高效的数值求解偏微分方程... 　是对于结构力学分析迅速发展起来的一种现代计算方法。...版是基于新的 GPU/CPU 混合架构的并行有限元计算...1978 年 SAMCEF 优化模块 OPTI 推出。 1980 年非... 　一种改进的基于线性有限元并行计算的追赶算法_专业资料。一种改进的基于线性有限元并行计算的追赶算法 摘要 随着有限元计算规模的扩大,有限元并行计算的作用日 益凸显... 　有限元网格自动生成的并行区域划分算法作者:呙嘉妮胡久乡卢正鼎 摘要:提出了一种基于网格生成递归法的并行区域划分算法,该算法依据网格生成代价 的估算分析, 采用迭代... 　面板坝三维有限元模型接触单元的自动生成及应用 43…...面板堆石坝三维非线性有限元并行计算 57……混凝土...水布垭面板堆石坝坝体分区优化有限元分析 90……有限... 　元计算FELAC并行版的产品功能_计算机软件及应用_IT/计算机_专业资料。诚信?公平...数学公式推理的方式,由有限元问题的微分方程表达式及 其求解算法自动产生有限元... 　内支撑有限元分析和优化有限元试验软件和优化软件为 ...取轮胎常压下的标准载荷 615kg 进行计算,并取内...6 执行迭代 本文选择自动执行多次迭代,迭代次数为 ... 　显式有限元并行计算方法.该方法针对 GPU 计算的特点...PVM 支持在虚拟机中自动加载任务运行,任务间可以相互...图算法的高度优化逐渐转向分布式并行大图处理的优化。...}