- 學位論文
Two-Level Deflated Preconditioners for Sparse Symmetric Positive Define Linear Systems with Approximate Eigenvector Approach
Two-Level Deflated Preconditioners for Sparse Symmetric Positive Define Linear Systems with Approximate Eigenvector Approach
摘要
我們有興趣解一個大型的稀疏正定對稱線性系統。在使用傳統的多重網格法需要考慮原始問題的區域分割，即把原始的問題限制(restriction)到一個粗網格系統，經由運算後再內插(Interpolation)到原問題的細網格系統，由於原有的的微分方程式在造網格系統時，必須考慮網格點跟原始方程式的變數等，因此相當不易使用。於是我們採用圖論理論為基礎的區域分割，並使用Krylov迭代法 Conjugate gradient method 與 GMRES，來求解大型稀疏正定對稱線性系統。我們主要專注在Two-Level的preconditioner上，有別於傳統的precondtitioner，我們知道若把某些夠小的特徵向量(eigenvector)組成一個deflation basis再結合傳統的preconditioner，對於迭代法次數會有相當的改進。我們提出一些方法去組成deflation basis，並使用個人電腦和叢集電腦作運算。 我們處理的問題有 Laplacian equation、Anisotropic problem 和Jump coefficient problem，最後再從University of Florida Sparse Matrix Collection 擷取線性系統並求解。我們會先使用個人電腦獲得較佳的參數設定，最後再套用到平行計算上，並比較其結果。
並列摘要
We are interested in solving sparse symmetric positive definite linear systems. In the traditional multigrid method, it needs to consider the domain decomposition; we must consider the original fine grid system that restriction to coarse grid system. After computing, we need to interpolate the coarse grid to the fine grid. However, it is difficult to construct coarse grid. We use some graph theory to do domain decomposition. For solving linear system, we use some Krylove iteration method, those are conjugate gradient method and GMRES. In particular, we focus on two-level preconditioner. We know the deflation basis which are the eigenvectors corresponding to eigenvalues will be very useful. Next, we combine deflation preconditioner and traditional preconditioner. We propose some approach constructing deflation preconditioner and run on sequential and parallel computing. Our test cases include Laplacian equation, anisotropic problem, jump coefficient problem, and also some cases from University of Florida Sparse Matrix Collection. We will test some parameters for two-level method in sequential computing, for optimal parameters setting to parallel computing.