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.     

Stability and convergence of difference schemes for multi-dimensional parabolic equations with variable coefficients and mixed derivatives

ABSTRACT

We present second-order difference schemes for a class of parabolic problems with variable coefficients and mixed derivatives. The solvability, stability and convergence of the schemes are rigorously analysed by the discrete energy method. Using the Richardson extrapolation technique, the fourth-order accurate numerical approximations both in time and space are obtained. It is noted that the Richardson extrapolation algorithms can preserve stability of the original difference scheme. Finally, numerical examples are carried out to verify the theoretical results.     

Euler-like discrete models of the logistic differential equation

To understand the behavior of difference schemes on nonlinear differential equations, it seems desirable to extend the standard linear stability theory into a nonlinear theory. As a step in that direction, we investigate the stability properties of Euler-related integration algorithms by checking how they preserve and violate the dynamical structure of the logistic differential equation.Among the schemes considered are two linearly implicit nonstandard schemes which are adjoint to each other. We find that these schemes are superior to explicit schemes when they are stable and the blow-up time has not passed: for these λh-values they are dynamically faithful. When these schemes ‘turn unstable’, however, they have much less desirable properties than explicit or fully implicit schemes: they become simultaneously superstable and unstable. This is explained by the fact that these schemes are not self-adjoint: the linearly implicit self-adjoint scheme is dynamically faithful in an Euler-typical range of step sizes and gives correct stability for all step sizes.     

A numerical method to price discrete double Barrier options under a constant elasticity of variance model with jump diffusion

We develop a numerical method to price discrete barrier options on an underlying described by the constant elasticity of variance model with jump-diffusion (CEVJD). In particular, the partial integro differential equation associated to this model is discretized in time using an operator splitting scheme whose accuracy is enhanced by repeated Richardson extrapolation. Such an approach allows us to approximate the differential terms and the jump integral by means of two different numerical techniques. Precisely, the spatial derivatives, which exist only in the weak sense, are discretized using a finite element method based on piecewise quadratic polynomials, whereas the jump integral is directly collocated at the mesh points, so that it can be easily evaluated by Simpson numerical quadrature. As shown by extensive numerical simulation, the proposed approach is very efficient from the computational standpoint, and performs significantly better than the finite difference scheme developed in Wade et al. [On smoothing of the Crank–Nicolson scheme and higher order schemes for pricing barrier options, J. Comput. Appl. Math. 204 (2007), pp. 144–158].     

Introducing the bounded derivative network—superceding the application of neural networks in control

The Bounded Derivative Network (BDN), the analytical integral of a neural network, is a natural and elegant evolution of universal approximating technology for use in automatic control schemes. This modeling approach circumvents the many real problems associated with standard neural networks in control such as model saturation (zero gain), arbitrary model gain inversion, ‘black box’ representation and inability to interpolate sensibly in regions of sparse excitation. Although extrapolation is typically not an advantage unless the understanding of the process is complete, the BDN can incorporate process knowledge in order that its extrapolation capability is inherently sensible in areas of data sparsity. This ability to impart process knowledge on the BDN model enables it to be safely incorporated into a model based control scheme.     

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.     

Variational multiscale method based on the Crank–Nicolson extrapolation scheme for the non-stationary Navier–Stokes equations

In this report, a variational multiscale (VMS) method based on the Crank–Nicolson extrapolation scheme of time discretization for the turbulent flow is analysed. The flow is modelled by the fully evolutionary Navier–Stokes problem. This method has two differences compared to the standard VMS method: (i) For the trilinear term, we use the extrapolation skill to linearize the scheme; (ii) for the projection term, we lag it onto the previous time level to simplify the construction of the projection. These modifications make the algorithm more efficient and feasible. An unconditionally stability and an a priori error estimate are given for a case with rather general linear (cellwise constant) viscosity of the turbulent models. Moreover, numerical tests for both linear viscosity and nonlinear Smagorinsky-type viscosity are performed, they confirm the theoretical results and indicate the schemes are effective.     

A Stability Criterion for Semi-Discrete Difference Schemes of Hyperbolic Conservation Laws on Uniform Grids

In the present study, the stability condition for semi-discrete difference schemes of hyperbolic conservation laws obtained from Fourier analysis is simplified. This stability condition can be applied only to linear difference schemes with constant coefficients implemented with periodic boundary treatment. It could often give useful results for other cases, such as schemes with variable coefficients, schemes for nonperiodic problem and nonlinear problem. However, this condition usually leads to a trigonometric inequality, which makes it not convenient to use. For explicit difference schemes on uniform grids, this trigonometric inequality can be converted to polynomial form. Furthermore, if the scheme is a high-order one, the polynomial can be factorized into a simple form. Thus, it is much easier to solve than the inequality obtained directly from Fourier analysis. For compact difference schemes and conservative schemes, similar results are obtained. Some applications of this new stability criterion are shown, including judging the stability of two schemes, proving the upstream central schemes to be stable, constructing a stable upwind dissipation relation preserving (DRP) scheme and constructing an optimized weighted essentially non-oscillatory (WENO) scheme. Since WENO schemes are nonlinear schemes, the stability analysis in the present study is performed on their underlying linear schemes. According to the numerical tests, the underlying linear scheme should be stable, otherwise the corresponding WENO scheme may display instability. These applications demonstrate that this criterion is convenient and efficient for judging the linear stability of semi-discrete difference schemes and constructing stable upwind difference schemes.     

