Improved numerical solvers for implicit coupling of subsurface and overland flow

Due to complex dynamics inherent in the physical models, numerical formulation of subsurface and overland flow coupling can be challenging to solve. ParFlow is a subsurface flow code that utilizes a structured grid discretization in order to benefit from fast and efficient structured solvers. Implicit coupling between subsurface and overland flow modes in ParFlow is obtained by prescribing an overland boundary condition at the top surface of the computational domain. This form of implicit coupling leads to the activation and deactivation of the overland boundary condition during simulations where ponding or drying events occur. This results in a discontinuity in the discrete system that can be challenging to resolve. Furthermore, the coupling relies on unstructured connectivities between the subsurface and surface components of the discrete system, which makes it challenging to use structured solvers to effectively capture the dynamics of the coupled flow. We present a formulation of the discretized algebraic system that enables the use of an analytic form of the Jacobian for the Newton–Krylov solver, while preserving the structured properties of the discretization. An effective multigrid preconditioner is extracted from the analytic Jacobian and used to precondition the Jacobian linear system solver. We compare the performance of the new solver against one that uses a finite difference approximation to the Jacobian within the Newton–Krylov approach, previously used in the literature. Numerical results explores the effectiveness of using the analytic Jacobian for the Newton–Krylov solver, and highlights the performance of the new preconditioner and its cost. The results indicate that the new solver is robust and generally outperforms the solver that is based on the finite difference approximation to the Jacobian, for problems where the overland boundary condition is activated and deactivated during the simulation. A parallel weak scaling study highlights the efficiency of the new solver.     

A parallel,fully coupled,fully implicit solution to reactive transport in porous media using the preconditioned Jacobian-Free Newton-Krylov Method

Modeling large multicomponent reactive transport systems in porous media is particularly challenging when the governing partial differential algebraic equations (PDAEs) are highly nonlinear and tightly coupled due to complex nonlinear reactions and strong solution-media interactions. Here we present a preconditioned Jacobian-Free Newton-Krylov (JFNK) solution approach to solve the governing PDAEs in a fully coupled and fully implicit manner. A well-known advantage of the JFNK method is that it does not require explicitly computing and storing the Jacobian matrix during Newton nonlinear iterations. Our approach further enhances the JFNK method by utilizing physics-based, block preconditioning and a multigrid algorithm for efficient inversion of the preconditioner. This preconditioning strategy accounts for self- and optionally, cross-coupling between primary variables using diagonal and off-diagonal blocks of an approximate Jacobian, respectively. Numerical results are presented demonstrating the efficiency and massive scalability of the solution strategy for reactive transport problems involving strong solution-mineral interactions and fast kinetics. We found that the physics-based, block preconditioner significantly decreases the number of linear iterations, directly reducing computational cost; and the strongly scalable algebraic multigrid algorithm for approximate inversion of the preconditioner leads to excellent parallel scaling performance.     

Preconditioned non‐linear conjugate gradient method for frequency domain full‐waveform seismic inversion

We present preconditioned non‐linear conjugate gradient algorithms as alternatives to the Gauss‐Newton method for frequency domain full‐waveform seismic inversion. We designed two preconditioning operators. For the first preconditioner, we introduce the inverse of an approximate sparse Hessian matrix. The approximate Hessian matrix, which is highly sparse, is constructed by judiciously truncating the Gauss‐Newton Hessian matrix based on examining the auto‐correlation and cross‐correlation of the Jacobian matrix. As the second preconditioner, we employ the approximation of the inverse of the Gauss‐Newton Hessian matrix. This preconditioner is constructed by terminating the iteration process of the conjugate gradient least‐squares method, which is used for inverting the Hessian matrix before it converges. In our preconditioned non‐linear conjugate gradient algorithms, the step‐length along the search direction, which is a crucial factor for the convergence, is carefully chosen to maximize the reduction of the cost function after each iteration. The numerical simulation results show that by including a very limited number of non‐zero elements in the approximate Hessian, the first preconditioned non‐linear conjugate gradient algorithm is able to yield comparable inversion results to the Gauss‐Newton method while maintaining the efficiency of the un‐preconditioned non‐linear conjugate gradient method. The only extra cost is the computation of the inverse of the approximate sparse Hessian matrix, which is less expensive than the computation of a forward simulation of one source at one frequency of operation. The second preconditioned non‐linear conjugate gradient algorithm also significantly saves the computational expense in comparison with the Gauss‐Newton method while maintaining the Gauss‐Newton reconstruction quality. However, this second preconditioned non‐linear conjugate gradient algorithm is more expensive than the first one.     

