由於平行子結構有限元素分析可在大型結構物分析上於較短時間內獲得一個精確度較高的解，故在近年來漸受到重視。但平行子結構有限元素分析之效率，卻受限於大部份的網格分割演算法未考量矩陣靜態濃縮運算量的平衡和訊息傳遞量的最小化，致使平行效率無法有效的提昇。故本研究先對影響平行子結構有限元素分析運算量的因素，作一研究和探討。並利用此一結果，提出網格分割最佳化架構和方法。為證明此網格分割最佳化方法之可行性與效率，本研究利用數種不同類型網格進行實例測試。另為使最佳網格分割能有自動化的機制，本研究亦研擬網格分割最佳化之目標函數，使整個網格分割最佳化方法能達到完整和實用的地步。

In this thesis, an optimization approach for mesh partitioning is proposed to improve the efficiency of parallel substructure finite element computations. In this approach, an evaluation function and rules are designed based on empirical and experimental studies to obtain optimized mesh partitions automatically. Nine different examples are tested to demonstrate the effectiveness of the approach. The results indicate that the proposed approach can effectively improve the efficiency of parallel substructure finite element computations.

第一章 緒論1
1.1 研究動機與目的 1
1.2 研究內容及方法 3
1.3 論文架構 4
第二章 文獻回顧 5
2.1 平行處理5
2.2 有限元素分析之平行子結構法9
2.2.1 靜態濃縮法(Static Condensation)9
2.2.2 子結構法(Substructure Method )10
2.3 圖分割14
2.3.1 網格分割之核心演算法17
2.3.2 遞迴分割演算法21
2.3.3 網格分割之最佳化演算法24
2.3.4 多階層演算法25
第三章 網格分割之最佳化29
3.1 子結構運算量之探討29
3.2 網格分割最佳化方法與架構之建立與測試32
3.2.1 測試環境35
3.2.2 網格分割最佳化方法之行為測試結果37
3.2.3 網格分割最佳化方法之可行性測試44
3.2.4 網格分割最佳化方法可行性之測試結果45
第四章 最佳網格分割之自動化機制50
4.1 數據分析50
4.1.1 靜態濃縮運算時間之數據分析50
4.1.2 求解邊界自由度時間之數據分析54
4.1.3 網格分割成效評估公式56
4.2 實例測試60
第五章 結論與建議63

