An interpretation and derivation of the lattice Boltzmann method using Strang splitting

The lattice Boltzmann space/time discretisation, as usually derived from integration along characteristics, is shown to correspond to a Strang splitting between decoupled streaming and collision steps. Strang splitting offers a second-order accurate approximation to evolution under the combination of two non-commuting operators, here identified with the streaming and collision terms in the discrete Boltzmann partial differential equation. Strang splitting achieves second-order accuracy through a symmetric decomposition in which one operator is applied twice for half timesteps, and the other operator is applied once for a full timestep. We show that a natural definition of a half timestep of collisions leads to the same change of variables that was previously introduced using different reasoning to obtain a second-order accurate and explicit scheme from an integration of the discrete Boltzmann equation along characteristics. This approach extends easily to include general matrix collision operators, and also body forces. Finally, we show that the validity of the lattice Boltzmann discretisation for grid-scale Reynolds numbers larger than unity depends crucially on the use of a Crank–Nicolson approximation to discretise the collision operator. Replacing this approximation with the readily available exact solution for collisions uncoupled from streaming leads to a scheme that becomes much too diffusive, due to the splitting error, unless the grid-scale Reynolds number remains well below unity.     

On Semi-implicit Splitting Schemes for the Beltrami Color Image Filtering

The Beltrami flow is an efficient nonlinear filter, that was shown to be effective for color image processing. The corresponding anisotropic diffusion operator strongly couples the spectral components. Usually, this flow is implemented by explicit schemes, that are stable only for very small time steps and therefore require many iterations. In this paper we introduce a semi-implicit Crank-Nicolson scheme based on locally one-dimensional (LOD)/additive operator splitting (AOS) for implementing the anisotropic Beltrami operator. The mixed spatial derivatives are treated explicitly, while the non-mixed derivatives are approximated in an implicit manner. In case of constant coefficients, the LOD splitting scheme is proven to be unconditionally stable. Numerical experiments indicate that the proposed scheme is also stable in more general settings. Stability, accuracy, and efficiency of the splitting schemes are tested in applications such as the Beltrami-based scale-space, Beltrami denoising and Beltrami deblurring. In order to further accelerate the convergence of the numerical scheme, the reduced rank extrapolation (RRE) vector extrapolation technique is employed.     

平均曲率运动的三种实现方案的比较研究

讨论了曲率运动演化方程的三种数值方案:离散中值滤波方案、显式水平集方案和半隐式水平集方案的原理与算法,并对它们的效率、精度以及旋转不变性等性能进行了对比实验研究.结果表明,半隐式加性算子分裂(AOS)算法相对于另两种方案性能上明显占优.     

Image Segmentation Using Some Piecewise Constant Level Set Methods with MBO Type of Projection

In this work, we are trying to propose fast algorithms for Mumford-Shah image segmentation using some recently proposed piecewise constant level set methods (PCLSM). Two variants of the PCLSM will be considered in this work. The first variant, which we call the binary level set method, needs a level set function which only takes values ±1 to identify the regions. The second variant only needs to use one piecewise constant level set function to identify arbitrary number of regions. For the Mumford-Shah image segmentation model with these new level set methods, one needs to minimize some smooth energy functionals under some constrains. A penalty method will be used to deal with the constraint. AOS (additive operator splitting) and MOS (multiplicative operator splitting) schemes will be used to solve the Euler-Lagrange equations for the minimization problems. By doing this, we obtain some algorithms which are essentially applying the MBO scheme for our segmentation models. Advantages and disadvantages are discussed for the proposed schemes. We acknowledge support from the Norwegian Research Council and IMS of the National University of Singapore.     

Application of Discontinuous Galerkin Methods for Reaction-Diffusion Systems in Developmental Biology

