針對無網(wǎng)格并行計(jì)算的基于模糊均值聚類的分區(qū)方法

摘要：針對國際上普遍采用的基于回歸幾何二分的分區(qū)方法的缺陷，提出了基于模糊均值聚類的均勻模糊均值聚類分區(qū)算法。采用該方法對不同類型的無網(wǎng)格幾何模型進(jìn)行了分區(qū)，并根據(jù)分區(qū)信息對三維實(shí)體模型進(jìn)行了并行計(jì)算。通過與基于回歸幾何二分法的比較，充分驗(yàn)證該算法的有效性和可行性。

關(guān)鍵詞：并行計(jì)算； 分區(qū)； 均勻模糊均值聚類； 無網(wǎng)格； 回歸幾何二分法

中圖分類號(hào)：TP338．6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)12-0103-03

無網(wǎng)格方法^[1]是20世紀(jì)90年代中期在國際上興起并得到迅速發(fā)展的一種數(shù)值方法。它僅僅采用節(jié)點(diǎn)來構(gòu)造插值函數(shù)，而不需要節(jié)點(diǎn)之間的連接關(guān)系，并且因?yàn)椴捎昧烁叽尾逯岛瘮?shù)，所以可方便準(zhǔn)確地處理非常嚴(yán)重的變形畸變及應(yīng)力應(yīng)變局部變化，如，連續(xù)體結(jié)構(gòu)的解體、碎裂、固體的層裂、脆性斷裂等；同時(shí)可方便地進(jìn)行自適應(yīng)計(jì)算。雖然無網(wǎng)格方法有以上諸多優(yōu)點(diǎn)，但由于其形函數(shù)采用高次插值，在插值函數(shù)緊支域中的插值點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)大于有限單元中的節(jié)點(diǎn)數(shù)。此外，多數(shù)無網(wǎng)格方法需要采用背景網(wǎng)格進(jìn)行積分，而積分域中的積分點(diǎn)數(shù)目龐大。與傳統(tǒng)的有限元數(shù)值計(jì)算方法相比較，雖然精度得到了明顯的提高，但是計(jì)算量過大、計(jì)算時(shí)間過長，這成為無網(wǎng)格方法推廣到實(shí)際工程計(jì)算的瓶頸。為此，將無網(wǎng)格數(shù)值計(jì)算方法并行化，可以大大縮短其計(jì)算時(shí)間，使無網(wǎng)格方法成功應(yīng)用于實(shí)際工程問題^[2]。

并行計(jì)算是可同時(shí)求解的多進(jìn)程集合，這些進(jìn)程相互作用和協(xié)調(diào)動(dòng)作，并最終獲得問題的求解。簡單地說，就是將一個(gè)問題分解成多個(gè)子問題同時(shí)進(jìn)行求解。對于無網(wǎng)格方法，就是將各個(gè)節(jié)點(diǎn)劃分成若干個(gè)子區(qū)域，將這些子區(qū)域分配給不同的CPU同時(shí)求解。而無網(wǎng)格的分區(qū)方法對并行算法的動(dòng)態(tài)加載起著決定性的作用，因此分區(qū)方法對并行計(jì)算的效率高低有著決定性的影響^[3]。

由于無網(wǎng)格模型是由離散點(diǎn)構(gòu)成，點(diǎn)與點(diǎn)之間不存在幾何拓?fù)潢P(guān)系，國際上普遍采用的方法是RCB法。但對于節(jié)點(diǎn)密度分布不均勻的無網(wǎng)格模型，如果采用幾何分區(qū)法，則會(huì)造成各個(gè)區(qū)域之間的節(jié)點(diǎn)數(shù)目相差巨大，而且對于比較復(fù)雜的模型會(huì)產(chǎn)生龐大的邊界區(qū)域，會(huì)使通信量劇增。為了解決這個(gè)問題，筆者曾經(jīng)將無網(wǎng)格模型中的離散點(diǎn)進(jìn)行簡單連接，構(gòu)成類似于有限元網(wǎng)格的幾何模型，最后采用有限元分區(qū)方法進(jìn)行分區(qū)。但是采用這種方法的分區(qū)結(jié)果對三維問題的無網(wǎng)格計(jì)算進(jìn)行拓?fù)溥B接非常困難，使其可行性下降。

1模糊均值聚類基本理論及其針對分區(qū)問題修正

聚類方法是模式分類與系統(tǒng)建模的基本方法之一。聚類的目的就是根據(jù)某種準(zhǔn)則，將樣本空間的樣本數(shù)據(jù)集合劃分為表示不同模式或系統(tǒng)行為的一些子集。實(shí)際問題一般都帶有一定的模糊性，因此，自從L. A. Zadeh 建立模糊集理論^[4]以來，利用模糊集理論進(jìn)行模式分類取得了很多有意義的成果。1974年，J.C.Dunn 首先將最小方差聚類方法模糊化，提出了fuzzy ISODA TA 聚類方法^[5]。其后J.C. Bezdek將該聚類方法推廣為一般的模糊聚類FCM迭代算法^[6]，并且證明了其收斂性^[6，7]。在眾多的聚類算法中，F(xiàn)CM算法是最重要也是最為人們所熟悉的方法之一。