Application of Jacobian-free Newton–Krylov with physics-based preconditioning to biogeochemical transport

Modern multicomponent geochemical transport models require the use of parallel computation for carrying out three-dimensional, field-scale simulations due to extreme memory and processing demands. However, to fully exploit the advanced computational power provided by today’s supercomputers, innovative parallel algorithms are needed. We demonstrate the use of Jacobian-free Newton–Krylov (JFNK) within the Newton–Raphson method to reduce memory and processing requirements on high-performance computers. We also demonstrate the use of physics-based preconditioners, which are often necessary when using JFNK since no explicit Jacobian matrix is ever formed. We apply JFNK to simulate enhanced in situ bioremediation of a NAPL source zone, which entails highly coupled geochemical and biodegradation reactions. The algorithm’s performance is evaluated and compared with conventional solvers and preconditioners. We found that JFNK provided substantial saving in memory (i.e. 30–60%) on problems utilizing up to 512 processors on LANL’s ASCI Q. However, the performance based on wallclock time was less advantageous, coming out on par with conventional techniques. In addition, we illustrate deficiencies in physics-based preconditioner performance for biogeochemical transport problems with components that undergo significant sorption or form a local quasi-stationary state.     

A least-squares penalty method algorithm for inverse problems of steady-state aquifer models

Based on the generalized Gauss–Newton method, a new algorithm to minimize the objective function of the penalty method in (Bentley LR. Adv Wat Res 1993;14:137–48) for inverse problems of steady-state aquifer models is proposed. Through detailed analysis of the “built-in” but irregular weighting effects of the coefficient matrix on the residuals on the discrete governing equations, a so-called scaling matrix is introduced to improve the great irregular weighting effects of these residuals adaptively in every Gauss–Newton iteration. Numerical results demonstrate that if the scaling matrix equals the identity matrix (i.e., the irregular weighting effects of the coefficient matrix are not balanced), our algorithm does not perform well, e.g., the computation cost is higher than that of the traditional method, and what is worse is the calculations fail to converge for some initial values of the unknown parameters. This poor situation takes a favourable turn dramatically if the scaling matrix is slightly improved and a simple preconditioning technique is adopted: For naturally chosen simple diagonal forms of the scaling matrix and the preconditioner, the method performs well and gives accurate results with low computational cost just like the traditional methods, and improvements are obtained on: (1) widening the range of the initial values of the unknown parameters within which the minimizing iterations can converge, (2) reducing the computational cost in every Gauss–Newton iteration, (3) improving the irregular weighting effects of the coefficient matrix of the discrete governing equations. Consequently, the example inverse problem in Bentley (loc. cit.) is solved with the same accuracy, less computational effort and without the regularization term containing prior information on the unknown parameters. Moreover, numerical example shows that this method can solve the inverse problem of the quasilinear Boussinesq equation almost as fast as the linear one.In every Gauss–Newton iteration of our algorithm, one needs to solve a linear least-squares system about the corrections of both the parameters and the groundwater heads on all the discrete nodes only once. In comparison, every Gauss–Newton iteration of the traditional method has to solve the discrete governing equations as many times as one plus the number of unknown parameters or head observation wells (Yeh WW-G. Wat Resour Res 1986;22:95–108).All these facts demonstrate the potential of the algorithm to solve inverse problems of more complicated non-linear aquifer models naturally and quickly on the basis of finding suitable forms of the scaling matrix and the preconditioner.     

Partial eigensolution of damped structural systems by Arnoldi's method

