| 摘要: | 本論文的第一個重點，是開發高效率且穩健對雙曲型偏微分方程求解的平行化演算法，這類問題在計算科學和工程都有廣泛的應用，其解的不連續性和高度局部非線性特性，使得一般針對橢圓偏微分方程設計的迭代法，效能上表現不盡理想，也常有不收斂的問題。傳統上，以使用時間步進方法為基礎的的平行解法，主要是在於每個時間步驟內的平行化，同時在時間步驟之間保持循序進行。然而，這樣的循序步驟可能成為平行化演算法效能的瓶頸。另一方面，隨著現代超級電腦系統運算能力的提升，全耦合時空平行解法越來越受到學界的重視，對於時空演算法，穩健且高效能的大型稀疏非線性方程求解器為演算法成功扮演重要的角色。
不精確牛頓回朔法（Inexact Newton with Backtracking, INB）是大型非線性系統求解常用方法，但在處理我們感興趣的震盪現象發生時，數值解有不連續的情況發生，造成INB收斂速度較慢。為有效解決此問題，我們提出了一種新的非線性消去(Nonlinear Elimination) 預條件法，以提高針對雙曲型偏微分方程解特性的INB的穩健性和效率。透過將非線性消去法作為左或右預條件法，結合INB，包括：自適應非線性消去的INB-ANE（INB-Adaptive Nonlinear Elimination）和非線性消除預條件的不精確牛頓法（ Nonlinear Elimination Preconditioned Inexact Newton, NEPIN）。這些方法旨在減少高度局部非線性的影響，並為下一次牛頓迭代提供更好的初始猜測。數值實驗結果顯示，這一改進增強了INB在Burgers′和Buckley-Leverett方程中的穩健性，而NEPIN優於INB-ANE，在於前者能正確的偵測震波位置並減少子空間修正後的界面污染對方法收斂性的影響。此外，對於NEPIN而言，收斂所需的牛頓迭代次數幾乎與時間步長和網格大小無關。
儘管數值結果顯示，非線性預條件法是改進牛頓法穩健性和效率有效的技術，但對這類方法的理論分析或啟發性理解的完備，仍有待努力。因此，本論文的第二個重點是提出一種新的衡量方法，稱為剛性比，這一想法是源自剛性常微分方程（ODE），用以量化系統中的非線性不平衡的程度。這一度量類似於線性系統中用於評估矩陣質量的條件數。這指標可以用於衡量對非線性方程使用牛頓法求解的難易程度，或作為開發針對特定應用的預條件器，提供了有價值的設計指引或分析方法的工具。我們推導出牛頓法對應的常微分方程系統並計算其剛性比，我們透過數值實例驗證了，NEPIN中的非線性消除去預條件法有效的降低相應牛頓ODE系統剛性比，對方法的成功有較為清楚的理解。;As the first focus of this work, we aim to develop an efficient and robust solution algorithm for solving hyperbolic partial differential equations exhibiting solution discontinuity and highly local nonlinearity behavior. Such problems arise in numerous applications in computational science and engineering. Traditionally, parallel solution algorithms using time-marching methods focused on parallelizing computations within each time step while maintaining a sequential approach between time steps. Such a sequential step is the potential bottleneck of parallel algorithm performance. On the other hand, with the increasing computational power of modern parallel computer systems, there has been a growing interest in fully coupled space-time solution algorithms for time-dependent partial differential equations (PDEs), enabling parallelism in the temporal domain. To make the solution algorithm practical, it is crucial to have a robust and efficient nonlinear solver for large, sparse systems of equations in space-time algorithms. The inexact Newton with backtracking (INB) method is a well-known approach for solving nonlinear equations, but it exhibits slow convergence in the presence of shocks of our interests. In this work, we propose a new variant of nonlinear elimination preconditioning techniques to enhance the robustness and improve the efficiency of INB based on the solution characteristics of hyperbolic PDEs. By employing nonlinear elimination as a right or left preconditioner in conjunction with INB, we introduce two methods: INB with adaptive nonlinear elimination (INB-ANE) and nonlinear elimination preconditioned inexact Newton (NEPIN). These methods aim to reduce the impact of highly local nonlinearity and provide a better initial guess for the next Newton iteration. Numerical results show that the modification enhances the robustness of INB for Burgers′ and Buckley-Leverett equations and reveal that NEPIN outperforms INB-ANE in identifying the correct shock location and introducing less interface pollution after the subspace correction before the global update.
Additionally, the number of Newton iterations required to converge for NEPIN is almost independent of the time step and mesh size.
Although nonlinear preconditioning has been shown numerically to be a valuable technique to enhance the robustness and efficiency of Newton-type methods, a comprehensive theoretical or heuristic understanding of this technique still needs to be completed. Therefore, the second focus of this thesis is to introduce a new metric known as the stiffness ratio, which is borrowed from stiff ordinary differential equations (ODEs) to quantify the unbalanced nature of nonlinear systems. This metric is analogous to the condition number of the coefficient matrix for linear systems, which is used to assess matrix quality. Such insights offer valuable guidance and analytical tools for developing preconditioners tailored to specific applications. An investigation of a highly nonlinear algebraic system reveals that NEPIN reduces stiffness compared to INB. To illustrate this concept, we present numerical examples demonstrating the reduction of stiffness ratios of the corresponding Newton ODE system through nonlinear elimination. |