Energy stable and large time-stepping methods for the Cahn–Hilliard equation

We present the numerical methods for the Cahn–Hilliard equation, which describes phase separation phenomenon. The goal of this paper is to construct high-order, energy stable and large time-stepping methods by using Eyre's convex splitting technique. The equation is discretized by using a fourth-order compact difference scheme in space and first-order, second-order or third-order implicit–explicit Runge–Kutta schemes in time. The energy stability for the first-order scheme is proved. Numerical experiments are given to demonstrate the performance of the proposed methods.     

Bicompact monotonic schemes for a multidimensional linear transport equation

Bicompact difference schemes, previously proposed by the authors for linear one-dimensional transport equations are generalized to the multidimensional case by using a coordinate-wise splitting of the multidimensional problem. The scheme stencil for each of the spatial directions is minimal and consists of two points. The schemes are efficient and can be solved by the running calculation method. The proposed difference schemes have the fourth-order approximation in space variables and first- or third-order time approximation for smooth solutions. The schemes for solving multidimensional problems have inherited the monotonicity property of one-dimensional bicompact schemes. Numerical examples are given illustrating the actual accuracy order of bicompact schemes for smooth solutions and the scheme monotonicity for discontinuous solutions.     

Distributed Multi-Level Recovery in Main-Memory Databases

In this paper we present recovery techniques for distributed main-memory databases, specifically for client-server and shared-disk architectures. We present a recovery scheme for client-server architectures which is based on shipping log records to the server, and two recovery schemes for shared-disk architectures—one based on page shipping, and the other based on broadcasting of the log of updates. The schemes offer different tradeoffs, based on factors such as update rates.Our techniques are extensions to a distributed-memory setting of a centralized recovery scheme for main-memory databases, which has been implemented in the Dalì main-memory database system. Our centralized as well as distributed-memory recovery schemes have several attractive features—they support an explicit multi-level recovery abstraction for high concurrency, reduce disk I/O by writing only redo log records to disk during normal processing, and use per-transaction redo and undo logs to reduce contention on the system log. Further, the techniques use a fuzzy checkpointing scheme that writes only dirty pages to disk, yet minimally interferes with normal processing—all but one of our recovery schemes do not require updaters to even acquire a latch before updating a page. Our log shipping/broadcasting schemes also support concurrent updates to the same page at different sites.     

Towards secure and efficient user authentication scheme using smart card for multi-server environments

Two user authentication schemes for multi-server environments have been proposed by Tsai and Wang et al., respectively. However, there are some flaws existing in both schemes. Therefore, a new scheme for improving these drawbacks is proposed in this paper. The proposed scheme has the following benefits: (1) it complies with all the requirements for multi-server environments; (2) it can withstand all the well-known attacks at the present time; (3) it is equipped with a more secure key agreement procedure; and (4) it is quite efficient in terms of the cost of computation and transmission. In addition, the analysis and comparisons show that the proposed scheme outperforms the other related schemes in various aspects.     

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.     

Numerical Study of a Modified Time-Stepping θ-Scheme for Incompressible Flow Simulations

In [Turek (1996). Int. J. Numer. Meth. Fluids 22, 987–1011], we had performed numerical comparisons for different time stepping schemes for the incompressible Navier–Stokes equations. In this paper, we present the numerical analysis in the context of the Navier–Stokes equations for a modified time-stepping θ-scheme which has been recently proposed by Glowinski [Glowinski (2003). In: Ciarlet, P. G., and Lions, J. L. (eds.), Handbook of Numerical Analysis, Vol. IX, North-Holland, Amsterdam, pp. 3–1176]. Like the well-known classical Fractional-Step-θ-scheme which had been introduced by Glowinski [Glowinski (1985). In Murman, E. M. and Abarbanel, S. S. (eds.), Progress and Supercomputing in Computational Fluid Dynamics, Birkh?user, Boston MA; Bristeau et al. (1987). Comput. Phys. Rep. 6, 73–187], too, and which is still one of the most popular time stepping schemes, with or without operator splitting techniques, this new scheme consists of 3 substeps with nonequidistant substepping to build one macro time step. However, in contrast to the Fractional-Step-θ-scheme, the second substep can be formulated as an extrapolation step for previously computed data only, and the two remaining substeps look like a Backward Euler step so that no expensive operator evaluations for the right hand side vector with older solutions, as for instance in the Crank–Nicolson scheme, have to be performed. This modified scheme is implicit, strongly A-stable and second order accurate, too, which promises some advantageous behavior, particularly in implicit CFD simulations for the nonstationary Navier–Stokes equations. Representative numerical results, based on the software package FEATFLOW [Turek (2000). FEATFLOW Finite element software for the incompressible Navier–Stokes equations: User Manual, Release 1.2, University of Dortmund] are obtained for typical flow problems with benchmark character which provide a fair rating of the solution schemes, particularly in long time simulations.Dedicated to David Gottlieb on the occasion of his 60th anniversary     