An efficient numerical algorithm is developed to solve the quadratic eigenvalue problems arising in the dynamic analysis of damped structural systems. The algorithm can even be applied to structural systems with non-symmetric matrices. The algorithm is based on the use of Arnoldi's method to generate a Krylov subspace of trial vectors, which is then used to reduce a large eigenvalue problem to a much smaller one. The reduced eigenvalue problem is solved and the solutions are used to construct approximate solutions to the original large system. In the process, the algorithm takes full advantage of the sparseness and symmetry of the system matrices and requires no complex arithmetic, therefore, making it very economical for use in solving large problems. The numerical results from test examples are presented to demonstrate that a large fraction of the approximate solutions calculated are very accurate, indicating that the algorithm is highly effective for extracting a number of vibration modes for a large dynamic system, whether it is lightly or heavily damped.     

正则化预处理迭代算法在频率域声波模拟中的应用

高精度及高效频率域声波数值模拟的关键在于高效求解声波方程经离散化后得到的大型稀疏线性方程组.该方程组系数矩阵具有很强的稀疏性,非对称性和非正定性等特征,常用的迭代算法难以准确、高效地求解.为了改善数值模拟迭代算法的收敛性与稳定性,在算法基础上添加预条件算子是求解该类方程的常用方案.本文基于以上思路,引入正则化技术来构造合适的预条件算子,提出正则化预条件迭代算法,以加速求解方程组.通过包含有均匀介质和高非均匀度介质(Marmousi)模型的数值模拟实验结果表明:与单独使用迭代算法相比,本文提出的正则化预条件迭代算法在计算量方面仅多了一次矩阵-矢量相乘,内存消耗未增加;同时,基于该算法的数值模拟结果能够满足精度要求,较单独使用迭代法能够有效改善收敛性质,加快收敛速度;而且,在二维模型算例下,与LU分解算法相比,基于该算法的内存消耗大幅下降.     

EVALUATION OF SOME IMPLICIT TIME-STEPPING ALGORITHMS FOR PSEUDODYNAMIC TESTS

Two types of implicit time-stepping algorithms have been proposed recently for pseudodynamic tests. The first type consists of an algorithm which relies on Newton iterations to satisfy the equations of motion. The second type consists of an algorithm which is based on the Operator-Splitting technique and does not require any numerical iteration. While one or the other has been preferred by some researchers, these time-stepping algorithms have not been analysed and compared under a uniform setting. In this paper, a concise summary of these schemes is presented, and they are evaluated in a consistent manner in terms of numerical dissipation, frequency distortion and experimental errors. The analytical results are validated by numerical simulations as well as experimental results. It is shown that the algorithm based on Newton iterations can control experimental error effects effectively by means of an error-correction procedure. The algorithm based on the Operator-Splitting technique demonstrates similar performance provided the I-Modification is adopted.     

A Constitutive Scaling Law for Shear Rupture that is Inherently Scale-dependent, and Physical Scaling of Nucleation Time to Critical Point

It is shown that the rupture nucleation length increases up to the critical length with time according to a power law, and that the accelerating phase of nucleation leading up to the critical point is scaled in the framework of fracture mechanics based on slip-dependent constitutive formulation. Geometric irregularity of the rupturing surfaces plays a fundamental role in scaling the accelerating phase of nucleation up to the critical point. A power-law scaling relation between the rupture growth length and the nucleation time to the critical point is derived from theoretical consideration based on laboratory data. This power-law scaling relation has no singularity, and hence it may be useful for the predictive purpose of an imminent, large earthquake.     

Efficient simulation of geothermal processes in heterogeneous porous media based on the exponential Rosenbrock–Euler and Rosenbrock-type methods

Simulation of geothermal systems is challenging due to coupled physical processes in highly heterogeneous media. Combining the exponential Rosenbrock–Euler method and Rosenbrock-type methods with control-volume (two-point flux approximation) space discretizations leads to efficient numerical techniques for simulating geothermal systems. In terms of efficiency and accuracy, the exponential Rosenbrock–Euler time integrator has advantages over standard time-discretization schemes, which suffer from time-step restrictions or excessive numerical diffusion when advection processes are dominating. Based on linearization of the equation at each time step, we make use of matrix exponentials of the Jacobian from the spatial discretization, which provide the exact solution in time for the linearized equations. This is at the expense of computing the matrix exponentials of the stiff Jacobian matrix, together with propagating a linearized system. However, using a Krylov subspace or Léja points techniques make these computations efficient.The Rosenbrock-type methods use the appropriate rational functions of the Jacobian of the ODEs resulting from the spatial discretization. The parameters in these schemes are found in consistency with the required order of convergence in time. As a result, these schemes are A-stable and only a few linear systems are solved at each time step. The efficiency of the methods compared to standard time-discretization techniques are demonstrated in numerical examples.     