Nonlinear reaction-diffusion systems which are often employed in mathematical modeling in developmental biology are usually highly stiff in both diffusion and reaction terms. Moreover, they are typically considered on multidimensional complex geometrical domains because of complex shapes of embryos. We overcome these computational challenges by combining discontinuous Galerkin (DG) finite element methods with Strang type symmetrical operator splitting technique, on triangular meshes. This allows us to avoid directly solving a coupled nonlinear system, as is necessary with the standard implicit schemes. Numerical solutions of two reaction-diffusion systems, the well-studied Schnakenberg model, which has been applied to several problems in developmental biology, and a new biologically based system for skeletal pattern formation in the vertebrate limb, are presented to demonstrate effects of various domain geometries on the resulting biological patterns.     

On combination of first order Strang's splitting and additive splitting for the solution of multi-dimensional convection diffusion problem

In this article we present a new splitting approach for the numerical solution of the multi-dimensional convection diffusion equations. The method combines additive and multiplicative splitting. In particular the method combines first order Strang's splitting, multiplicative splitting defined for splitting the convection and diffusion equation, and additive splitting defined in accordance with the spatial variables. The method not only reduces the linear (or nonlinear) original problem into a series of one-dimensional and one physical operator linear problems, but also enables us to compute these one-dimensional problems using parallel processors. The accuracy and stability of the new algorithm are investigated through the solution of different multi-dimensional convection diffusion model problems with scalar coefficients.     

Coherence-Enhancing Diffusion Filtering

The completion of interrupted lines or the enhancement of flow-like structures is a challenging task in computer vision, human vision, and image processing. We address this problem by presenting a multiscale method in which a nonlinear diffusion filter is steered by the so-called interest operator (second-moment matrix, structure tensor). An m-dimensional formulation of this method is analysed with respect to its well-posedness and scale-space properties. An efficient scheme is presented which uses a stabilization by a semi-implicit additive operator splitting (AOS), and the scale-space behaviour of this method is illustrated by applying it to both 2-D and 3-D images.     

基于迭代重加权的非刚性图像配准

非刚性图像配准问题是当今重要的研究课题. 本文提出一类基于能量最小化方法的非刚性图像配准模型, 其中包括单模态和多模态两个模型. 在单模态模型中,正则项采用迭代重加权的L2范数度量, 一方面克服了迭代收敛不同步的问题, 另一方面使新模型既能保持图像的边缘几何结构, 又能避免块效应的产生. 在多模态模型中, 不同模态的图像被转化为同一模态进行处理, 提高了配准的效率. 在模型求解方面, 利用算子分裂和交替最小化的方法, 将原问题转化为阈值和加性算子分裂的迭代格式进行求解. 数值实验表明, 本文的方法对含噪以及变形较大的图像都能实现较好的配准.     

Further results on regular splittings and multisplittings

In this article a detailed study of the regularity of induced splitting from the two-stage and multisplitting iterative methods is made. We present sufficient conditions which guarantee that the induced splitting is still a regular one. Meanwhile, we have established two new comparison theorems for the induced splittings characterized by a monotone matrix. In addition, we have also applied these theorems to some concrete methods.     

Implicit–explicit Runge–Kutta methods applied to atmospheric chemistry-transport modelling

Chemistry-transport calculations are highly stiff in terms of time-stepping. Because explicit ODE solvers require numerous short time steps in order to maintain stability, it seems that especially sparse implicit–explicit solvers are suited to improve the numerical efficiency for atmospheric chemistry applications. In the new version of our mesoscale chemistry-transport model MUSCAT [Knoth, O., Wolke, R., 1998a. An explicit–implicit numerical approach for atmospheric chemistry–transport modelling. Atmospheric Environment 32, 1785–1797.], implicit–explicit (IMEX) time integration schemes are implemented. Explicit second order Runge–Kutta methods for the integration of the horizontal advection are used. The stiff chemistry and all vertical transport processes (turbulent diffusion, advection, deposition) are integrated in an implicit and coupled manner utilizing the second order BDF method. The horizontal fluxes are treated as ‘artificial’ sources within the implicit integration. A change of the solution values as in conventional operator splitting is thus avoided.The aim of this paper is to investigate the interaction between the explicit Runge–Kutta scheme and the implicit integrator. The numerical behavior is discussed for a 1D test problem and 3D chemistry-transport simulations. The efficiency and accuracy of the algorithm are compared to results obtained using the Strang splitting approach. The numerical experiments indicate that our second order implicit–explicit Runge–Kutta methods are a valuable alternative to the conventional operator splitting approach for integrating atmospheric chemistry-transport-models. In mesoscale applications and in cases with stronger accuracy requirements the ‘source splitting’ approach shows a better performance than Strang splitting.     

Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method

