Higher order operator splitting methods via Zassenhaus product formula: Theory and applications

In this paper, we contribute higher order operator splitting methods improved by Zassenhaus product. We apply the contribution to classical and iterative splitting methods. The underlying analysis to obtain higher order operator splitting methods is presented. While applying the methods to partial differential equations, the benefits of balancing time and spatial scales are discussed to accelerate the methods.The verification of the improved splitting methods are done with numerical examples. An individual handling of each operator with adapted standard higher order time-integrators is discussed. Finally, we conclude the higher order operator splitting methods.     

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.     

基于全局性分裂算子的进化K-means算法

进化算法可以有效地克服K means对初始聚类中心敏感的缺陷,提高了聚类性能。在进化K means聚类算法 (F-EAC)的基础上,针对其变异操作——簇分裂算子的随机性与局部性,提出了两个全局性分裂算子。结合最大最小距离的思想,利用待分裂簇的周边簇信息来指导簇分裂初始点的选择,使簇的分裂更有利于全局划分,以进一步提高进化聚类的有效性。实验结果表明,基于全局性分裂算子的算法在类数发现及聚类精度方面均优于F EAC。     

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.     

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.     

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.     

An operator splitting-radial basis function method for the solution of transient nonlinear Poisson problems

This paper presents an operator splitting-radial basis function (OS-RBF) method as a generic solution procedure for transient nonlinear Poisson problems by combining the concepts of operator splitting, radial basis function interpolation, particular solutions, and the method of fundamental solutions. The application of the operator splitting permits the isolation of the nonlinear part of the equation that is solved by explicit Adams-Bashforth time marching for half the time step. This leaves a nonhomogeneous, modified Helmholtz type of differential equation for the elliptic part of the operator to be solved at each time step. The resulting equation is solved by an approximate particular solution and by using the method of fundamental solution for the fitting of the boundary conditions. Radial basis functions are used to construct approximate particular solutions, and a grid-free, dimension-independent method with high computational efficiency is obtained. This method is demonstrated for some prototypical nonlinear Poisson problems in heat and mass transfer and for a problem of transient convection with diffusion. The results obtained by the OS-RBF method compare very well with those obtained by other traditional techniques that are computationally more expensive. The new OS-RBF method is useful for both general (irregular) two- and three-dimensional geometry and provides a mesh-free technique with many mathematical flexibilities, and can be used in a variety of engineering applications.     

Splitting Methods for Three-Dimensional Transport Models with Interaction Terms

We investigate the use of splitting methods for the numerical integration of three-dimensional transport-chemistry models. In particular, we investigate various possibilities for the time discretization that can take advantage of the parallelization and vectorization facilities offered by multi-processor vector computers. To suppress wiggles in the numerical solution, we use third-order, upwind-biased discretization of the advection terms, resulting in a five-point coupling in each direction. As an alternative to the usual splitting functions, such as co-ordinate splitting or operator splitting, we consider a splitting function that is based on a three-coloured hopscotch-type splitting in the horizontal direction, whereas full coupling is retained in the vertical direction. Advantages of this splitting function are the easy application of domain decomposition techniques and unconditional stability in the vertical, which is an important property for transport in shallow water. The splitting method is obtained by combining the hopscotch-type splitting function with various second-order splitting formulae from the literature. Although some of the resulting methods are highly accurate, their stability behaviour (due to horizontal advection) is quite poor. Therefore we also discuss several new splitting formulae with the aim to improve the stability characteristics. It turns out that this is possible indeed, but the price to pay is a reduction of the accuracy. Therefore, such methods are to be preferred if accuracy is less crucial than stability; such a situation is frequently encountered in solving transport problems. As part of the project TRUST (Transport and Reactions Unified by Splitting Techniques), preliminary versions of the schemes are implemented on the Cray C98 4256 computer and are available for benchmarking.     

磁共振图像的原始-对偶近似迭代重建算法

基于压缩感知（CS）的磁共振成像（MRI）是一种利用磁共振（MR）图像的稀疏性的快速成像技术,经典CS-MRI重建数学模型是在包含线性合成非平滑正则约束下的最优化问题。针对重建模型中的线性合成正则项提出利用原始-对偶框架同时求解原始-对偶问题,对原始-对偶问题的增广Lagrangian形式求解其最优解,提出了一种原始-对偶迭代重建算法;对于非平滑正则项的处理,提出使用Moreau包络进行平滑近似,然后利用近似算子得到平滑近似函数的导数形式。用体模图像和真实MR图像,与共轭梯度算法（CG）、算子分离算法（TVCMRI）、变量分离算法（RecPF）和快速混合分离算法（FCSA）进行比较,表明该算法重建效果最好,算法复杂度与最快的FCSA算法相当。     

