Numerical Study of Algebraic Multigrid Methods
for Solving Linear/Nonlinear Elliptic Problems on
Sequential and Parallel Computers

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：32

、訪客IP：3.15.6.77

姓名

曾郁潔(Yu-Chieh Tseng) 查詢紙本館藏

畢業系所

數學系

論文名稱

Numerical Study of Algebraic Multigrid Methods for Solving Linear/Nonlinear Elliptic Problems on Sequential and Parallel Computers
(Numerical Study of Algebraic Multigrid Methodsfor Solving Linear/Nonlinear Elliptic Problems onSequential and Parallel Computers )

相關論文

★ 非線性塊狀高斯消去牛頓演算法在噴嘴流體的應用	★ 以平行 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
★ 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	★ A Markov Chain Multi-elimination Preconditioner for Elliptic PDE Problems on GPU

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

在現今做數值計算的趨勢中，多重網格法(Multigrid method)已是一個重要，不可或缺的數值方法，因為它的好處除了可降低迭代次數和計算時間之外，可平行化也是一個很大的優勢，這對專門研究平行計算的研究者們是一大福音。有關於多重網格法的發展已有一段時間，其效率及演算法的形式也是百家爭鳴。本文藉由對多重網格法的由來和其中發展出的演算法來解Poisson-Boltzmann Equations, Convection-Diffusion Equations等問題上的應用來探討多重網格法對於解其問題的效果及成本等等的結果，並觀察多重網格法的優缺點。透過了解多重網格法的特性，以期能用此特性來節省迭代次數和時間成本。用來解更多的大型線系統或大型的稀疏矩陣。

摘要(英)

In the nowadays, Multigrid method plays an important role in the trend of numerical computations.
Besides of its advantages of decreasing the iterations and the computation time, parallelization is also a big advantage of the parallel computation, it brings the convience for those researchers who do the research about parallel computation. About the developement of the multigrid already exists for a period of time. Its efficiency and the form of algorithms also have many different versions. In this paper, we will discuss about the result of solving the Poisson-Boltzmann Equations, Convection-Diffusion Equations by using the numerical multigrid method, including the time cost and the effect of solving linear system after using multigird method. And recovering the disadvantages and advantages of multigrid method. Through understanding the concepts of multigrid method, we hope we can using this method to decrease the iterations and cost of time. And extending this method that can be used to solve more linear system problems or linear sparse matrix problems.

關鍵字(中)

★ 多重網格法
★ 橢圓問題
★ 平行計算

關鍵字(英)

★ Elliptic problems
★ Multigrid methods
★ Parallel computing

