High-order numerical method for the nonlinear Helmholtz equation with material discontinuities in one space dimension

The nonlinear Helmholtz equation (NLH) models the propagation of electromagnetic waves in Kerr media, and describes a range of important phenomena in nonlinear optics and in other areas. In our previous work, we developed a fourth order method for its numerical solution that involved an iterative solver based on freezing the nonlinearity. The method enabled a direct simulation of nonlinear self-focusing in the nonparaxial regime, and a quantitative prediction of backscattering. However, our simulations showed that there is a threshold value for the magnitude of the nonlinearity, above which the iterations diverge.In this study, we numerically solve the one-dimensional NLH using a Newton-type nonlinear solver. Because the Kerr nonlinearity contains absolute values of the field, the NLH has to be recast as a system of two real equations in order to apply Newton’s method. Our numerical simulations show that Newton’s method converges rapidly and, in contradistinction with the iterations based on freezing the nonlinearity, enables computations for very high levels of nonlinearity.In addition, we introduce a novel compact finite-volume fourth order discretization for the NLH with material discontinuities. Our computations corroborate the design fourth order convergence of the method.The one-dimensional results of the current paper create a foundation for the analysis of multidimensional problems in the future.     

A numerical algorithm for the solution of a phase-field model of polycrystalline materials

We describe an algorithm for the numerical solution of a phase-field model (PFM) of microstructure evolution in polycrystalline materials. The PFM system of equations includes a local order parameter, a quaternion representation of local orientation and a species composition parameter. The algorithm is based on the implicit integration of a semidiscretization of the PFM system using a backward difference formula (BDF) temporal discretization combined with a Newton–Krylov algorithm to solve the nonlinear system at each time step. The BDF algorithm is combined with a coordinate-projection method to maintain quaternion unit length, which is related to an important solution invariant. A key element of the Newton–Krylov algorithm is the selection of a preconditioner to accelerate the convergence of the Generalized Minimum Residual algorithm used to solve the Jacobian linear system in each Newton step. Results are presented for the application of the algorithm to 2D and 3D examples.     

Numerical solution of the one-dimensional Burgers’ equation: Implicit and fully implicit exponential finite difference methods

This paper describes two new techniques which give improved exponential finite difference solutions of Burgers’ equation. These techniques are called implicit exponential finite difference method and fully implicit exponential finite difference method for solving Burgers’ equation. As the Burgers’ equation is nonlinear, the scheme leads to a system of nonlinear equations. At each time-step, Newton’s method is used to solve this nonlinear system. The results are compared with exact values and it is clearly shown that results obtained using both the methods are precise and reliable.     

A high-order accurate unstructured finite volume Newton–Krylov algorithm for inviscid compressible flows

A fast implicit Newton–Krylov finite volume algorithm has been developed for high-order unstructured steady-state computation of inviscid compressible flows. The matrix-free generalized minimal residual (GMRES) algorithm is used for solving the linear system arising from implicit discretization of the governing equations, avoiding expensive and complex explicit computation of the high-order Jacobian matrix. The solution process has been divided into two phases: start-up and Newton iterations. In the start-up phase an approximate solution with the general characteristics of the steady-state flow is computed by using a defect correction procedure. At the end of the start-up phase, the linearization of the flow field is accurate enough for steady-state solution, and a quasi-Newton method is used, with an infinite time step and very rapid convergence. A proper limiter implementation for efficient convergence of the high-order discretization is discussed and a new formula for limiting the high-order terms of the reconstruction polynomial is introduced. The accuracy, fast convergence and robustness of the proposed high-order unstructured Newton–Krylov solver for different speed regimes is demonstrated for the second, third and fourth-order discretization. The possibility of reducing computational cost required for a given level of accuracy by using high-order discretization is examined.     

基于L-M算法的反向传播网络的湿度传感器输出误差补偿研究

针对湿度传感器的输出非线性问题,提出了基于L-M算法建立BP神经网络进行补偿校正,实现电阻湿度传感器的输入与输出非线性补偿,并与共轭梯度算法、拟牛顿算法所建立的神经网路模型进行对比,重点比较了模型误差性能、收敛速度。结果表明：基于L-M算法建立的神经网络模型,在收敛速度、误差性能等方面具有更高效的表现,更适合湿度传感器的非线性特性的补偿校正。     

