Efficient Nonlinear Solvers for Nodal High-Order Finite Elements in 3D

Conventional high-order finite element methods are rarely used for industrial problems because the Jacobian rapidly loses sparsity as the order is increased, leading to unaffordable solve times and memory requirements. This effect typically limits order to at most quadratic, despite the favorable accuracy and stability properties offered by quadratic and higher order discretizations. We present a method in which the action of the Jacobian is applied matrix-free exploiting a tensor product basis on hexahedral elements, while much sparser matrices based on Q ₁ sub-elements on the nodes of the high-order basis are assembled for preconditioning. With this “dual-order” scheme, storage is independent of spectral order and a natural taping scheme is available to update a full-accuracy matrix-free Jacobian during residual evaluation. Matrix-free Jacobian application circumvents the memory bandwidth bottleneck typical of sparse matrix operations, providing several times greater floating point performance and better use of multiple cores with shared memory bus. Computational results for the p-Laplacian and Stokes problem, using block preconditioners and AMG, demonstrate mesh-independent convergence rates and weak (bounded) dependence on order, even for highly deformed meshes and nonlinear systems with several orders of magnitude dynamic range in coefficients. For spectral orders around 5, the dual-order scheme requires half the memory and similar time to assembled quadratic (Q ₂) elements, making it very affordable for general use.     

Higher-order split-step Fourier schemes for the generalized nonlinear Schrödinger equation

The generalized nonlinear Schrödinger (GNLS) equation is solved numerically by a split-step Fourier method. The first, second and fourth-order versions of the method are presented. A classical problem concerning the motion of a single solitary wave is used to compare the first, second and fourth-order schemes in terms of the accuracy and the computational cost. This numerical experiment shows that the split-step Fourier method provides highly accurate solutions for the GNLS equation and that the fourth-order scheme is computationally more efficient than the first-order and second-order schemes. Furthermore, two test problems concerning the interaction of two solitary waves and an exact solution that blows up in finite time, respectively, are investigated by using the fourth-order split-step scheme and particular attention is paid to the conserved quantities as an indicator of the accuracy. The question how the present numerical results are related to those obtained in the literature is discussed.     

Three-dimensional aerodynamic computations on unstructured grids using a Newton-Krylov approach

A Newton-Krylov algorithm is presented for the compressible Navier-Stokes equations in three dimensions on unstructured grids. The algorithm uses a preconditioned matrix-free Krylov method to solve the linear system that arises in the Newton iterations. Incomplete factorization is used as the preconditioner, based on an approximate Jacobian matrix after the reverse Cuthill-McKee reordering of the unknowns. Several approximate viscous operators that involve only the nearest neighboring terms are studied to reduce the cost of preconditioning. The performance of the algorithm is demonstrated through numerical studies of the ONERA M6 wing and the DLR-F6 wing-body configuration. A ten-order-of-magnitude residual reduction for the wing and wing-body configurations can be obtained with a computing cost equivalent to 5500 and 8000 function evaluations, respectively, on grids with a half million nodes.     

A split-step Fourier method for the complex modified Korteweg-de Vries equation

In this study, the complex modified Korteweg-de Vries (CMKdV) equation is solved numerically by three different split-step Fourier schemes. The main difference among the three schemes is in the order of the splitting approximation used to factorize the exponential operator. The space variable is discretized by means of a Fourier method for both linear and nonlinear subproblems. A fourth-order Runge-Kutta scheme is used for the time integration of the nonlinear subproblem. Classical problems concerning the motion of a single solitary wave with a constant polarization angle are used to compare the schemes in terms of the accuracy and the computational cost. Furthermore, the interaction of two solitary waves with orthogonal polarizations is investigated and particular attention is paid to the conserved quantities as an indicator of the accuracy. Numerical tests show that the split-step Fourier method provides highly accurate solutions for the CMKdV equation.     

Fast algorithms for high-order numerical methods for space-fractional diffusion equations

