Two-Level Deflated Preconditioners for Sparse Symmetric Positive Define Linear Systems with Approximate Eigenvector Approach

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：29

、訪客IP：3.14.132.214

姓名

張文威(Wen-wei Chang) 查詢紙本館藏

畢業系所

數學系

論文名稱

(Two-Level Deflated Preconditioners for Sparse Symmetric Positive Define Linear Systems with Approximate Eigenvector Approach)

相關論文

★ 非線性塊狀高斯消去牛頓演算法在噴嘴流體的應用	★ 以平行 Newton-Krylov-Schwarz 演算法解 Poisson-Boltzmann 方程式的有限元素解在膠體科學上的應用
★ 最小平方有限元素法求解對流擴散方程以及使用Bubble函數的改良	★ Bifurcation Analysis of Incompressible Sudden Expansion Flows Using Parallel Computing
★ Parallel Jacobi-Davidson Algorithms and Software Developments for Polynomial Eigenvalue Problems in Quantum Dot Simulation	★ An Inexact Newton Method for Drift-DiffusionModel in Semiconductor Device Simulations
★ Numerical Simulation of Three-dimensional Blood Flows in Arteries Using Domain Decomposition Based Scientific Software Packages in Parallel Computers	★ A Parallel Fully Coupled Implicit Domain Decomposition Method for the Stabilized Finite Element Solution of Three-dimensional Unsteady Incompressible Navier-Stokes Equations
★ A Study for Linear Stability Analysis of Incompressible Flows on Parallel Computers	★ Parallel Computation of Acoustic Eigenvalue Problems Using a Polynomial Jacobi-Davidson Method
★ Numerical Study of Algebraic Multigrid Methods for Solving Linear/Nonlinear Elliptic Problems on Sequential and Parallel Computers	★ A Parallel Multilevel Semi-implicit Scheme of Fluid Modeling for Numerical Low-Temperature Plasma Simulation
★ Performance Comparison of Two PETSc-based Eigensolvers for Quadratic PDE Problems	★ A Parallel Two-level Polynomial Jacobi-Davidson Algorithm for Large Sparse Dissipative Acoustic Eigenvalue Problems
★ A Full Space Lagrange-Newton-Krylov Algorithm for Minimum Time Trajectory Optimization	★ Parallel Two-level Patient-specific Numerical Simulation of Three-dimensional Rheological Blood Flows in Branching Arteries

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

我們有興趣解一個大型的稀疏正定對稱線性系統。在使用傳統的多重網格法需要考慮原始問題的區域分割，即把原始的問題限制(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.

關鍵字(中)

★ 平行計算
★ 特徵值問題
★ 正定對稱矩陣
★ 區域分割法

關鍵字(英)

★ deﬂation
★ parallel computing
★ preconditioning
★ Krylov iteration method
★ eigenvalue problem
★ Jacobi-Davidson method
★ SPD matrices
★ two-level preconditioning
★ domain decomposition

論文目次

Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Iteration Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 A review of CG method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Two-Level Iteration method Preconditioner Operator . . . . . . . . . . . . . . . . . . . . 4
2.3 SubDomain Deﬂation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.1 Algebraic Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.2 Graph Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Deﬂation Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1 Preconditioner Condition Number Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Deﬂation Eigenvectors Deﬂation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.1 Interpolation Weighted-Jacobi Deﬂation . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.2 Jacobi-Davidson Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Algorithm and Schematic Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.1 Model Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 Sequential Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2.1 Subdomains Deﬂation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2.2 Eigenvectors Deﬂation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 Parallel Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Appendix A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

參考文獻

[1] Timothy A. Davis and Yifan Hu. The university of ﬂorida sparse matrix collection. ACM Transactions
on Mathematical Software (TOMS), 38, 2011.
[2] Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge University Press, 1985.
[3] Tsung-Ming Huang, Weichung Wang, and Chang-Tse Lee. An efﬁciency study of polynomial eigen-
value problem solvers for quantum dot simulations. Taiwanese Journal of Mathematics, Vol. 14, No.
3A:999–1021, 2010.
[4] George Karypis and Kirk Schloegel. Parallel Graph Partitioning and Sparse Matrix Ordering Library
Version 4.0. University of Minnesota, Department of Computer Science and Engineering Minneapolis,
March 30 2013.
[5] R. NABBEN and C. VUIK. A comparison of deﬂation and coarse grid correction applied to porous
media ﬂow. Society for Industrial and Applied Mathematics, 42 No.4:1631–1647, 2004.
[6] Yousef Saad. Iterative methods for sparse linear systems. Society for Industrial and Applied Mathe-
matics, 2003.
[7] J. M. Tang, R. Nabben, C. Vuik, and Y. A. Erlangga. Theoretical and numerical comparison of various
projection methods derived from deﬂation domain decomposition and multigrid methods. DELFT
UNIVERSITY OF TECHNOLOGY, DIAM Report 07-04,:ISSN 1389–6520, 2007.
[8] J. M. Tang, R. Nabben, C. Vuik, and Y. A. Erlangga. Comparison of two-level preconditioners de-
rived from deﬂation, domain decomposition and multigrid methods. Journal of Scientiﬁc Computing,
39:340–370, 2009.
[9] J.M. Tang and C. Vuik. New variants of deﬂation techniques for pressure correction in bubbly ﬂow
problems. Journal of Numerical Analysis, Industrial and Applied Mathematics, 2:227–249, 2007.
[10] C. Vuik, R. Nabben, and J. Tang. Deﬂation acceleration for domain decomposition preconditioners.
None, 2006.

指導教授

黃楓南(Feng-nan Hwang)

審核日期

2014-8-27

推文