A fixed-mesh method for incompressible flow–structure systems with finite solid deformations

A fixed-mesh algorithm is proposed for simulating flow–structure interactions such as those occurring in biological systems, in which both the fluid and solid are incompressible and the solid deformations are large. Several of the well-known difficulties in simulating such flow–structure interactions are avoided by formulating a single set of equations of motion on a fixed Eulerian mesh. The solid’s deformation is tracked to compute elastic stresses by an overlapping Lagrangian mesh. In this way, the flow–structure interaction is formulated as a distributed body force and singular surface force acting on an otherwise purely fluid system. These forces, which depend on the solid elastic stress distribution, are computed on the Lagrangian mesh by a standard finite-element method and then transferred to the fixed Eulerian mesh, where the joint momentum and continuity equations are solved by a finite-difference method. The constitutive model for the solid can be quite general. For the force transfer, standard immersed-boundary and immersed-interface methods can be used and are demonstrated. We have also developed and demonstrated a new projection method that unifies the transfer of the surface and body forces in a way that exactly conserves momentum; the interface is still effectively sharp for this approach. The spatial convergence of the method is observed to be between first- and second-order, as in most immersed-boundary methods for membrane flows. The algorithm is demonstrated by the simulations of an advected elastic disk, a flexible leaflet in an oscillating flow, and a model of a swimming jellyfish.     

Analysis of Two-Grid Methods for Nonlinear Parabolic Equations by Expanded Mixed Finite Element Methods

In this paper, we present an efficient method of two-grid scheme for the approximation of two-dimensional nonlinear parabolic equations using an expanded mixed finite element method. We use two Newton iterations on the fine grid in our methods. Firstly, we solve an original nonlinear problem on the coarse nonlinear grid, then we use Newton iterations on the fine grid twice. The two-grid idea is from Xu$'$s work [SIAM J. Numer. Anal., 33 (1996), pp. 1759-1777] on standard finite method. We also obtain the error estimates for the algorithms of the two-grid method. It is shown that the algorithm achieves asymptotically optimal approximation rate with the two-grid methods as long as the mesh sizes satisfy $h=\mathcal{O}(H^{(4k+1)/(k+1)})$.     

Exponential speedup of quantum newton optimization algorithm for general polynomials

Quantum optimization algorithms can outperform their classical counterpart and are key in modern technology. The second-order optimization algorithm(the Newton algorithm) is a critical optimization method, speeding up the convergence by employing the second-order derivative of loss functions in addition to their first derivative. Here, we propose a new quantum second-order optimization algorithm for general polynomials with a computational complexity of O(poly(log d)). We use this algorithm to solve the nonlinear equation and learning parameter problems in factorization machines. Numerical simulations show that our new algorithm is faster than its classical counterpart and the first-order quantum gradient descent algorithm. While existing quantum Newton optimization algorithms apply only to homogeneous polynomials, our new algorithm can be used in the case of general polynomials, which are more widely present in real applications.     

Computation of invariant tori by Newton–Krylov methods in large-scale dissipative systems

A method to compute invariant tori in high-dimensional systems, obtained as discretizations of PDEs, by continuation and Newton–Krylov methods is described. Invariant tori are found as fixed points of a generalized Poincaré map so that the dimension of the system of equations to be solved is that of the original system. Due to the dissipative nature of the problems studied, the convergence of the linear solvers is extremely fast. The computation of periodic orbits inside the Arnold’s tongues is also considered. Thermal convection of a binary mixture of fluids, in a rectangular cavity, has been used to test the method.     

Evaluating the accuracy performance of Lucas-Kanade algorithm in the circumstance of PIV application

Lucas-Kanade(LK) algorithm, usually used in optical flow filed, has recently received increasing attention from PIV community due to its advanced calculation efficiency by GPU acceleration. Although applications of this algorithm are continuously emerging,a systematic performance evaluation is still lacking. This forms the primary aim of the present work. Three warping schemes in the family of LK algorithm: forward/inverse/symmetric warping, are evaluated in a prototype flow of a hierarchy of multiple two-dimensional vortices. Second-order Newton descent is also considered here. The accuracy efficiency of all these LK variants are investigated under a large domain of various influential parameters. It is found that the constant displacement constraint, which is a necessary building block for GPU acceleration, is the most critical issue in affecting LK algorithm's accuracy, which can be somehow ameliorated by using second-order Newton descent. Moreover, symmetric warping outbids the other two warping schemes in accuracy level, robustness to noise, convergence speed and tolerance to displacement gradient, and might be the first choice when applying LK algorithm to PIV measurement.     

