A fast implementation algorithm of TV inpainting model based on operator splitting method

In this paper, we propose a fast algorithm to solve the well known total variation (TV) inpainting model. Classically, the Euler-Lagrange equation deduced from TV inpainting model is solved by the gradient descent method and discretized by an explicit scheme, which produces a slow inpainting process. Sometimes an implicit scheme is also used to tackle the problem. Although the implicit scheme is several times faster than the explicit one, it is still too slow in many practical applications. In this paper, we propose to use an operator splitting method by adding new variables in the Euler-Lagrange equation of TV inpainting model such that the equation is split into a few very simple subproblems. Then we solve these subproblems by an alternate iteration. Numerically, the proposed algorithm is very easy to implement. In the numerical experiments, we mainly compare our algorithm with the existing implicit TV inpainting algorithms. It is shown that our algorithm is about ten to twenty times faster than the implicit TV inpainting algorithms with similar inpainting quality. The comparison of our algorithm with harmonic inpainting algorithm also shows some advantages and disadvantages of the TV inpainting model.     

Third-order temporal discrete scheme for the non-stationary Navier–Stokes equations

In this article, we suggest a new third-order time discrete scheme for the two-dimensional non-stationary Navier–Stokes equations. After presenting the Galerkin finite element approximation for the spatial discretization, we consider an implicit/explicit time discrete scheme for the problem, which is based on the two-step Adams–Moulton scheme (implicit scheme) for the linear term and the three-step Adams–Bashforth scheme (explicit scheme) for the nonlinear term. In this method, we only need to solve a linearized discrete system at each time step, so the scheme can converge fast and the computational cost can be reduced. Moreover, under some assumptions, we deduce the stability and optimal error estimate for the velocity in L ²-norm.     

Interpolating Runge-Kutta methods for vanishing delay differential equations

In the numerical solution of delay differential equations by a continuous explicit Runge-Kutta method a difficulty arises when the delay vanishes or becomes smaller than the stepsize the method would like to use. In this situation the standard explicit sequential process of computing the Runge-Kutta stages becomes an implicit process and an iteration scheme must be adopted. We will consider alternative iteration schemes and investigate their order.     

Locally Implicit Time Integration Strategies in a Discontinuous Galerkin Method for Maxwell’s Equations

An attractive feature of discontinuous Galerkin (DG) spatial discretization is the possibility of using locally refined space grids to handle geometrical details. However, locally refined meshes lead to severe stability constraints on explicit integration methods to numerically solve a time-dependent partial differential equation. If the region of refinement is small relative to the computational domain, the time step size restriction can be overcome by blending an implicit and an explicit scheme where only the solution variables living at fine elements are treated implicitly. The downside of this approach is having to solve a linear system per time step. But due to the assumed small region of refinement relative to the computational domain, the overhead will also be small while the solution can be advanced in time with step sizes determined by the coarse elements. In this paper, we present two locally implicit time integration methods for solving the time-domain Maxwell equations spatially discretized with a DG method. Numerical experiments for two-dimensional problems illustrate the theory and the usefulness of the implicit–explicit approaches in presence of local refinements.     

Gauss–Newton Multilevel Methods for Least-Squares Finite Element Computations of Variably Saturated Subsurface Flow

We apply the least-squares mixed finite element framework to the nonlinear elliptic problems arising in each time-step of an implicit Euler discretization for variably saturated flow. This approach allows the combination of standard piecewise linear H ¹-conforming finite elements for the hydraulic potential with the H(div)-conforming Raviart–Thomas spaces for the flux. It also provides an a posteriori error estimator which may be used in an adaptive mesh refinement strategy. The resulting nonlinear algebraic least-squares problems are solved by an inexact Gauss–Newton method using a stopping criterion for the inner iteration which is based on the change of the linearized least-squares functional relative to the nonlinear least-squares functional. The inner iteration is carried out using an adaptive multilevel method with a block Gauss–Seidel smoothing iteration. For a realistic water table recharge problem, the results of computational experiments are presented. Received January 4, 1999; revised July 19, 1999     

Time Stepping Via One-Dimensional Padé Approximation

The numerical solution of time-dependent ordinary and partial differential equations presents a number of well known difficulties—including, possibly, severe restrictions on time-step sizes for stability in explicit procedures, as well as need for solution of challenging, generally nonlinear systems of equations in implicit schemes. In this note we introduce a novel class of explicit methods based on use of one-dimensional Padé approximation. These schemes, which are as simple and inexpensive per time-step as other explicit algorithms, possess, in many cases, properties of stability similar to those offered by implicit approaches. We demonstrate the character of our schemes through application to notoriously stiff systems of ODEs and PDEs. In a number of important cases, use of these algorithms has resulted in orders-of-magnitude reductions in computing times over those required by leading approaches.     

A non-stiff boundary integral method for 3D porous media flow with surface tension