In this paper, fast numerical methods for solving space-fractional diffusion equations are studied in two stages. Firstly, a fast direct solver for an implicit finite difference scheme proposed by Hao et al. [A fourth-order approximation of fractional derivatives with its applications, J. Comput. Phys. 281 (2015), pp. 787–805], which is fourth-order accurate in space and second-order accurate in time, is developed based on a circulant-and-skew-circulant (CS) representation of Toeplitz matrix inversion. Secondly, boundary value method with spatial discretization of Hao et al. [A fourth-order approximation of fractional derivatives with its applications, J. Comput. Phys. 281 (2015), pp. 787–805] is adopted to produce a numerical solution with higher order accuracy in time. Particularly, a method with fourth-order accuracy in both space and time can be achieved. GMRES method is employed for solving the discretized linear system with two preconditioners. Based on the CS representation of Toeplitz matrix inversion, the two preconditioners can be applied efficiently, and the convergence rate of the preconditioned GMRES method is proven to be fast. Numerical examples are given to support the theoretical analysis.     

A Matrix-free Two-grid Preconditioner for Solving Boundary Integral Equations in Electromagnetism

In this paper, we describe a matrix-free iterative algorithm based on the GMRES method for solving electromagnetic scattering problems expressed in an integral formulation. Integral methods are an interesting alternative to differential equation solvers for this problem class since they do not require absorbing boundary conditions and they mesh only the surface of the radiating object giving rise to dense and smaller linear systems of equations. However, in realistic applications the discretized systems can be very large and for some integral formulations, like the popular Electric Field Integral Equation, they become ill-conditioned when the frequency increases. This means that iterative Krylov solvers have to be combined with fast methods for the matrix-vector products and robust preconditioning to be affordable in terms of CPU time. In this work we describe a matrix-free two-grid preconditioner for the GMRES solver combined with the Fast Multipole Method. The preconditioner is an algebraic two-grid cycle built on top of a sparse approximate inverse that is used as smoother, while the grid transfer operators are defined using spectral information of the preconditioned matrix. Experiments on a set of linear systems arising from real radar cross section calculation in industry illustrate the potential of the proposed approach for solving large-scale problems in electromagnetism.     

A matrix-free quasi-Newton method for solving large-scale nonlinear systems

One of the widely used methods for solving a nonlinear system of equations is the quasi-Newton method. The basic idea underlining this type of method is to approximate the solution of Newton’s equation by means of approximating the Jacobian matrix via quasi-Newton update. Application of quasi-Newton methods for large scale problems requires, in principle, vast computational resource to form and store an approximation to the Jacobian matrix of the underlying problem. Hence, this paper proposes an approximation for Newton-step based on the update of approximation requiring a computational effort similar to that of matrix-free settings. It is made possible by approximating the Jacobian into a diagonal matrix using the least-change secant updating strategy, commonly employed in the development of quasi-Newton methods. Under suitable assumptions, local convergence of the proposed method is proved for nonsingular systems. Numerical experiments on popular test problems confirm the effectiveness of the approach in comparison with Newton’s, Chord Newton’s and Broyden’s methods.     

Towards optimal explicit time-stepping schemes for the gyrokinetic equations

The nonlinear gyrokinetic equations describe plasma turbulence in laboratory and astrophysical plasmas. To solve these equations, massively parallel codes have been developed and run on present-day supercomputers. This paper describes measures to improve the efficiency of such computations, thereby making them more realistic. Explicit Runge–Kutta schemes are considered to be well suited for time-stepping. Although the numerical algorithms are often highly optimized, performance can still be improved by a suitable choice of the time-stepping scheme, based on the spectral analysis of the underlying operator. Here, an operator splitting technique is introduced to combine first-order Runge–Kutta–Chebychev schemes for the collision term with fourth-order schemes for the remaining terms. In the nonlinear regime, based on the observation of eigenvalue shifts due to the (generalized) E×B$E\times B$ advection term, an accurate and robust estimate for the nonlinear timestep is developed. The presented techniques can reduce simulation times by factors of up to three in realistic cases. This substantial speedup encourages the use of similar timestep optimized explicit schemes not only for the gyrokinetic equation, but also for other applications with comparable properties.     