Al-Nasra, M. and Nguyen, D. T. (1993). “An Algorithm for Domain Decomposition in Finite Element Analysis,” Computers and Structures, 39(3/4), 277-289
Barnard, S. T. and Simon, H.(1993). “A Parallel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems,” Processing of the 6th SIAM Conference on Parallel for Scientific Computing, SIAM, 711-718
Barnard, S. T., Pothen, A., Simon, H.(1995). “A Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems,” Proceedings of the 6th SIAM Conference on Parallel Processing for Scientific Computing, SIAM, 711-718.
Farhat, C.(1988). “A Simple and Efficient Automatic FEM Domain Decomposer,” Computers and Structures, 28(5), 579-602.
Farhat, C.(1991). “A Method of Finite Element Tearing and Interconnecting and Its Parallel Solution Algorithm,” International Journal for Numerical Methods in Engineering, 32, 1205-1227.
Farhat, C., and Lesoinne, M. (1993). “Automatic Partitioning of Unstructured Meshes for The Parallel Solution of Problems in Computational Mechanics,” International Journal for Numerical Methods in Engineering, 36, 745-764
Fiduccia, C. M., and Mattheyses, R. M. (1982). “A Linear-time Heuristic for Improving Network Partitions,” Proceedings of the 19th Design Automation Conference, 175-181
George, A., and Liu, J. W-H.(1981). Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, New Jersey, USA.
Gilbert, J. R., and Zmijewski, E.(1987), “A Parallel Graph Partitioning Algorithm for a Message-Passing Multiprocessor,” International Journal of Parallel Programming, 16(6), 427-449
Glover, C. McMillan and B. Novick, (1985) “Interaction decision software and computer graphics for architectural and space planning,” Ann. Opns. Res. 5, 557-573
Han, T. Y., and Abel, J. F.(1984). “Substructure Condensation Using Modified Decomposition,” International Journal for Numerical Methods in Engineering, 20(11), 1959-1964.
Hsieh, S. H. (1993). “Parallel Processing For Nonlinear Dynamics Simulations of Structures Including Rotating Bladed-Disk Assemblies,” Ph.D. Dissertation, Cornell University, USA.
Hsieh, S. H., Paulino, G. H., and Abel, J.F.(1995). “Recursive Spectral Algorithms for Automatic Domain Partitioning in Parallel Finite Element Analysis,” Computer Methods in Applied Mechanics and Engineering, 121, 137-162
Hsieh, S. H., and Abel, J. F.(1997). “Evaluation of Automatic Domain Partitioning Algorithm For Parallel Finite Element Analysis,” International Journal For Numerical Methods in Engineering, 40, 1025-1051.
Karypis,G.,and Kumar,V.(1995a). ”A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs,” Technical Report:95-035,Department of Computer Science, University of Minnesota , Mineapolis, MN.
Karypis, G., and Kumar, V.(1995b).”METIS: Unstructured Graph Partitioning and Spare Matrix Ordering-Version 2.0,” Department of Computer Science, University of Minnesota, Minneapolis, MN, USA.
Karypis, G., and Kumar, V.(1998).”METIS: A Software Package for Partitioning Unstructured Graph, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices-Version 2.0,” Department of Computer Science / Army HPC Research Center, University of Minnesota, Minneapolis, MN, USA.
Kernighan, B. W., and Lin, S.(1970). “An Efficient Heuristic for Partitioning Graphs,” The Bell System Technical Journal, 49,291-308.
Kumar, G., Grama, A., Gupta, A., and Karypis, G. (1994). Introduction to Parallel Computing: Design and Analysis of Algorithms, Benjamin/Cummings, New Yark, USA
Nikishkov G. P., Makinouchi A., Yagawa G., Yoshimura S. (1996). “Performance study of the domain decomposition method with direct equation solver for parallel finite element analysis”, Computational Mechanics 19, 84-93
Pothen, A., Simon, H., and Liou, K.-P.(1990). “Partitioning Sparse Matrices with Eigenvectors of Graph,” SIAM Journal on Matrix Analysis and Applications, 11(3), 430-452.
Saab Y.G. and Rao V.B., (1991), “Combinatorial optimization by stochastic evolution, ” IEEE Trans. C.A.D., 10, 525-535
Seitz, C. L.,and Matisoo, J.(1984).”Engineering Limits On Computer Performance,” Physics Today, 37(5), 38-45
Simon, H. D.(1991). “Partitioning of Unstructured Problems for Parallel Processing,” Computing Systems in Engineering, 2(2/3), 135-148
Williams, R.D.(1991).”Performance of Dynamic Load Balancing Algorithm for Unstructured Mesh Calculations,” Concurrency: Practice Experience, 3, 457-481.
William Mcguire and Richard H. Gallagher.(1979). Matrix Structural Analysis, USA
Vanderstraeten D., Farhat C., Chen P.S., Keunings R. andOzone O., (1996), “A retrofit based methodology for the fast generation and optimization of large-scale mesh partitions: beyond the minimum interface size criterion,” Computing. Methods Application Mesh Engineering. 133,25-45
謝尚賢、楊元森與鄭維中(1997),”平行有限元素計算之網格分割研究”,行政院國家科學委員會專題研究計畫成果報告,計畫編號:NSC 86-2211-E-002-029.
盧明德(1996). “平行有限元素計算中網格分割技術之評估與比較,” 碩士論文, 台灣大學, 台北