針對無網格并行計算的基于模糊均值聚類的分區方法

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

關鍵詞：并行計算； 分區； 均勻模糊均值聚類； 無網格； 回歸幾何二分法

中圖分類號：TP338．6文獻標志碼：A

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

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

并行計算是可同時求解的多進程集合，這些進程相互作用和協調動作，并最終獲得問題的求解。簡單地說，就是將一個問題分解成多個子問題同時進行求解。對于無網格方法，就是將各個節點劃分成若干個子區域，將這些子區域分配給不同的CPU同時求解。而無網格的分區方法對并行算法的動態加載起著決定性的作用，因此分區方法對并行計算的效率高低有著決定性的影響^[3]。

由于無網格模型是由離散點構成，點與點之間不存在幾何拓撲關系，國際上普遍采用的方法是RCB法。但對于節點密度分布不均勻的無網格模型，如果采用幾何分區法，則會造成各個區域之間的節點數目相差巨大，而且對于比較復雜的模型會產生龐大的邊界區域，會使通信量劇增。為了解決這個問題，筆者曾經將無網格模型中的離散點進行簡單連接，構成類似于有限元網格的幾何模型，最后采用有限元分區方法進行分區。但是采用這種方法的分區結果對三維問題的無網格計算進行拓撲連接非常困難，使其可行性下降。

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

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

2基于UFCM分區方法對無網格模型的分區

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

2．1算例1：對節點非均勻分布問題的分區

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

2．4分區數據及其并行效率的比較

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

3結束語

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

參考文獻：

[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]王琥，李光耀，鐘志華.三維體積成形過程的并行無網格法仿真分析[J].機械工程學報，2006，42(4):82-87.

[3]王琥，李光耀，鐘志華.有限元并行計算自動分區方法的優化[J].計算機輔助設計與圖形學學報，2005，17(8):1766-1722.

[4]ZADEH L A.模糊集合、語言變量及模糊邏輯[M].陳國權，譯.北京：科學出版社，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.

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