Multiplicative Operator Splittings in Nonlinear Diffusion: From Spatial Splitting to Multiple Timesteps

Operator splitting is a powerful concept used in many diversed fields of applied mathematics for the design of effective numerical schemes. Following the success of the additive operator splitting (AOS) in performing an efficient nonlinear diffusion filtering on digital images, we analyze the possibility of using multiplicative operator splittings to process images from different perspectives.We start by examining the potential of using fractional step methods to design a multiplicative operator splitting as an alternative to AOS schemes. By means of a Strang splitting, we attempt to use numerical schemes that are known to be more accurate in linear diffusion processes and apply them on images. Initially we implement the Crank-Nicolson and DuFort-Frankel schemes to diffuse noisy signals in one dimension and devise a simple extrapolation that enables the Crank-Nicolson to be used with high accuracy on these signals. We then combine the Crank-Nicolson in 1D with various multiplicative operator splittings to process images. Based on these ideas we obtain some interesting results. However, from the practical standpoint, due to the computational expenses associated with these schemes and the questionable benefits in applying them to perform nonlinear diffusion filtering when using long timesteps, we conclude that AOS schemes are simple and efficient compared to these alternatives.We then examine the potential utility of using multiple timestep methods combined with AOS schemes, as means to expedite the diffusion process. These methods were developed for molecular dynamics applications and are used efficiently in biomolecular simulations. The idea is to split the forces exerted on atoms into different classes according to their behavior in time, and assign longer timesteps to nonlocal, slowly-varying forces such as the Coulomb and van der Waals interactions, whereas the local forces like bond and angle are treated with smaller timesteps. Multiple timestep integrators can be derived from the Trotter factorization, a decomposition that bears a strong resemblance to a Strang splitting. Both formulations decompose the time propagator into trilateral products to construct multiplicative operator splittings which are second order in time, with the possibility of extending the factorization to higher order expansions. While a Strang splitting is a decomposition across spatial dimensions, where each dimension is subsequently treated with a fractional step, the multiple timestep method is a decomposition across scales. Thus, multiple timestep methods are a realization of the multiplicative operator splitting idea. For certain nonlinear diffusion coefficients with favorable properties, we show that a simple multiple timestep method can improve the diffusion process.     

Efficient nonlinear solvers for Laplace–Beltrami smoothing of three-dimensional unstructured grids

The Laplace–Beltrami system of nonlinear, elliptic, partial differential equations has utility in the generation of computational grids on complex and highly curved geometry. Discretization of this system using the finite-element method accommodates unstructured grids, but generates a large, sparse, ill-conditioned system of nonlinear discrete equations. The use of the Laplace–Beltrami approach, particularly in large-scale applications, has been limited by the scalability and efficiency of solvers. This paper addresses this limitation by developing two nonlinear solvers based on the Jacobian-Free Newton–Krylov (JFNK) methodology. A key feature of these methods is that the Jacobian is not formed explicitly for use by the underlying linear solver. Iterative linear solvers such as the Generalized Minimal RESidual (GMRES) method do not technically require the stand-alone Jacobian; instead its action on a vector is approximated through two nonlinear function evaluations. The preconditioning required by GMRES is also discussed. Two different preconditioners are developed, both of which employ existing Algebraic Multigrid (AMG) methods. Further, the most efficient preconditioner, overall, for the problems considered is based on a Picard linearization. Numerical examples demonstrate that these solvers are significantly faster than a standard Newton–Krylov approach; a speedup factor of approximately 26 was obtained for the Picard preconditioner on the largest grids studied here. In addition, these JFNK solvers exhibit good algorithmic scaling with increasing grid size.     

High-accuracy finite-difference methods for the valuation of options