Nonlinear iteration methods for nonequilibrium multiphase subsurface flow

Fully implicit, fully coupled techniques are developed for simulating multiphase flow with nonequilibrium mass transfer between phases, with application to groundwater contaminant flow and transport. Numerical issues which are addressed include: use of MUSCL or Van Leer flux limiters to reduce numerical dispersion, use of full or approximate Jacobian for flux limiter methods, and variable substitution for increased Newton iteration efficiency. A comparison of the performance of equilibrium and nonequilibrium models is also presented.     

三维感应测井响应计算的交错网格有限差分法

应用交错网格有限差分法计算三维复杂环境中的感应测井响应. 其中，利用Krylov子空间不变性求解离散得到的大型稀疏复对称线性方程组. 在构造Krylov子空间时使用其系数矩阵的伪逆以改善迭代的收敛性. 迭代中，使用不完全Cholesky分解共轭梯度法求解4个三维Poisson方程以得到新的Lanczos向量. 通常迭代不超过20次可得到理想结果. 另外，提出一种新的物质平均公式以计算电导率平均值，可保证电流守恒.     

三维时间域航空电磁有理Krylov正演研究

常规的三维时间域航空电磁模拟通常采用隐式步长方法进行时间离散,需要几次矩阵分解和上百次右端源项回带,计算效率较低.为了提高正演计算效率,本文提出使用有理Krylov方法求解时间域电场扩散方程.首先使用非结构四面体网格进行空间离散,采用Nédélec矢量基函数近似四面体单元内的电场;然后基于有限元离散给出矩阵指数和矢量乘积表示的电场显式解;最后采用有理Arnoldi算法构造Krylov子空间内的正交基函数并进一步求解矩阵指数与矢量的乘积,直接得到任意时刻的电场解向量,避免步长离散过程.此外,本文还提出一种指数加权偏移参数优化方法,使得有理Arnoldi近似在瞬变衰减晚期具备更高的精度,从而降低Krylov子空间阶数并提高计算效率.通过和层状模型解析解的对比验证了有理Krylov方法的精度.针对三维异常体模型使用全局网格和局部网格剖分并和其他数值方法比较,进一步说明了有理Krylov方法的有效性.     

New preconditioning strategy for Jacobian-free solvers for variably saturated flows with Richards’ equation

We develop a new approach for solving the nonlinear Richards’ equation arising in variably saturated flow modeling. The growing complexity of geometric models for simulation of subsurface flows leads to the necessity of using unstructured meshes and advanced discretization methods. Typically, a numerical solution is obtained by first discretizing PDEs and then solving the resulting system of nonlinear discrete equations with a Newton-Raphson-type method. Efficiency and robustness of the existing solvers rely on many factors, including an empiric quality control of intermediate iterates, complexity of the employed discretization method and a customized preconditioner. We propose and analyze a new preconditioning strategy that is based on a stable discretization of the continuum Jacobian. We will show with numerical experiments for challenging problems in subsurface hydrology that this new preconditioner improves convergence of the existing Jacobian-free solvers 3-20 times. We also show that the Picard method with this preconditioner becomes a more efficient nonlinear solver than a few widely used Jacobian-free solvers.     

Lens eddies in rotating two-fluid systems

Abstract

Laboratory experiments are conducted on the instantaneous release of a constant volume of intermediate density fluid along the interface of a two-layer fluid system in rigid body rotation about a vertical axis. Such a system leads to the development of a thin lens of fluid with anticyclonic motion which grows in radial extent to reach an equilibrium radius as the radial motion is captured by Coriolis effects, becomes unstable to non-symmetric dusturbances, and finally decays due to the action of fluid viscosity. Scaling and dimensional analysis arguments are advanced for the growth, equilibrium and decay phases of the motion. The scaling analysis for the initial growth and equilibrium phases are shown to be in good agreement with the experimental observations. The lens decay data do not collapse under the assumption of a simple Ekman spindown model assuming immiscible fluids. An empirical fit of the data for the decay phase is presented.     