Operator Splittings,Bregman Methods and Frame Shrinkage in Image Processing

We examine the underlying structure of popular algorithms for variational methods used in image processing. We focus here on operator splittings and Bregman methods based on a unified approach via fixed point iterations and averaged operators. In particular, the recently proposed alternating split Bregman method can be interpreted from different points of view—as a Bregman, as an augmented Lagrangian and as a Douglas-Rachford splitting algorithm which is a classical operator splitting method. We also study similarities between this method and the forward-backward splitting method when applied to two frequently used models for image denoising which employ a Besov-norm and a total variation regularization term, respectively. In the first setting, we show that for a discretization based on Parseval frames the gradient descent reprojection and the alternating split Bregman algorithm are equivalent and turn out to be a frame shrinkage method. For the total variation regularizer, we also present a numerical comparison with multistep 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.     

Hybrid Splitting Methods for the System of Operator Inclusions with Monotone Operators1

New algorithms are proposed to solve a system of operator inclusions with monotone operators acting in a Hilbert space. The algorithms are based on three well-known methods: the Tseng forward-backward splitting algorithm and two hybrid algorithms for approximation of fixed points of nonexpansive operators. Theorems on the strong convergence of the sequences generated by the algorithms are proved.     

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.     

Inertial Hybrid Splitting Methods for Operator Inclusion Problems<Superscript>*</Superscript>

In this paper, new algorithms are proposed to solve operator inclusion problems with maximal monotone operators acting in a Hilbert space. The algorithms are based on inertial extrapolation and three well-known methods: Tseng forward-backward splitting and two hybrid algorithms for approximation of fixed points of nonexpansive operators. Theorems about strong convergence of the sequences generated by the algorithms are proved.     

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.     

An isentropic flow algorithm with body fitted meshes

An efficient algorithm based on flux difference splitting is presented for the solution of the three-dimensional equations of isentropic flow in a generalised coordinate system, and with a general convex gas law. The scheme is based on solving linearised Riemann problems approximately and in more than one dimension incorporates operator splitting. The algorithm requires only one function evaluation of the gas law in each computational cell. The scheme has good shock capturing properties and the advantage of using body-fitted meshes. Numerical results are shown for Mach 3 flow of air past a circular cylinder. Furthermore, the algorithm also applies to shallow water flows by employing the familiar gas dynamics analogy.     

A split-combination approach to merging knowledge bases in possibilistic logic

We propose an adaptive approach to merging possibilistic knowledge bases that deploys multiple operators instead of a single operator in the merging process. The merging approach consists of two steps: the splitting step and the combination step. The splitting step splits each knowledge base into two subbases and then in the second step, different classes of subbases are combined using different operators. Our merging approach is applied to knowledge bases which are self-consistent and results in a knowledge base which is also consistent. Two operators are proposed based on two different splitting methods. Both operators result in a possibilistic knowledge base which contains more information than that obtained by the t-conorm (such as the maximum) based merging methods. In the flat case, one of the operators provides a good alternative to syntax-based merging operators in classical logic. This paper is a revised and extended version of [36].     

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

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

Pricing American options using a space-time adaptive finite difference method

American options are priced numerically using a space- and time-adaptive finite difference method. The generalized Black–Scholes operator is discretized on a Cartesian structured but non-equidistant grid in space. The space- and time-discretizations are adjusted such that a predefined tolerance level on the local discretization error is met. An operator splitting technique is used to separately handle the early exercise constraint and the solution of linear systems of equations from the finite difference discretization of the linear complementarity problem. In numerical experiments three variants of the adaptive time-stepping algorithm with and without local time-stepping are compared.     

无线传感器网络中基于免疫补体优化的感知资源分配算法

基于无线传感器网络资源分配的非确定多项式(NP)难特性,提出了一种基于免疫补体优化的感知资源分配算法,提高了对感知资源的检查效率。给出了问题的优化模型和实现过程。借鉴免疫补体机制,设计了分裂算子、结合算子;抗体克隆扩增时根据激励度进行,保证了解的多样性。实验结果表明:该算法目标检测成功率随着检测目标数的不同而变化,最高检出率可达92%。