以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：127

、訪客IP：18.217.116.183

姓名	蔡尚融(Shang-Rong Cai)  查詢紙本館藏	畢業系所	數學系
論文名稱	(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)
相關論文	★ 非線性塊狀高斯消去牛頓演算法在噴嘴流體的應用 ★ 以平行 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 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載] 本電子論文使用權限為同意立即開放。 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中)	本文的範圍是針對於開發牛頓類型方法的穩固性與有效性兩個方面問題,關於由偏微分方程離散化而產生的大型、稀疏、非線性方程組的數值求解演算法。 本論文的第一部分致力於研究多層 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.
關鍵字(中)	★ 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
論文目次	Chinese Abstract i English Abstract ii Contents iv List of Figures viii List of Tables x Explanation of Symbols xi 1 Introduction 1 2 Review of methods for solving nonlinear systems 4 2.1 Inexact Newton backtracking methods . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Gradient descent methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Gauss-Newton method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 A comparison of three methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Parallel smoothed aggregation multilevel Schwarz preconditioned Newton-Krylov algorithms Poisson-Boltzmann problems 14 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Poisson-Boltzmann equation and its finite element formulation . . . . . . . . . . 16 3.3 Parallel multilevel solution algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3.1 A general Newton-Krylov-Schwarz framework . . . . . . . . . . . . . . . . 19 3.3.2 Geometric two-level Schwarz preconditioner . . . . . . . . . . . . . . . . . 19 3.3.3 A parallel smoothed aggregation multilevel Schwarz preconditioner . . . . 21 3.4 Numerical results and discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4.1 Three test problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4.2 Code verification test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4.3 Algorithmic parametric study . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4.4 Parallel performance evaluation . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.5 Physical parametric study . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4 A hybrid-line-and-curve search globalization technique for inexact Newton methods 38 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2 An illustrating example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3 Hybrid line and nonlinear elimination-based curve search for inexact Newton algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4 Application to drift-diffusion model for semiconductor device simulation and its discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4.1 The drift-diffusion model . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4.2 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.5 Numerical results and discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.5.1 Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.5.2 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.5.3 Example 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.5.4 Example 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5 Conclusions and future work 73 Bibliography 75
參考文獻	[1] Y. Saad. Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia, 2003. [2] Y. Saad and M.H. Schultz. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., 7:856–869, 1986. [3] Y. Saad. A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Comput., 14:461–469, 1993. [4] M. Dryja and W. Hackbusch. On the nonlinear domain decomposition method. BIT Numer. Math., 37:296–311, 1997. [5] A. Brandt. Multi-level adaptive solutions to boundary-value problems. Math. Comput., 31:333–390, 1977. [6] C.T. Kelley. Solving Nonlinear Equations with Newton’s Method. SIAM, Philadelphia, 2003. [7] D.A Knoll and D.E Keyes. Jacobian-free Newton–Krylov methods: a survey of approaches and applications. J. Comput. Phys., 193:357–397, 2004. [8] B. Smith, P. Bjørstad, and W. Gropp. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, Cambridge, 1996. [9] J.E. Dennis and R.B. Schnabel. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, Philadelphia, 1996. [10] P. Wolfe. Convergence conditions for ascent methods. SIAM Rev., 11:226–235, 1969. [11] P. Wolfe. Convergence conditions for ascent methods. ii: Some corrections. SIAM Rev., 13:185–188, 1971. [12] J. Nocedal and S. Wright. Numerical Optimization. Springer-Verlag, New York, 2006. [13] Z. Chen and R.K. Singh. General solution for Poisson–Boltzmann equation in semiinfinite planar symmetry. J. Colloid Interface Sci., 245:301–306, 2002. [14] P.E. Dyshlovenko. Two-dimensional colloidal crystal in nonlinear Poisson–Boltzmann model. Colloid Journal, 69:13–19, 2007. [15] A.O. Sharif, Z. Tabatabaian, and W.R. Bowen. The wall and multivalent counterion effects on the electrostatic force between like-charged spherical particles confined in a charged pore. J. Colloid Interface Sci., 255:138–144, 2002. [16] A.O. Sharif, M.H. Afshar, J. Moghadasi, and T.J. Williams. The effect of many-body interactions on the electrostatic force on a finite chain of spheres confined in a long charged tube. Powder Tech., 135:76–81, 2003. [17] S.-R. Cai, J.-Y. Xiao, Y.-C. Tseng, and F.-N. Hwang. Parallel smoothed aggregation multi-level Schwarz preconditioned Newton–Krylov algorithms for Poisson–Boltzmann problems. Numerical Mathematics: Theory, Methods & Applications, 13:745–769, 2020. [18] J.Z. Wu, D. Bratko, H.W. Blanch, and J.M. Prausnitz. Monte Carlo simulation for the potential of mean force between ionic colloids in solutions of asymmetric salts. J. Chem. phys., 111:7084–7094, 1999. [19] Y.-Y. Wu, F.-H. Wang, and Z.-J. Tan. Calculating potential of mean force between like-charged nanoparticles: a comprehensive study on salt effects. Phys. Lett. A, 377:1911–1919, 2013. [20] X. Zhang, J.-S. Zhang, Y.-Z. Shi, X.-L. Zhu, and Z.-J. Tan. Potential of mean force between like-charged nanoparticles: Many-body effect. Sci. Rep., 6:23434, 2016. [21] B.Z. Lu, Y.C. Zhou, M.J. Holst, and J.A. McCammon. Recent progress in numerical methods for the Poisson-Boltzmann equation in biophysical applications. Commun Comput Phys, 3:973–1009, 2008. [22] C. Li, L. Li, M. Petukh, and E. Alexov. Progress in developing Poisson-Boltzmann equation solvers. CMB, 1:42–62, 2013. [23] J.H. Masliyah and S. Bhattacharjee. Electrokinetic and Colloid Transport Phenomena. John Wiley & Sons, Hoboken, 2006. [24] F.-N. Hwang, S.-R. Cai, Y.-L. Shao, and J.-S. Wu. Parallel Newton-Krylov-Schwarz algorithms for the three-dimensional Poisson-Boltzmann equation in numerical simulation of colloidal particle interactions. Comput. Phys. Commun., 181:1529–1537, 2010. [25] X.-C. Cai, W.D. Gropp, D.E Keyes, R.G. Melvin, and D.P Young. Parallel Newton–Krylov–Schwarz algorithms for the transonic full potential equation. SIAM J. Sci. Comput., 19:246–265, 1998. [26] M. Brezina, R. Falgout, S. MacLachlan, T. Manteuffel, S. McCormick, and J. Ruge. Adap-tive smoothed aggregation (α SA) multigrid. SIAM Rev., 47:317–346, 2005. [27] R.S. Tuminaro and C. Tong. Parallel smoothed aggregation multigrid: Aggregation strategies on massively parallel machines. In Supercomputing, ACM/IEEE 2000 Conference, pages 5–5. IEEE, 2000. [28] M.J. Holst and F. Saied. Multigrid solution of the Poisson–Boltzmann equation. J. Comput. Chem., 14:105–113, 1993. [29] J.C. Womack, L. Anton, J. Dziedzic, P.J. Hasnip, M.I.J. Probert, and C.-K. Skylaris. DL_MG: A parallel multigrid Poisson and Poisson-Boltzmann solver for electronic structure calculations in vacuum and solution. J. Chem. Theory Comput., 14:1412–1432, 2018. [30] H.M. Tufo and P.F. Fischer. Fast parallel direct solvers for coarse grid problems. J. Parallel Distrib. Comput., 61:151–177, 2001. [31] F.-N. Hwang and X.-C. Cai. Parallel fully coupled Schwarz preconditioners for saddle point problems. Electron. Trans. Numer. Anal., 22:146–162, 2006. [32] S. Balay, K. Buschelman, W.D. Gropp, D. Kaushik, M.G. Knepley, L.C. McInnes, B.F. Smith, and H. Zhang. PETSc web page, 2018. [33] M.W. Gee, C.M. Siefert, J. J. Hu, R.S. Tuminaro, and M.G. Sala. ML 5.0 smoothed aggregation user’s guide. Technical report, Technical Report SAND2006-2649, Sandia National Laboratories, 2006. [34] G.F. Hassan, A.O. Sharif, U. Tuzun, and A. Tate. The effect of many-body interactions on the electrostatic force in an array of spherical particles. J. Colloid Interface Sci., 346:232–235, 2010. [35] R.S. Dembo, S.C. Eisenstat, and T. Steihaug. Inexact Newton methods. SIAM J. Numer. Anal., 19:400–408, 1982. [36] A. Beck. Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB. SIAM, Philadelphia, 2014. [37] F.-N. Hwang, H.-L. Lin, and X.-C. Cai. Two-level nonlinear elimination based preconditioners for inexact Newton methods with application in shocked duct flow calculation. Electron. Trans. Numer. Anal., 37:239–251, 2010. [38] F.-N. Hwang, Y.-C. Su, and X.-C. Cai. A parallel adaptive nonlinear elimination preconditioned inexact Newton method for transonic full potential equation. Comput. Fluids, 110:96–107, 2015. [39] F.-N. Hwang and X.-C. Cai. A parallel nonlinear additive Schwarz preconditioned inexact Newton algorithm for incompressible Navier–Stokes equations. J. Comput. Phys., 204:666–691, 2005. [40] J.N. Shadid, R.S. Tuminaro, and H.F. Walker. An inexact Newton method for fully coupled solution of the Navier–Stokes equations with heat and mass transport. J. Comput. Phys., 137:155–185, 1997. [41] H.K. Gummel. A self-consistent iterative scheme for one-dimensional steady state transistor calculations. IEEE Trans. Electron. Devices, 11:455–465, 1964. [42] CP Please. An analysis of semiconductor PN junctions. IMA J. Appl. Math., 28:301–318, 1982. [43] P.J. Lanzkron, D.J. Rose, and J.T. Wilkes. An analysis of approximate nonlinear elimination. SIAM J. Sci. Comput., 17:538, 1996. [44] X.-C. Cai and X. Li. Inexact Newton methods with restricted additive Schwarz based nonlinear elimination for problems with high local nonlinearity. SIAM J. Sci. Comput., 33:746–762, 2011. [45] H. Yang and F.-N. Hwang. An adaptive nonlinear elimination preconditioned inexact Newton algorithm for highly local nonlinear multicomponent PDE systems. Appl. Numer. Math., 133:100–115, 2018. [46] L. Luo, X.-C. Cai, Z. Yan, L. Xu, and D.E Keyes. A multilayer nonlinear elimination preconditioned inexact Newton method for steady-state incompressible flow problems in three dimensions. SIAM J. Sci. Comput., 42:B1404–B1428, 2020. [47] P. Farrell, N. Rotundo, D.H. Doan, M. Kantner, J. Fuhrmann, and T. Koprucki. Numerical methods for drift-diffusion models. Preprint, 2016. [48] R.S. Tuminaro, H.F. Walker, and J.N. Shadid. On backtracking failure in Newton–GMRES methods with a demonstration for the Navier–Stokes equations. J. Comput. Phys., 180:549–558, 2002. [49] F.-N. Hwang and X.-C. Cai. Improving robustness and parallel scalability of Newton method through nonlinear preconditioning. In Domain decomposition methods in science and engineering, pages 201–208. Springer, 2005. [50] C.R. Harris, K.J. Millman, S.J van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, J. Taylor, S. Berg, N.J. Smith, R. Kern, M. Picus, S. Hoyer, M.H. van Kerkwijk, M. Brett, A. Haldane, J. Fernández del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant, K. Sheppard, T. Reddy, W. Weckesser, H. Abbasi, C. Gohlke, and T.E. Oliphant. Array programming with NumPy. Nature, 585:357–362, 2020. [51] P. Virtanen, R. Gommers, T.E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S.J. van der Walt, M. Brett, J. Wilson, K.J. Millman, N. Mayorov, A.R.J. Nelson, E. Jones, R. Kern, E. Larson, C.J Carey, İ. Polat, Y. Feng, E.W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E.A. Quintero, C.R. Harris, A.M. Archibald, A.H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272, 2020. [52] R.A. Jabr, M. Hamad, and Y.M. Mohanna. Newton-Raphson solution of Poisson’s equation in a PN diode. Int. J. Electr. Eng. Educ., 44:23–33, 2007. [53] S.M. Sze. Semiconductor Devices: Physics and Technology. John wiley & sons, 2008. [54] Y. Li. A parallel monotone iterative method for the numerical solution of multi-dimensional semiconductor Poisson equation. Comput. Phys. Commun., 153:359–372, 2003. [55] R.C. Chen and J.L. Liu. A quantum corrected energy-transport model for nanoscale semiconductor devices. J. Comput. Phys., 204:131–156, 2005. [56] X.-C. Cai, D.E Keyes, and D.P Young. A nonlinear additive Schwarz preconditioned inexact Newton method for shocked duct flows. In Thirteenth International Conference on Domain Decomposition Methods, pages 343–350, 2002. [57] D.P Young, R.G. Melvin, M.B. Bieterman, F.T Johnson, S.S. Samant, and J.E. Bussoletti. A locally refined rectangular grid finite element method: application to computational fluid dynamics and computational physics. J. Comput. Phys., 92:1–66, 1991.
指導教授	黃楓南(Feng-Nan Hwang)	審核日期	2021-1-26
推文	facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu
網路書籤	Google bookmarks   del.icio.us   hemidemi   myshare