We have studied previously a generalized conjugate gradient method for solving sparse positive-definite systems of linear equations arising from the discretization of elliptic partial-differential boundary-value problems. Here, extensions to the nonlinear case are considered. We split the original discretized operator into the sum of two operators, one of which corresponds to a more easily solvable system of equations, and accelerate the associated iteration based on this splitting by (nonlinear) conjugate gradients. The behavior of the method is illustrated for the minimal surface equation with splittings corresponding to nonlinear SSOR, to approximate factorization of the Jacobian matrix, and to elliptic operators suitable for use with fast direct methods. The results of numerical experiments are given as well for a mildy nonlinear example, for which, in the corresponding linear case, the finite termination property of the conjugate gradient algorithm is crucial.     

小波域上图像非线性扩散滤波

提出一个小波域上图像扩散滤波恢复新模型。主要思想是把原图像作为最精细尺度下的小波子带，根据噪声分布的特点，导出保护较大尺度下信息的泛函模型代替小波阈值除噪，对泛函求变分得：Euler-Lagrange方程。新的滤波方法能避免小波阈值除噪的伪Gibbs现象，改进了同类型非线性扩散方程滤波的效果。利用可加算子分裂(AOS)格式求非线性扩散方程的数值解。实例的数值计算说明对图像滤波和保护边缘的有效性。     

On splitting-based numerical methods for nonlinear models of European options

We present a large class of nonlinear models of European options as parabolic equations with quasi-linear diffusion and fully nonlinear hyperbolic part. The main idea of the operator splitting method (OSM) is to couple known difference schemes for nonlinear hyperbolic equations with other ones for quasi-linear parabolic equations. We use flux limiter techniques, explicit–implicit difference schemes, Richardson extrapolation, etc. Theoretical analysis for illiquid market model is given. The numerical experiments show second-order accuracy for the numerical solution (the price) and Greeks Delta and Gamma, positivity and monotonicity preserving properties of the approximations.     

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.     

Globalized matrix-explicit Newton-GMRES for the high-order accurate solution of the Euler equations

Implicit methods for finite-volume schemes on unstructured grids typically rely on a matrix-free implementation of GMRES and an explicit first-order accurate Jacobian for preconditioning. Globalization is typically achieved using a global timestep or a CFL based local timestep. We show that robustness of the globalization can be improved by supplementing the pseudo-timestepping method commonly used with a line search method. The number of timesteps required for convergence can be reduced by using a timestep that scales with the local residual. We also show that it is possible to form the high-order Jacobian explicitly at a reasonable computational cost. This is demonstrated for cases using both limited and unlimited reconstruction. This exact Jacobian can be used for preconditioning and directly in the GMRES method. The benefits of improvements in preconditioning and the elimination of residual evaluations in the inner iterations of the matrix-free GMRES method are substantial. Computational results focus on second- and fourth-order accurate schemes with some results for the third-order scheme. Overall computational cost for the matrix-explicit method is lower than the matrix-free method for all cases. The fourth-order matrix-explicit scheme is a factor of 1.6-3 faster than the matrix-free scheme while requiring about 50-100% more memory.     

DCT- and DST-based splitting methods for Toeplitz systems

