A parallel smoothed aggregation multilevel Schwarz preconditioner and a hybrid-line-and-curve search globalization technique for inexact Newton methods with applications in colloidal particle interactions and semiconductor device simulations

NCU Institutional Repository > 理學院 > 數學研究所 > 博碩士論文 > Item 987654321/85088

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/85088

題名:	A parallel smoothed aggregation multilevel Schwarz preconditioner and a hybrid-line-and-curve search globalization technique for inexact Newton methods with applications in colloidal particle interactions and semiconductor device simulations
作者:	蔡尚融;Cai, Shang-Rong
貢獻者:	數學系
關鍵詞:	Poisson-Boltzmann 方程式;區域分解;Newton-Krylov-Schwarz 演算法;平滑聚合;混合線與曲線搜尋;平行計算;漂移擴散模型;Poisson-Boltzmann equation;domain decomposition;Newton-Krylov-Schwarz algorithm;smoothed aggregation;hybrid-line-and-curve search;parallel computing;drift-diffusion model
日期:	2021-01-26
上傳時間:	2021-03-18 17:37:51 (UTC+8)
出版者:	國立中央大學
摘要:	本文的範圍是針對於開發牛頓類型方法的穩固性與有效性兩個方面問題,關於由偏微分方程離散化而產生的大型、稀疏、非線性方程組的數值求解演算法。本論文的第一部分致力於研究多層 Schwarz 預處理的 Newton-Krylov 算法,以解決 Poisson-Boltzmann 方程,並將其應用於多粒子膠體模擬中。這項研究工作已經發表在由蔡尚融、蕭鈞懌、曾郁潔與黃楓南所著 “Parallel multilevel smoothed aggregation Schwarz preconditioned Newton-Krylov algorithms for Poisson-Boltzmann problems” 發表於學術期刊 Numerical Mathematics: Theory, Methods and Applications 第13卷(2020 年)745 至 769 頁。結合單層 Schwarz 方法並引入平滑的聚合類型的粗網格空間,作為組成每個 Newton 步驟中的解 Jacobian 系統前處理器,以加速 Krylov 子空間方法的收斂性。所提出的求解算法的重要特性是,構造多層預處理器所需的網格幾何資訊與細網格上的單層 Schwarz 方法相同。其他部份,例如粗網格的定義,所有網格轉換運算子和粗網格的問題,由美國 Sandia 國家實驗室的 Trillinos/ML 軟件套件處理。經過算法參數調校後,我們展現所提出的平滑聚合多層 Newton-Krylov-Schwarz (NKS) 演算法在數值上優於平滑聚合多網格方法和單層版本的 NKS 演算法,並在使用數千個運算核心的情況下,具有令人滿意的平行性能。此外,我們研究了粒子之間的靜電力,對於分開離距離的影響是如何;取決於球形膠體粒子的半徑以及立方體中陽離子和陰離子的化合價比。本文的第二部分著重於牛頓類型方法的穩固性問題,該方法用於求解偏微分方程離散化所生成的大型非線性方程組。即使用某些全局策略(例如線搜索或信任區域),這些方法也無法解決由非線性不平衡所致的陷入局部最小值而停滯情況。我們提出了一種新的全域策略,即牛頓類型方法的混合線和曲線搜索技術,以解決其潛在的收斂失敗問題。在提出的方法中,當經典線搜索失敗時,我們轉換使用曲線搜索技術。此這種想法之下,根據 Armijo 條件,解空間分解成兩個正交子空間,分別稱為好的子空間和壞的子空間;壞的子空間將包含導致違反充分減小條件的部份。接下來,將原始預測值投影到良好子空間上,然後執行非線性消去過程,希望新的更新將在全域範圍內達成充分減小條件。我們在數值實驗中展示了該方法的有效性,包括半導體器件模擬和潛勢流問題。;This thesis addresses two issues of robustness and effectiveness for Newton-type methods as the numerical solution algorithm for a large, sparse, nonlinear system of equations arising from some discretization of partial differential equations. The first part of this thesis is devoted to studying a multilevel Schwarz preconditioned Newton-Krylov algorithm to solve the Poisson-Boltzmann equation with applications in multi-particle colloidal simulation. This research work has been published in [S.-R. Cai, J.-Y. Xiao, Y.-C. Tseng, and F.-N. Hwang, Parallel multilevel smoothed aggregation Schwarz preconditioned Newton-Krylov algorithms for Poisson-Boltzmann problems, Numerical Mathematics: Theory, Methods and Applications, Vol. 13, (2020), pp. 745-769.] The smoothed aggregation-type coarse mesh space is introduced in collaboration with the one-level Schwarz method as a composite preconditioner for accelerating a Krylov subspace method for solving the Jacobian system at each Newton step. The important feature of the proposed solution algorithm is that the geometric mesh information needed for constructing the multilevel preconditioner is the same as the one-level Schwarz method on the fine mesh. Other components, such as the definition of the coarse mesh, all the mesh transfer operators, and the coarse mesh problem, are taken care of by the Trillinos/ML packages of the Sandia National Laboratories in the United States. After algorithmic parameter tuning, we show that the proposed smoothed aggregation multilevel Newton-Krylov-Schwarz (NKS) algorithm numerically outperforms the smoothed aggregation multigrid method and one-level version of the NKS algorithm with satisfactory parallel performances up to a few thousand cores. Besides, we investigate how the electrostatic forces between particles for the separation distance depend on the radius of spherical colloidal particles and valence ratios of cation and anion in a cubic system. he second part of this thesis focuses on the robustness issue of Newton-type methods used for solving large nonlinear systems of equations from the discretization of partial differential equations. Even with some global strategies such as line search or trust region, these methods cannot solve situations when an intermediate solution is trapped into local minima due to unbalanced nonlinearity. We propose a new globalization strategy, namely the hybrid line and curve search technique for Newton-type methods, to resolve their potential convergence failure problems. In the proposed method, we activate the curve search technique when the classical line search fails. In this idea, the solution space is decomposed into two orthogonal subspaces, which are referred to as good and bad subspaces, according to the Armijo condition. The bad one corresponds to the components causing the violation of the sufficient decrease condition. Next, we project the original predicted value on the good subspace and then perform the nonlinear elimination process. Hopefully, the new update will satisfy the sufficient decrease condition globally. We show the proposed method′s effectiveness in numerical experiments, including semiconductor device simulation and potential flow problems.
顯示於類別:	[數學研究所] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	185	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....