基于改进Krylov子空间算法的井中激电反演

井中激电是二次找矿重要的地球物理勘探手段,快速而稳定的正反演算法有助于方法的推广和应用.本文在正演模拟中,给出了考虑井眼影响下的网格剖分方式;用右端项校正技术减小边界效应和源点奇异性引起的模拟误差;并采用循环Krylov子空间算法提高多线性方程组的求解效率.反演用Gauss-Newton法结合Jacobian-free Krylov迭代求解技术,给出了Jacobian矩阵向量积的简化计算方法;用不精确预处理共轭梯度法对模型修正量方程近似求解以减少计算量;采用不同于正演的反演网格剖分降低不适定性.数值算例验证了相关算法的有效性和可靠性.     

Finite element analysis of three-dimensional groundwater flow problems

A numerical method is presented for analysing either steady state or transient three-dimensional groundwater flow problems. The governing equation is formulated in terms of the finite element process using the Galerkin approach, and cubic isoparametric elements are used to simulate the flow domain as these permit accurate modelling of curved boundaries. Particular attention is paid to the time dependent movement of the phreatic surface where an iterative technique based on the replacement of the original transient problem by a discrete number of steady state problems is used to effect a solution. Furthermore, in tracing the movement of the surface use is made of the element formulation theory in order to compute the normal to the boundary.The validity of the technique is first established by analysing a radially symmetrical problem for which an alternative analytical solution is available. Finally, a general three-dimensional flow system is studied for which there is no known analytical solution. It is shown that relatively few elements are required to yield practical solutions.     

电导率各向异性的海洋电磁三维有限单元法正演

本文提出了一种基于非结构化网格的海洋电磁有限单元正演算法.为了回避场源奇异性,文中选用二次场算法,将背景电阻率设置为水平层状且各向异性,场源在水平层状各向异性介质中所激发的一次场通过汉克尔积分得到.基于Coulomb规范得到二次矢量位和标量位所满足的Maxwell方程组,通过Galerkin加权余量法形成大型稀疏有限元方程,采用不完全LU分解(ILU)预条件因子的quasi-minimum residual(QMR)迭代解法对有限元方程进行求解得到二次矢量位和标量位;进而,利用滑动平均方法得到二次矢量位和标量位在空间的导数,由此得到二次电磁场;通过一维模型对算法的可靠性进行验证,与此同时,针对实际复杂海洋电磁模型,比较有限元模拟结果与积分方程模拟结果,进一步验证算法精度.若干计算结果均表明,文中算法具有良好的通用性,适用于井中电磁、航空电磁,环境地球物理等非均匀且各向异性介质中的电磁感应基础研究.     

Complex polynomials for the computation of 2D gravity anomalies

We present an efficient algorithm using a complex variables formulation for the computation of the gravity effect of 2D polygonal bodies having densities varying both laterally and with depth. The first derivatives of the gravity effect are also provided in order to enable the computation of the Jacobian matrix, which is necessary for linear inverse gravity problems. A geophysical example based on numerical assumptions about the density contrast on a well-studied basin area shows the applicability of the algorithm.     

Stochastic seismic sliding of rigid mass supported through non-symmetric friction

The sliding behaviour of a rigid mass supported on a randomly vibrating foundation through a non-symmetric Coulomb-friction contact is studied both analytically and by numerical simulation. The analysis is based on a stationary solution of the associated Fokker-Planck equation, and makes use of equivalent linearization and of a suitable decomposition of the non-zero mean non-stationary sliding process. It is shown that the analytical results yield several exact asymptotic expansions for both small and large values of time. An extensive Monte Carlo type numerical simulation study produces non-stationary response statistics which are in very good accord with the analytical results. Furthermore, it is found that Gumbel's Extreme Value Distribution reproduces with remarkable accuracy the observed cumulative frequency of maximum slip displacement. The results of this paper may find application in seismic design of embankment dams, earth retaining walls and base ‘isolation’ systems.