Bulk velocity extraction for nano-scale Newtonian flows

The conventional velocity extraction algorithm in MDS method has difficulty to determine the small flow velocity. This study proposes a new method to calculate the bulk velocity in nano-flows. Based on the Newton?s law of viscosity, according to the calculated viscosities and shear stresses, the flow velocity can be obtained by numerical integration. This new method can overcome the difficulty existed in the conventional MDS method and improve the stability of the computational process. Numerical results show that this method is effective for the extraction of bulk velocity, no matter the bulk velocity is large or small.     

反射式牛顿环系统在微振动测量中的应用

为了拓展牛顿环系统的应用领域,探索了反射式牛顿环系统在微振动测量中的应用,推导出了振幅和频率的测量公式,阐述了微振动的全过程就是牛顿环条纹不停地吞吐条纹的变化过程,分析了反射式牛顿环系统只能测量微振动的原因。     

The multidimensional moment-constrained maximum entropy problem: A BFGS algorithm with constraint scaling

In a recent paper we developed a new algorithm for the moment-constrained maximum entropy problem in a multidimensional setting, using a multidimensional orthogonal polynomial basis in the dual space of Lagrange multipliers to achieve numerical stability and rapid convergence of the Newton iterations. Here we introduce two new improvements for the existing algorithm, adding significant computational speedup in situations with many moment constraints, where the original algorithm is known to converge slowly. The first improvement is the use of the BFGS iterations to progress between successive polynomial reorthogonalizations rather than single Newton steps, typically reducing the total number of computationally expensive polynomial reorthogonalizations for the same maximum entropy problem. The second improvement is a constraint rescaling, aimed to reduce relative difference in the order of magnitude between different moment constraints, improving numerical stability of iterations due to reduced sensitivity of different constraints to changes in Lagrange multipliers. We observe that these two improvements can yield an average wall clock time speedup of 5–6 times compared to the original algorithm.     

Unconditionally convergent nonlinear solver for hyperbolic conservation laws with S-shaped flux functions

This paper addresses the convergence properties of implicit numerical solution algorithms for nonlinear hyperbolic transport problems. It is shown that the Newton–Raphson (NR) method converges for any time step size, if the flux function is convex, concave, or linear, which is, in general, the case for CFD problems. In some problems, e.g., multiphase flow in porous media, the nonlinear flux function is S-shaped (not uniformly convex or concave); as a result, a standard NR iteration can diverge for large time steps, even if an implicit discretization scheme is used to solve the nonlinear system of equations. In practice, when such convergence difficulties are encountered, the current time step is cut, previous iterations are discarded, a smaller time step size is tried, and the NR process is repeated. The criteria for time step cutting and selection are usually based on heuristics that limit the allowable change in the solution over a time step and/or NR iteration. Here, we propose a simple modification to the NR iteration scheme for conservation laws with S-shaped flux functions that converges for any time step size. The new scheme allows one to choose the time step size based on accuracy consideration only without worrying about the convergence behavior of the nonlinear solver. The proposed method can be implemented in an existing simulator, e.g., for CO₂ sequestration or reservoir flow modeling, quite easily. The numerical analysis is confirmed with simulation studies using various test cases of nonlinear multiphase transport in porous media. The analysis and numerical experiments demonstrate that the modified scheme allows for the use of arbitrarily large time steps for this class of problems.     

Pedestrian intention prediction based on dynamic fuzzy automata for vehicle driving at nighttime

In this paper, we propose a novel algorithm that can predict a pedestrian’s intention using images captured by a far-infrared thermal camera mounted on a moving car at nighttime. To predict a pedestrian’s intention in consecutive sequences, we use the dynamic fuzzy automata (DFA) method, which not only provides a systemic approach for handling uncertainty but also is able to handle continuous spaces. As the spatio-temporal features, the distance between the curbs and the pedestrian and the pedestrian’s velocity and head orientation are used. In this study, we define four intention states of the pedestrian: Standing-Sidewalk (S-SW), Walking-Sidewalk (W-SW), Walking-Crossing (W-Cro), and Running-Crossing (R-Cro). In every frame, the proposed system determines the final intention of the pedestrian as ‘Stop’ if the pedestrian’s intention state is S-SW or W-SW. In contrast, the proposed system determines the final intention of a pedestrian as ‘Cross’ if the pedestrian’s intention state is W-Cro or R-Cro. A performance comparison with other related methods shows that the performance of the proposed algorithm is better than that of other related methods. The proposed algorithm was successfully applied to our dataset, which includes complex environments with many pedestrians.     