A finite-difference scheme often employed for the valuation of options from the Black–Scholes equation is the Crank–Nicolson (CN) scheme. The CN scheme is second order in both time and asset. For a rapid valuation with a reasonable resolution of the option price curve, it requires extremely small steps in both time and asset. In this paper, we present high-accuracy finite-difference methods for the Black–Scholes equation in which we employ the fourth-order L-stable Simpson-type (LSIMP) time integration schemes developed earlier and the well-known Numerov method for discretization in the asset direction. The resulting schemes, called LSIMP–NUM, are fourth order in both time and asset. The LSIMP–NUM schemes obtained can provide a rapid, stable and accurate resolution of option prices, allowing for relatively large steps in both time and asset. We compare the computational efficiency of the LSIMP–NUM schemes with the CN and Douglas schemes by considering valuation of European options and American options via the linear complementarity approach.     

A Family of Fourth-Order and Sixth-Order Compact Difference Schemes for the Three-Dimensional Poisson Equation

In this paper a family of fourth-order and sixth-order compact difference schemes for the three dimensional (3D) linear Poisson equation are derived in detail. By using finite volume (FV) method for derivation, the highest-order compact schemes based on two different types of dual partitions are obtained. Moreover, a new fourth-order compact scheme is gained and numerical experiments show the new scheme is much better than other known fourth-order schemes. The outline for the nonlinear problems are also given. Numerical experiments are conducted to verify the feasibility of this new method and the high accuracy of these fourth-order and sixth-order compact difference scheme.     

欧拉方程的隐式间断有限元算法研究

针对Euler方程,设计了适合间断Galerkin有限元方法的LU-SGS、GMRES以及修正LU-SGS隐式算法。采用Roe通量以及Van Albada限制器技术实现了经典LU-SGS、GMRES算法,引入高阶项误差补偿,发展了修正LU-SGS算法。以NACA0012、RAE2822翼型为例验证分析了算法的可靠性和高效性。结果表明修正LU-SGS算法存储量较少,程序实现方便,而且计算效率是LU-SGS算法的2.5倍以上,接近于循环GMRES算法。     

A rational high-order compact ADI method for unsteady convection–diffusion equations

Based on a fourth-order compact difference formula for the spatial discretization, which is currently proposed for the one-dimensional (1D) steady convection–diffusion problem, and the Crank–Nicolson scheme for the time discretization, a rational high-order compact alternating direction implicit (ADI) method is developed for solving two-dimensional (2D) unsteady convection–diffusion problems. The method is unconditionally stable and second-order accurate in time and fourth-order accurate in space. The resulting scheme in each ADI computation step corresponds to a tridiagonal matrix equation which can be solved by the application of the 1D tridiagonal Thomas algorithm with a considerable saving in computing time. Three examples supporting our theoretical analysis are numerically solved. The present method not only shows higher accuracy and better phase and amplitude error properties than the standard second-order Peaceman–Rachford ADI method in Peaceman and Rachford (1959) [4], the fourth-order ADI method of Karaa and Zhang (2004) [5] and the fourth-order ADI method of Tian and Ge (2007) [23], but also proves more effective than the fourth-order Padé ADI method of You (2006) [6], in the aspect of computational cost. The method proposed for the diffusion–convection problems is easy to implement and can also be used to solve pure diffusion or pure convection problems.     

Hybrid WENO schemes for polydisperse sedimentation models

Polydisperse sedimentation models can be described by a strongly coupled system of conservation laws for the concentration of each species of solids. Typical solutions for the sedimentation model considered for batch settling in a column include stationary kinematic shocks separating layers of sediment of different composition. This phenomenon, known as segregation of species, is a specially demanding task for numerical simulation due to the need of accurate numerical simulations. Very high-order accurate solutions can be constructed by incorporating characteristic information, available due to the hyperbolicity analysis made in Donat and Mulet [A secular equation for the Jacobian matrix of certain multispecies kinematic flow models, Numer. Methods Partial Differential Equations 26 (2010), pp. 159–175.] But characteristic-based schemes, see Bürger et al. [On the implementation of WENO schemes for a class of polydisperse sedimentation models, J. Comput. Phys. 230 (2011), pp. 2322–2344], are very expensive in terms of computational time, since characteristic information is not readily available, and they are not really necessary in constant areas, where a less complex method can obtain similar results. With this idea in mind, in this paper we develop a hybrid finite difference WENO scheme that only uses the characteristic information of the Jacobian matrix of the system in those regions where singularities exist or are starting to develop, while it uses a component-wise approximation of the scheme in smooth regions. We perform some experiments showing the computational gains that can be achieved by this strategy.     

