有限元素法是一在工程上廣泛被使用的數值方法，而在求解的過程中，我們最後都將必須去面對求解一線性聯立方程組的過程，去求得問題的近似解，而在此部分所花費的時間與計算量，在整體的時間與計算量上，所佔的比重是非常大的。
對於大型求解線性聯立方程組，我們應用兩種已知的迭代法：Jacobi 預加條件共軛梯度法與SSOR 預加條件共軛梯度法。而在使用SSOR預加條件共軛梯度法時，需要去求解上、下三角矩陣，此部分最難平行化。在本文中，即針對三維有限元素問題，採用一新的垂直切割方式作切割問題空間，而其實際上的作法是將節點的編號方式變更，在實驗室的個人電腦叢集平台上進行測試。
而由結果中顯示，當隨著處理器數目的增加，SSOR 預加條件共軛梯度法，將在總迭代時間上顯現出其優勢，在面對規模較大問題時，採用垂直切割方式的SSOR 預加條件共軛梯度法，將是一種較好的選擇。面對這樣的結果，在日後的個人電腦叢集平台上，所進行的平行有限元素法中，將會有很大的助益。

Finite element method has been widely used in engineering applications. A set of linear equations has to be solved to get the approximate solutions. This calculation spent most of the compution time .
Two well known iterative methods are applied to solve this linear equations. They are the Jacobi conjugate gradient method and the SSOR conjugate gradient method. When we use SSOR conjugate gradient method, we need to solve upper and lower triangular matrices which are very difficult to be paralleized. In this paper, we use a new vertical domain cutting procedure on three-dimensional finite element problem. The numberical experiment are performed on personal computer clusters in our laboratory. In real calculation, the node munbers are reordered as several groups, so that every group of nodes in the matrix are independent of the other groups.
The results show that when the amounts of processors increase, the SSOR method performs better in the total iterative time. When we face the large scale problem, it is better to choose the vertical domain cutting procedure in SSOR conjugate gradient method. The results will give great help in developing the heterogeneous personal computer cluster and parallelize the finite element method in the future.

中文摘要 I
Abstract II
誌謝 III
目錄 IV
表目錄 VII
圖目錄 IX
符號說明 XI

第一章 緒論 1
1.1 前言 1
1.2 文獻回顧 2
1.3 研究動機與目的 3
1.4 論文架構簡介 4

第二章 基本理論 5
2.1 有限元素法 5
2.2 資料儲存之格式 6
2.2.1 壓縮列儲存法 6
2.2.2 區塊壓縮列儲存法 8
2.3 線性聯立方程組之求解 10
2.3.1 預加條件共軛梯度法 10
2.3.2 預選矩陣之形式 12
2.3.2.1 Jacobi預選矩陣 12
2.3.2.2 SSOR預選矩陣 13

第三章 個人電腦叢集與平行處理 14
3.1 個人電腦叢集發展背景 14
3.2 個人電腦叢集計算環境 15
3.2.1 電腦的資料存取與運作 15
3.2.2 平行計算的環境架構 18
3.2.3 實驗室個人電腦叢集架構的建置 19
3.3 MPI平行處理軟體 23
3.3.1 MPI發展背景 23
3.3.2 MPI指令介紹 24
3.3.2.1 基本常用指令介紹 24
3.3.2.2 編輯與執行指令 27
3.4 平行有限元素法 28
3.4.1 預加條件共軛梯度法之平行處理 29
3.4.2 Jacobi預選矩陣共軛梯度法之平行處理 30
3.4.3 SSOR預選矩陣共軛梯度法之平行處理 32
3.4.3.1 解三角矩陣平行處理之想法 33
3.4.3.2 解三角矩陣平行處理之切割 34
3.4.3.3 三角矩陣平行處理之資料交換 42

第四章 實驗結果與討論 46
4.1 三維模型有限元素法之實例敘述 46
4.2 平行有限元素法程式驗證 47
4.2.1 平行有限元素法實驗設備 48
4.3 實驗室個人電腦叢集之平行處理結果 48
4.3.1 Jacobi預選矩陣共軛梯度法 49
4.3.2 SSOR預選矩陣共軛梯度法 55

第五章 結論與建議 71

參考文獻 74

[1]Shi-Pin Ho,“Parallelization of Finite Element Matrix-vector Multiplications on SP2 ”, HPC Asia 95, Taipei, 1995.
[2]L. N. Trefethen, D. Bau, “ Numerical Linear Algebra”, Ⅲ, SIAM, 1997.
[3]R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst, “ Templates for the Solution of Linear Systems：Building Blocks for Iterative Methods”, SIAM, 1994.
[4]C. Farhat, “A Method of Finite Element Tearing and Interconnecting and Its parallel Solution Algorithm, Internationl Journal for Numerical Methods in Enginerring”, Vol. 32, 1205-1227, 1991.
[5]謝尚賢，楊元森，蔡柏良，“平行子結構有限元素計算之效率研究”，行政院國家科學委員會專題研究計劃成果報告，計劃編號：NSC88-2211-E-002-018，1999。
[6]V. Kumar, A. Gramma, A. Gupta, G. Karypis, “Introduction to parallel Computing : Design and Analysis of Algorithms”, Benjamin/Cummings, New York, 1994.
[7]M. T. Jones, P. E. Plaassmann, “ BlockSolve 95 User Manual : Scalable Library Software for the Parallel Solution of Sparse Linear Systems”, Argonne National Laboratory, Technical report, ANL-95/48, USA, 1995.
[8]C. Ashcraft, R. Grimes, “ SPOOLES: An Object-Oriented Sparse Matrix Library”, SIAM Conference on Parallel Processing for Scientific Computing, March 22-27, 1999.
[9]陳俊良，“迭代法解多重負荷問題之探討”，碩士論文，國立成功大學機械工程學系，1994。
[10] 余政篷，“預加條件共軛梯度法與三度空間有限元素問題之研究”，碩士論文，國立成功大學機械工程學系，1995。
[11] 徐文政，“大型三角稀疏矩陣平行解法”，碩士論文，國立成功大學機械工程學系，1996。
[12] 吳宗穎，“平行處理應用於有限元素計算之使用評估”，碩士論文，國立成功大學機械工程學系，1999。
[13] 黃建彰，“個人電腦叢集之平行有限元素計算”，碩士論文，國立成功大學機械工程學系，2000。
[14] 陳明凱，“平行有限元素法之負載平衡探討”，碩士論文，國立成功大學機械工程學系，2001。
[15] E. B. Becker, G. F. Carey, J. T. Oden, “Finite Elements”, An Introduction Volumn (Ⅰ), Prentice-Hall International Inc., 1981.
[16] D. C. Robert, “Finite Element Modeling For Stress Analysis”, John Wiley & Sons,Inc., 1995.
[17] K. Dowd, “High Performance Computing”, O’Reilly & Associates,Inc., 1993.
[18] 施威銘研究室，“Red Hat Linux 7.1實務應用”，初版，旗標出版股份有限公司，1999。
[19] M. Welsh, M. K. Dalheimer, L. Kaufman原著，詹韋佐，林長毅編譯，“Linux技術手冊”，初版，美商歐萊禮股份有限公司台灣分公司，1999。
[20] B. Wilkinson, M. Allen, “Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers”, Prentice Hall, Inc, 1999.