A novel method of Newton iteration-based interval analysis for multidisciplinary systems

A Newton iteration-based interval uncertainty analysis method (NI-IUAM) is proposed to analyze the propagating effect of interval uncertainty in multidisciplinary systems. NI-IUAM decomposes one multidisciplinary system into single disciplines and utilizes a Newton iteration equation to obtain the upper and lower bounds of coupled state variables at each iterative step. NI-IUAM only needs to determine the bounds of uncertain parameters and does not require specific distribution formats. In this way, NI-IUAM may greatly reduce the necessity for raw data. In addition, NI-IUAM can accelerate the convergence process as a result of the super-linear convergence of Newton iteration. The applicability of the proposed method is discussed, in particular that solutions obtained in each discipline must be compatible in multidisciplinary systems. The validity and efficiency of NI-IUAM is demonstrated by both numerical and engineering examples.     

离散牛顿正则化方法及应用

把离散Newton法和解不适定问题的正则化方法结合起来,给出了离散Newton正则化方法的迭代格式,并给出了这种迭代格式的收敛性分析的结果。最后考虑了这种方法在微分方程反问题上的应用,数值计算结果表明了这种方法的有效性。     

Solving the 3D MHD equilibrium equations in toroidal geometry by Newton’s method

We describe a novel form of Newton’s method for computing 3D MHD equilibria. The method has been implemented as an extension to the hybrid spectral/finite-difference Princeton Iterative Equilibrium Solver (PIES) which normally uses Picard iteration on the full nonlinear MHD equilibrium equations. Computing the Newton functional derivative numerically is not feasible in a code of this type but we are able to do the calculation analytically in magnetic coordinates by considering the response of the plasma’s Pfirsch–Schlüter currents to small changes in the magnetic field. Results demonstrate a significant advantage over Picard iteration in many cases, including simple finite-β stellarator equilibria. The method shows promise in cases that are difficult for Picard iteration, although it is sensitive to resolution and imperfections in the magnetic coordinates, and further work is required to adapt it to the presence of magnetic islands and stochastic regions.     

Fast finite difference solvers for singular solutions of the elliptic Monge–Ampère equation

The elliptic Monge–Ampère equation is a fully nonlinear Partial Differential Equation which originated in geometric surface theory, and has been applied in dynamic meteorology, elasticity, geometric optics, image processing and image registration. Solutions can be singular, in which case standard numerical approaches fail.In this article we build a finite difference solver for the Monge–Ampère equation, which converges even for singular solutions. Regularity results are used to select a priori between a stable, provably convergent monotone discretization and an accurate finite difference discretization in different regions of the computational domain. This allows singular solutions to be computed using a stable method, and regular solutions to be computed more accurately. The resulting nonlinear equations are then solved by Newton’s method.Computational results in two and three-dimensions validate the claims of accuracy and solution speed. A computational example is presented which demonstrates the necessity of the use of the monotone scheme near singularities.     

Dual timestepping methods for detailed combustion chemistry

In this work, we develop and study several dual time integration methods for the solution of stiff, explosive differential equations governing combustion chemistry. Dual time integration is an implicit method wherein the sub-iteration process of each timestep is performed as a steady-state integration process, rather than the commonly used Newton–Raphson method. This allows stabilisation when nonlinear ignition events are contained within a timestep, providing considerable freedom in the choice of resolved phenomena. Timesteps may be chosen so as to resolve relatively long process timescales accurately rather than fast chemical timescales, something not possible with the common Newton's method. We illustrate this method using several backward difference formula methods and demonstrate the efficacy of our method in resolving low-frequency solutions of continuous flow stirred-tank reactors with periodic ignition–extinction events. We are able to step over ignition–extinction events with our stable, adaptive dual time method, and we study numerical convergence and error scaling on process timescales.