A linearly semi-implicit compact scheme for the Burgers–Huxley equation

In this paper, a linearly semi-implicit compact scheme is developed for the Burgers–Huxley equation. The equation is decomposed into two subproblems, i.e. a Burgers equation and a nonlinear ODE, by the operator splitting technique. The Burgers equation is solved by a linearly self-starting compact scheme which is fourth-order accurate in space and second-order accurate in time. The nonlinear ODE is discretized by a third-order semi-implicit Runge–Kutta method, which possesses good numerical stability with low computational cost. The numerical experiments show that the scheme provides the expected convergence order. Finally, several experiments are conducted to simulate the solutions of the Burgers–Huxley equation to validate our numerical method.     

High-order time stepping Fourier spectral method for multi-dimensional space-fractional reaction–diffusion equations

This paper introduces a high-order time stepping scheme, that is based on using Fourier spectral in space and a fourth-order diagonal Padé approximation to the matrix exponential function for solving multi-dimensional space-fractional reaction–diffusion equations. The resulting time stepping scheme is developed based on an exponential time differencing approach such that it alleviates solving a large non-linear system at each time step while maintaining the stability of the scheme. The non-locality of the fractional operator in some other numerical schemes for these equations leads to full and dense matrices. This scheme is able to overcome such computational inefficiency due to the full diagonal representation of the fractional operator. It also attains spectral convergence for multiple spatial dimensions. The stability of the scheme is discussed through the investigation of the amplification symbol and plotting its stability regions, which provides an indication of the stability of the method. The convergence analysis is performed empirically to show that the scheme is fourth-order accurate in time, as expected. Numerical experiments on reaction–diffusion systems with application to pattern formation are discussed to show the effect of the fractional order in space-fractional reaction–diffusion equations and to validate the effectiveness of the scheme.     

Hopscotch procedures for a fourth-order parabolic partial differential equation differential equation

In a recent paper (McKee, 1975) the Hopscotch method was applied to solve the fourth-order parabolic (beam) equation. Several computational schemes were discussed which prove to be conditionally stable with the stability range no better than that of the usual explicit scheme.By using two different nets in this paper, the Hopscotch algorithm is applied to the decomposed form of the equation (Richtmyer, 1959) and shown to provide a stable computational scheme.     

High Order Fluctuation Schemes on Triangular Meshes

We develop a new class of schemes for the numerical solution of first-order steady conservation laws. The schemes are of the residual distribution, or fluctuation-splitting type. These schemes have mostly been developed in the context of triangular or tetrahedral elements whose degrees of freedom are their nodal values. We work here with more general elements that allow high-order accuracy. We introduce, for an arbitrary number of degrees of freedom, a simple mapping from a low-order monotone scheme to a monotone scheme that is as accurate as the degrees of freedom will allow. Proofs of consistency, convergence and accuracy are presented, and numerical examples from second, third and fourth-order schemes.     

Matrix-free aerostructural optimization of aircraft wings

In structural optimization subject to failure constraints, computing the gradients of a large number of functions with respect to a large number of design variables may not be computationally practical. Often, the number of constraints in these optimization problems is reduced using constraint aggregation at the expense of a higher mass of the optimal structural design. This work presents results of structural and coupled aerodynamic and structural design optimization of aircraft wings using a novel matrix-free augmented Lagrangian optimizer. By using a matrix-free optimizer, the computation of the full constraint Jacobian at each iteration is replaced by the computation of a small number of Jacobian-vector products. The low cost of the Jacobian-vector products allows optimization problems with thousands of failure constraints to be solved directly, mitigating the effects of constraint aggregation. The results indicate that the matrix-free optimizer reduces the computational work of solving the optimization problem by an order of magnitude compared to a traditional sequential quadratic programming optimizer. Furthermore, the use of a matrix-free optimizer makes the solution of large multidisciplinary design problems, in which gradient information must be obtained through iterative methods, computationally tractable.