We present an efficient, non-stiff boundary integral method for 3D porous media flow with surface tension. Surface tension introduces high order (i.e., high derivative) terms into the evolution equations, and this leads to severe stability constraints for explicit time-integration methods. Furthermore, the high order terms appear in non-local operators, making the application of implicit methods difficult. Our method uses the fundamental coefficients of the surface as dynamical variables, and employs a special isothermal parameterization of the interface which enables efficient application of implicit or linear propagator time-integration methods via a small-scale decomposition. The method is tested by computing the relaxation of an interface to a flat surface under the action of surface tension. These calculations employ an approximate interface velocity to test the stiffness reduction of the method. The approximate velocity has the same mathematical form as the exact velocity, but avoids the numerically intensive computation of the full Birkhoff–Rott integral. The algorithm is found to be effective at eliminating the severe time-step constraint that plagues explicit time-integration methods.     

Ein implizites Charakteristikenverfahren zur Lösung von Anfangsrandwertaufgaben bei hyperbolischen Systemen und seine Konvergenz

We present an implicit method of characteristics for the solution of systems of quasilinear hyperbolic differential equations with two independent variables. The computation of the variables is done in a rectangular grid and is not bound by Courants conditions, which means no limitation of time-step. It was possible to give a rather elementary proof of convergence. The method is already applied to the computation of flood waves in rivers with great success.     

Adaptive finite differences and IMEX time-stepping to price options under Bates model

In this paper, we consider numerical pricing of European and American options under the Bates model, a model which gives rise to a partial-integro differential equation. This equation is discretized in space using adaptive finite differences while an IMEX scheme is employed in time. The sparse linear systems of equations in each time-step are solved using an LU-decomposition and an operator splitting technique is employed for the linear complementarity problems arising for American options. The integral part of the equation is treated explicitly in time which means that we have to perform matrix-vector multiplications each time-step with a matrix with dense blocks. These multiplications are accomplished through fast Fourier transforms. The great performance of the method is demonstrated through numerical experiments.     

The Navier–Stokes-αβ equations as a platform for a spectral multigrid method to solve the Navier–Stokes equations

This paper describes a spectral multigrid method for spatially periodic homogeneous and isotropic turbulent flows. The method uses the Navier–Stokes-αβ equations to accelerate convergence toward solutions of the Navier–Stokes equations. The Navier–Stokes-αβ equations are solved on coarse grids at various levels and the Navier–Stokes equations are solved on the “nest grid”. The method uses Crank–Nicolson time-stepping for the viscous terms, explicit time-stepping for the remaining terms, and Richardson iteration to solve linear systems encountered at each time step and on each grid level. To explore the computational efficiency of the method, comparisons are made with results obtained from an analogous spectral multigrid method for the Navier–Stokes equations. These comparisons are based on computing work units and residuals for multigrid cycles. Most importantly, we examine how choosing different values of the length scales α and β entering the Navier–Stokes-αβ equations influence the efficiency and accuracy of these multigrid schemes.     

A new operator splitting method for the numerical solution of partial differential equations II

We extend the applications of a new method for splitting operators in partial differential equations introduced by us (A. Rouhi and J. Wright, A new operator splitting method for the numerical solution of partial differential equations, Comput. Phys. Commun. 85 (1995) 18–28, and Spectral implementation of a new operator splitting method for solving partial differential equations, Comput. Phys. (1995), to be published.) to equations in two spatial dimensions, and show how the method allows the use of explicit time stepping methods in some instances when other methods require implicit time stepping. This odd-even splitting method also enables one to increase the order of accuracy of time stepping in a straightforward manner. Our main examples will be the two-dimensional Navier-Stokes equations and the shallow water equations. In the first example we show how the pressure term can be dealt with in simple geometries. We will then discuss the treatment of the diffusion term. Next we will discuss how fast waves can be treated by explicit methods using the odd-even splitting, while retaining all stability and accuracy advantages of usual implicit methods. Our example here will be the shallow water equations in two dimensions.     

Concepts and Application of Time-Limiters to High Resolution Schemes

A new class of implicit high-order non-oscillatory time integration schemes is introduced in a method-of-lines framework. These schemes can be used in conjunction with an appropriate spatial discretization scheme for the numerical solution of time dependent conservation equations. The main concept behind these schemes is that the order of accuracy in time is dropped locally in regions where the time evolution of the solution is not smooth. By doing this, an attempt is made at locally satisfying monotonicity conditions, while maintaining a high order of accuracy in most of the solution domain. When a linear high order time integration scheme is used along with a high order spatial discretization, enforcement of monotonicity imposes severe time-step restrictions. We propose to apply limiters to these time-integration schemes, thus making them non-linear. When these new schemes are used with high order spatial discretizations, solutions remain non-oscillatory for much larger time-steps as compared to linear time integration schemes. Numerical results obtained on scalar conservation equations and systems of conservation equations are highly promising.     

Adaptive and nonadaptive Hermitian operator methods for combustion phenomena