New splitting iterative methods for Toeplitz systems are proposed by means of recently developed matrix splittings based on discrete sine and cosine transforms due to Kailath and Olshevsky [Displacement structure approach to discrete-trigonometric transform-based preconditioners of G. Strang type and of T. Chan type, SIAM J. Matrix Anal. Appl. 26 (2005), pp. 706–734]. Theoretical analysis shows that new splitting iterative methods converge to the unique solution of a symmetric Toeplitz linear system. Moreover, an upper bound of the contraction factor of our new splitting iterations is derived. Numerical examples are reported to illustrate the effectiveness of new splitting iterative methods.     

A mollification based operator splitting method for convection diffusion equations

The main goal of this paper is to show that discrete mollification is a suitable ingredient in operator splitting methods for the numerical solution of nonlinear convection–diffusion equations. In order to achieve this goal, we substitute the second step of the operator splitting method of Karlsen and Risebro (1997) [1] for a mollification step and prove that the convergence features are fairly well preserved. We end the paper with illustrative numerical experiments.     

An overview and generalization of implicit Navier–Stokes algorithms and approximate factorization

A theme of linearization and approximate factorization provides the context for a retrospective overview of the development and evolution of implicit numerical methods for the compressible and incompressible Euler and Navier–Stokes algorithms. This topic was chosen for this special volume commemorating the recent retirements of R.M. Beam and R.F. Warming. A generalized treatment of approximate factorization schemes is given, based on an operator notation for the spatial approximation. The generalization focuses on the implicit structure of Euler and Navier–Stokes algorithms as nonlinear systems of partial differential equations, with details of the spatial approximation left to operator definitions. This provides a unified context for discussing noniterative and iterative time-linearized schemes, and Newton iteration for unsteady nonlinear schemes. The factorizations include alternating direction implicit, LU and line relaxation schemes with either upwind or centered spatial approximations for both compressible and incompressible flows. The noniterative schemes are best suited for steady flows, while the iterative schemes are well suited for either steady or unsteady flows. This generalization serves to unify a large number of schemes developed over the past 30 years.     

The induced linguistic continuous ordered weighted geometric operator and its application to group decision making

In this paper, based on the induced linguistic ordered weighted geometric (ILOWG) operator and the linguistic continuous ordered weighted geometric (LCOWG) operator, we develop the induced linguistic continuous ordered weighted geometric (ILCOWG) operator, which is very suitable for group decision making (GDM) problems taking the form of uncertain multiplicative linguistic preference relations. We also present the consistency of uncertain multiplicative linguistic preference relation and study some properties of the ILCOWG operator. Then we propose the relative consensus degree ILCOWG (RCD-ILCOWG) operator, which can be used as the order-inducing variable to induce the ordering of the arguments before aggregation. In order to determine the weights of experts in group decision making (GDM), we define a new distance measure based on the LCOWG operator and develop a nonlinear model on the basis of the criterion of minimizing the distance of the uncertain multiplicative linguistic preference relations. Finally, we analyze the applicability of the new approach in a financial GDM problem concerning the selection of investments.     

Lod generalized trapezoidal formula schemes for parabolic differential equations in two space dimensions

We describe locally one-dimensional (LOD) time integration schemes for parabolic differential equations in two space dimensions, based on the generalized trapezoidal formulas (GTF(α)). We describe the schemes for the diffusion equation with Dirichlet and Neumann boundary conditions, for nonlinear reaction-diffusion equations, and for the convection-diffusion equation in two space dimensions. The obtained schemes are second order in time and unconditionally stable for all α ∈ [0, 1]. Numerical experiments are given to illustrate the obtained schemes and to compare their performance with the better known LOD Crank-Nicolson scheme. While the LOD Crank-Nicolson scheme can give unwanted oscillations in the computed solution, our present LOD-GTF(α) schemes provide both stable and accurate approximations for the true solution.