Achieving high-order fluctuation splitting schemes by extending the stencil

An extension to the fluctuation splitting approach for approximating hyperbolic conservation laws is described, which achieves higher than second-order accuracy in both space and time by extending the range of the distribution of the fluctuations. Initial results are presented for a simple linear scheme which is third-order accurate in both space and time on uniform triangular grids. Numerically induced oscillations are suppressed by applying the flux-corrected transport algorithm. These schemes are evaluated in the context of existing fluctuation splitting approaches to modelling time-dependent flows and some suggestions for their future development are made.     

空间太阳能电站太阳能接收器二维展开过程的保结构分析

针对传统数值方法求解微分-代数方程过程中经常遇到的违约问题,本文以空间太阳能电站太阳能接收器的简化二维模型为例,采用辛算法模拟了简化模型的展开过程,研究了辛算法在求解过程中约束违约问题.首先,基于Hamilton变分原理,将描述简化二维模型展开过程的Euler-Lagrange方程导入Hamilton体系,建立其Hamilton正则方程;随后,采用s级PRK离散方法离散正则方程,得到其辛格式;最后,采用辛PRK格式模拟太阳能接收器的二维展开过程.模拟结果显示:本文构造的辛PRK格式能够很好地满足系统的位移约束.     

Second-order-accurate explicit fluctuation splitting schemes for unsteady problems

This paper is concerned with the issue of obtaining explicit fluctuation splitting schemes which achieve second-order accuracy in both space and time on an arbitrary unstructured triangular mesh. A theoretical analysis demonstrates that, for a linear reconstruction of the solution, mass lumping does not diminish the accuracy of the scheme provided that a Galerkin space discretization is employed. Thus, two explicit fluctuation splitting schemes are devised which are second-order accurate in both space and time, namely, the well known Lax-Wendroff scheme and a Lax-Wendroff-type scheme using a three-point-backward discretization of the time derivative. A thorough mesh-refinement study verifies the theoretical order of accuracy of the two schemes on meshes with increasing levels of nonuniformity.     

Programming Environment for Phase-Reconfigurable Parallel Programming on SuperNode

This paper presents a programming environment called C_—NET that we have developed for the reconfigurable SuperNode multiprocessor. It shows how one can take advantage of the environment to implement phase-reconfigurable programs. In the first stage a computing model is designed in relation with the capabilities of the hardware. Next, the entire programming environment is built upon this model. It is organized around a kernel language which has been extended in three separate directions so as to provide three specialized languages: PPL (phase programming language) for the development of phase-reconfigurable programs, GCL (graph-construction language) for the construction of processor graphs on which the phases are to be executed, and CPL (component programming language) for coding the software components that are to be executed on the processors within the phases. The second part of the paper provides an illustration of C_—NET. First, two implementations of the conjugate gradient algorithm within C_—NET are carried out: a phase-reconfigurable implementation and a fixed-topology one. Both have been developed on a 32-node machine. Next, a time model is built for both implementations. The time estimates yielded by the models are checked against time measurements issued from program runs. The time models are proved valid and are subsequently used for extrapolation purposes. The speed-up that could be achieved by executing the conjugate gradient algorithm on larger machines (up to 1024) is discussed ultimately.     

Unconditionally positivity and boundedness preserving schemes for a FitzHugh–Nagumo equation

In this paper, a semi-explicit scheme is constructed for the space-independent FitzHugh–Nagumo equation. Qualitative stability analysis shows that the semi-explicit scheme is dynamically consistent with the space independent equation. Then, the semi-explicit scheme is extended to construct a new finite difference scheme for the full FitzHugh–Nagumo equation in one- and two-space dimensions, respectively. According to the theory of M-matrices, it is proved that these new schemes are able to preserve the positivity and boundedness of solutions of the corresponding equations for arbitrary step sizes. The consistency and numerical stability of these schemes is also analysed. Combined with the property of the strictly diagonally dominant matrix, the convergence of these schemes is established. Numerical experiments illustrate our results and display the advantages of our schemes in comparison to some other schemes.     

Strongly secure ramp secret sharing schemes for general access structures

Ramp secret sharing (SS) schemes can be classified into strong ramp SS schemes and weak ramp SS schemes. The strong ramp SS schemes do not leak out any part of a secret explicitly even in the case that some information about the secret leaks out from some set of shares, and hence, they are more desirable than the weak ramp SS schemes. In this paper, it is shown that for any feasible general access structure, a strong ramp SS scheme can be constructed from a partially decryptable ramp SS scheme, which can be considered as a kind of SS scheme with plural secrets. As a byproduct, it is pointed out that threshold ramp SS schemes based on Shamir's polynomial interpolation method are not always strong.