論文目次

Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Review of Multigrid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 Solution Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1 Algebraic Multigrid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 AMG algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Aggregation-based Algebraic Multigrid (AGMG) Method . . . . . . . . . 9
3.3.1 The solution Algorithm . . . . . . . . . . . . . . . . . . . . . . . 13
3.3.2 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.4 Multilevel Method: A Parallel Smoothed Aggregation Multigrid Method . 17
3.4.1 Uncoupled Parallel Aggregation Scheme . . . . . . . . . . . . . 19
3.4.2 Maximally Independent Sets(MIS) Parallel Aggregation Scheme . 19
3.5 Newton-Krylov-Schwarz algorithm . . . . . . . . . . . . . . . . . . . . . 20
3.5.1 Inexact Newton Method with Backtracking (INB) . . . . . . . . . 20
3.5.2 Krylov Iterative Methods . . . . . . . . . . . . . . . . . . . . . . 20
3.5.3 Overlapping Schwarz Preconditioner . . . . . . . . . . . . . . . 21
4 Testing Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1 Laplace Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.1 Model Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.1.2 Basic Solution Domain . . . . . . . . . . . . . . . . . . . . . . . 24
4.1.3 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1.4 Solution Graph of Laplace Equation . . . . . . . . . . . . . . . . 25
4.2 Anisotropic Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.1 Model Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.2 Basic Solution Domain . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.3 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.4 Solution Graph of ANI Equation . . . . . . . . . . . . . . . . . . 28
4.3 Jump Coefficient Problem . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3.1 Model Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3.2 Basic Solution Domain . . . . . . . . . . . . . . . . . . . . . . . 29
4.3.3 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3.4 Solution Graph of Jump Coefficient Problem . . . . . . . . . . . 32
4.4 Convection-Diffusion Problems . . . . . . . . . . . . . . . . . . . . . . 33
4.4.1 Model Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4.2 Basic Solution Domains . . . . . . . . . . . . . . . . . . . . . . 34
4.4.3 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4.4 Solution Graph of Convection-Diffusion Equations . . . . . . . . 38
4.5 Poisson-Boltzmann Equation . . . . . . . . . . . . . . . . . . . . . . . . 44
4.5.1 The derivation of Poisson-Boltzmann Equations . . . . . . . . . . 44
4.5.2 Finite Element Method for Discretizing Poisson-Boltzmann Equations
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5.3 Basic Solution Domains . . . . . . . . . . . . . . . . . . . . . . 50
4.5.4 The solution graph . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5.5 Particles Interaction Force . . . . . . . . . . . . . . . . . . . . . 51
4.5.6 The computation of the non-dimensionalized electrostatic force
acting on the charged particles . . . . . . . . . . . . . . . . . . . 54
4.6 Poisson Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.6.1 Model Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.6.2 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.6.3 Basic Solution Domain . . . . . . . . . . . . . . . . . . . . . . . 57
4.6.4 Solution Graphs of Poisson Equation . . . . . . . . . . . . . . . 57
5 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1 Sequential version: AGMG . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.1 Discussions and Results of Experiments . . . . . . . . . . . . . . 59
5.2 Parallel version: ML on PETSc . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.1 Discussions and Results of Experiments . . . . . . . . . . . . . . 63
6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Appendix about Indefinite Problems . . . . . . . . . . . . . . . . . . . . . . . . . 83
0.1 Helmholtz Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
0.1.1 Model Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 83
0.1.2 Basic Solution Domains . . . . . . . . . . . . . . . . . . . . . . 84
0.1.3 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
0.1.4 Solution Graphs of Helmholtz Equations . . . . . . . . . . . . . 86
0.2 Numerical Results of Helmholtz Problems . . . . . . . . . . . . . . . . . 91

參考文獻

[1] Yun-Long Shao Jong-ShinnWu Feng-Nan Hwang, Shang-Rong Cai. Parallel newtonkrylov-
schwarz algorithms for the three-dimensional poisson-boltzmann equation in
numerical simulation of colloidal particle interactions. 2010.
[2] Leopoldo P. Franca and Feng-Nan Hwang. Refining the submesh strategy in the
two-level finite element method: application to the advectionvdiffusion equation. INTERNATIONAL
JOURNAL FOR NUMERICAL METHODS IN FLUIDS, 2002.
[3] Michael W. Gee, Jonathan J. Hu Christopher M. Siefert, and Marzio G. Sala Ray
S. Tuminaro. Ml 5.0 smoothed aggregation user’s guide. 2007.
[4] Isaac Harari and Kirill Gosteev. Bubble-based stabilization for the helmholtz equation.
INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING,
2006.
[5] Ellen T. Paik-Stefan A. Sauter Ivo BabuSka, Frank Ihlenburg. A generalized finite
element method for solving the helmholtz equation in two dimensions with minimal
pollution. Computer methods in applied mechanics and engineering, 1994.
[6] YVAN NOTAY. An aggregation-based algebraic multigrid method. Electronic Transactions
on Numerical Analysis, 2010.
[7] Ray S. Tuminaro and Charles Tong. Parallel smoothed aggregation multigrid : Aggregation
strategies on massively parallel machines. 2000.
[8] Steve F. McCormick William L Briggs, Van Emden Henson. A Multigrid Tutorial.
siam, 2000.

指導教授

黃楓南(Feng-Nan Hwang)

審核日期

2012-7-19

推文