2基于UFCM分區(qū)方法對無網(wǎng)格模型的分區(qū)

為了驗(yàn)證該方法的有效性和平衡特性，采用UFCM分區(qū)方法和國際上流行的RCB分區(qū)軟件分別對二維和三維問題的無網(wǎng)格模型進(jìn)行了分區(qū)。通過比較兩者的分區(qū)效果，驗(yàn)證本文提出方法的有效性。

2．1算例1：對節(jié)點(diǎn)非均勻分布問題的分區(qū)

無網(wǎng)格計(jì)算中，節(jié)點(diǎn)非均勻布置是非常普遍的。本節(jié)主要針對該問題進(jìn)行了分析。以圖2中無網(wǎng)格模型為例。其中模型的節(jié)點(diǎn)數(shù)目2 887個(gè)，分別采用RCB和UFCM對其進(jìn)行8分區(qū)測試，得到的分區(qū)效果如圖2所示。各個(gè)分區(qū)的節(jié)點(diǎn)數(shù)目如表1所示。對該問題的迭代收斂次數(shù)為36次，累計(jì)耗時(shí)3.5 s。

2．4分區(qū)數(shù)據(jù)及其并行效率的比較

通過分區(qū)結(jié)果圖以及相關(guān)數(shù)據(jù)表1~3，筆者對相關(guān)數(shù)據(jù)進(jìn)行了匯總，并給出了不同方法的分區(qū)內(nèi)節(jié)點(diǎn)數(shù)目的分布圖（圖6）。不難發(fā)現(xiàn)，采用RCB方法會(huì)造成各個(gè)區(qū)域的節(jié)點(diǎn)均衡性差，曲線變化率很大；采用UFCM方法對無網(wǎng)格模型的分區(qū)則具有更好的平衡性，而且計(jì)算效率高。此外，筆者將由UFCM和RCB對算例3的分區(qū)結(jié)果作為分區(qū)信息應(yīng)用于再生核質(zhì)點(diǎn)法(RKPM)無網(wǎng)格并行程序^[2]進(jìn)行了計(jì)算，由UFCM分區(qū)信息的仿真結(jié)果如圖7所示(圖中的相關(guān)網(wǎng)格連線表示背景積分網(wǎng)格^[2])，相關(guān)并行性能數(shù)據(jù)如表4所示。不難看出，從并行加速比和并行效率上，基于UFCM方法的并行計(jì)算的優(yōu)勢明顯。

3結(jié)束語

本文針對國際上普遍采用的基于回歸幾何二分的分區(qū)方法的缺陷，提出了基于模糊均值聚類的均勻模糊均值聚類分區(qū)算法。采用該方法對不同類型的無網(wǎng)格幾何模型進(jìn)行了分區(qū)。通過與基于回歸幾何二分法的比較，筆者發(fā)現(xiàn)，UFCM方法對于復(fù)雜型面和實(shí)體的分區(qū)平衡度同傳統(tǒng)的幾何二分法相比有大幅度的提高。此外，根據(jù)分區(qū)信息對三維實(shí)體模型進(jìn)行并行計(jì)算的計(jì)算效率和加速比均有不同程度的提高，充分驗(yàn)證該算法的有效性和可行性。

參考文獻(xiàn)：

[1]BELYTSCHKO T，KRONGAUZ Y，ORGAN D， et al. Meshless methods: an overview and recent developments[J]. Computer Methods in Applied Mechanics and Engineering， 1996，139:3-47.

[2]王琥，李光耀，鐘志華.三維體積成形過程的并行無網(wǎng)格法仿真分析[J].機(jī)械工程學(xué)報(bào)，2006，42(4):82-87.

[3]王琥，李光耀，鐘志華.有限元并行計(jì)算自動(dòng)分區(qū)方法的優(yōu)化[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17(8):1766-1722.

[4]ZADEH L A.模糊集合、語言變量及模糊邏輯[M].陳國權(quán)，譯.北京：科學(xué)出版社，1990.

[5]DUNN J C. A fuzzy relative of the ISODA TA process and its use in detecting compact， well separate clusters[J]. Journal of Cyber，1974，3:32-57.

[6]BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. New York:Plenum， 1981.

[7]BEZDEK J C， HATHAWAY R， SABIN M，et al. Convergence theory for fuzzy C－means counter example and repairs[J]. IEEE Trans on Syst Man and Cyber， 1987，17(5):873-877.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”