Adaptive and nonadaptive, three-point, fourth-order accurate, compact or Hermitian operator methods are developed and used to study one-dimensional combustion phenomena. The nonadaptive Hermitian operator methods are based on the time linearization of the nonlinear partial differential equations, and employ an approximate factorization technique to reduce a three-dimensional reaction-diffusion operator to a sequence of three one-dimensional, linear, second-order differential operators in space. The three adaptive Hermitian operator techniques presented in this paper are based on the equidistribution of the arc length of the vector of dependent variables and use a subequidistribution principle to obtain smooth grids. The first adaptive technique uses quasilinearization and yields a block tridiagonal matrix for the values of the dependent variables at each iteration. The second technique employs partial quasilinearization and yields a system of uncoupled, linear algebraic equations for each dependent variable at each iteration. The third technique employs a predictor-corrector method to predict the grid point locations and a time linearization procedure to obtain the values of the dependent variables. It is shown that the efficiency and accuracy of adaptive Hermitian operator methods depend on the time step and number of grid points used in the calculations. It is also shown that adaptive methods which use a Crank-Nicolson scheme in time may yield oscillatory solutions, and that nonadaptive Hermitian operator methods require a much larger number of grid points than nonadaptive techniques if the solution of the governing equations is characterized by fast ignition phenomena and/or steep, fast moving flame fronts.     

Approximation of the Crank-Nicholson method by the iterated dynamic-theta method

Choptuik's iterated Crank-Nicholson method has become a popular algorithm for solving partial differential equations in computational physics. We generalize Choptuik's explicit iteration approach to implicit finite difference schemes, by the introduction of a novel method with an iteration step dependent parameter and analyze its stability and computational efficiency.     

三维Euler方程的隐式间断有限元算法

为了求解三维欧拉方程,对隐式时间离散格式间断有限元方法进行了研究。根据间断Galerkin有限元方法思想,构造内迭代SOR-LU-SGS隐式时间离散格式,结合当地时间步长技术、多重网格方法,实现了三维流场的计算。数值计算了ONERAM6机翼、大攻角尖前缘三角翼以及DLR-F4翼身组合体的亚声速绕流问题。结果表明,加入SOR内迭代步的LU-SGS隐式算法具有较大的优势,相较于GMRES算法所占用的内存少且收敛速度相当,是LU-SGS算法的三倍以上。针对三维算例,具有较好的稳定性和较高的收敛速度,能够给出准确的流场信息。与原方法相比,SOR-LU-SGS方法无论是在迭代步数上还是在CPU时间上,效率均有明显提高,适合于三维复杂流场计算。     

基于IMEX的织物动态仿真的近似解法

织物在空间运动的刚性特征始终是困扰织物动态仿真的难题．显式方法简单灵活，易于实现，但受稳定因素影响，无法实现具有刚性特征的织物动态模拟；隐式方法稳定性好，却忽略了非线性因素，而且计算复杂，直接影响到仿真的最终结果和实际效率．针对这一问题，提出了基于隐式一显式的近似解法，该方案从系统受力形变的非线性特征出发，将质点受力分为线性和非线性两部分，线性部分采用隐式解法，非线性部分利用显式解法，线性方程组的求解则运用近似解法．实验结果表明，该方法兼具两种方法的优点，既保留了隐式方法的稳定性，又充分利用了显式方法的简易性处理非线性特征，从而从真正意义上解决织物仿真中的刚性问题．     

Relaxation method for unsteady convection–diffusion equations

We propose and implement a relaxation method for solving unsteady linear and nonlinear convection–diffusion equations with continuous or discontinuity-like initial conditions. The method transforms a convection–diffusion equation into a relaxation system, which contains a stiff source term. The resulting relaxation system is then solved by a third-order accurate implicit–explicit (IMEX) Runge–Kutta method in time and a fifth-order finite difference WENO scheme in space. Numerical results show that the method can be used to effectively solve convection–diffusion equations with both smooth structures and discontinuities.     

Partitioned but strongly coupled iteration schemes for nonlinear fluid–structure interaction

We look at the computational procedure of computing the response of a coupled fluid–structure interaction problem. We use the so-called strong fluid–structure coupling––a totally implicit formulation. At each time step in an implicit formulation, new values for the solution variables have to be computed by solving a nonlinear system of equations, where we assume that we have solvers for the subproblems. This is often the case, when we have existing software to solve each subproblem separately, and want to couple both. We show how to solve the overall nonlinear system by using only the solvers for the subproblems. This is achieved not by considering the equilibrium equations, but the fixed-point problem resulting from the solution iteration for each of the subproblems.     

Embedded implicit Runge–Kutta Nyström method for solving second-order differential equations

An embedded diagonally implicit Runge–Kutta Nyström (RKN) method is constructed for the integration of initial-value problems for second-order ordinary differential equations possessing oscillatory solutions. This embedded method is derived using a three-stage diagonally implicit RKN method of order four within which a third-order three stage diagonally implicit RKN method is embedded. We demonstrate how this system can be solved, and by an appropriate choice of free parameters, we obtain an optimized RKN(4,3) embedded algorithm. We also examine the intervals of stability and show that the method is strongly stable within an appropriate region of stability and is thus suitable for oscillatory problems by applying the method to the test equation y″=?ω² y, ω>0. Necessary and sufficient conditions are given for this method to possess non-vanishing intervals of periodicity, for the fourth-order method. Finally, we present the coefficients of the method optimized for small truncation errors. This new scheme is likely to be efficient for the numerical integration of second-order differential equations with periodic solutions, using adaptive step size.