On the Convergence of Primal–Dual Hybrid Gradient Algorithms for Total Variation Image Restoration

In this paper we establish the convergence of a general primal?Cdual method for nonsmooth convex optimization problems whose structure is typical in the imaging framework, as, for example, in the Total Variation image restoration problems. When the steplength parameters are a priori selected sequences, the convergence of the scheme is proved by showing that it can be considered as an ??-subgradient method on the primal formulation of the variational problem. Our scheme includes as special case the method recently proposed by Zhu and Chan for Total Variation image restoration from data degraded by Gaussian noise. Furthermore, the convergence hypotheses enable us to apply the same scheme also to other restoration problems, as the denoising and deblurring of images corrupted by Poisson noise, where the data fidelity function is defined as the generalized Kullback?CLeibler divergence or the edge preserving removal of impulse noise. The numerical experience shows that the proposed scheme with a suitable choice of the steplength sequences performs well with respect to state-of-the-art methods, especially for Poisson denoising problems, and it exhibits fast initial and asymptotic convergence.     

Thermodynamic properties of quantum lattice models from numerical linked cluster expansions

We review a recently proposed numerical linked-cluster (NLC) algorithm that allows one to obtain temperature-dependent properties of quantum lattice models, in the thermodynamic limit, from exact diagonalization of finite clusters. This approach provides a systematic framework to assess finite-size effects and is valid for any quantum lattice model. We present results for thermodynamic properties of spin and t-J models in different lattice geometries in two-dimensions. In addition, we present an extrapolation scheme that enables one to accelerate the convergence of NLC.     

Interactions of two co-propagating laser beams in underdense plasmas using a generalized Peaceman-Rachford ADI form

A generalized Peaceman-Rachford ADI form based on the regularized finite difference scheme is employed to study the nonlinear interactions of two co-propagating laser beams in underdense plasmas. A numerical scheme using the form is constructed for the solution of two coupled 2D time-dependent nonlinear Schrödinger equations for quasineutral plasmas in paraxial approximation.In the constructed scheme, the coupled equations are reduced to systems of nonlinear tridiagonal equations that are solved using the matrix factorization and a direct explicit iteration method. In the stability analysis, a time-varying control parameter is introduced for a conditionally stable solution at varying conditions.The scheme has a good agreement with a previous simulations at similar conditions, and in comparison with other algorithms, the scheme presents a better conservation characteristic for the photons power. Finally, the simulations results confirmed that the scheme is suitable to simulate the interactions of two co-propagating laser beams in underdense plasma and it can successively simulate the associated phenomena at different parameters and conditions.     

Simulation of the Paraxial Laser Propagation Coupled with Hydrodynamics in 3D Geometry

We address here numerical simulation problems for modeling some phenomena arising in plasmas produced in experimental devices for Inertial Confinement Fusion. The model consists of a compressible fluid dynamics system coupled with a paraxial equation for modeling the laser propagation. For the fluid dynamics system, a numerical method of Lagrange–Euler type is used. For the paraxial equation, a time implicit discretization is settled which preserves the laser energy balance; the method is based on a splitting of the propagation term and the diffraction terms according to the propagation spatial variable. We give some features on the 3D implementation of the method in the parallel platform HERA. Results showing the accuracy of the numerical scheme are presented and we give also numerical results related to cases corresponding to realistic simulations, with a mesh containing up to 500 millions of cells.     

Sequential linear quadratic control of bilinear parabolic PDEs based on POD model reduction

We present a framework to solve a finite-time optimal control problem for parabolic partial differential equations (PDEs) with diffusivity-interior actuators, which is motivated by the control of the current density profile in tokamak plasmas. The proposed approach is based on reduced order modeling (ROM) and successive optimal control computation. First we either simulate the parabolic PDE system or carry out experiments to generate data ensembles, from which we then extract the most energetic modes to obtain a reduced order model based on the proper orthogonal decomposition (POD) method and Galerkin projection. The obtained reduced order model corresponds to a bilinear control system. Based on quasi-linearization of the optimality conditions derived from Pontryagin’s maximum principle, and stated as a two boundary value problem, we propose an iterative scheme for suboptimal closed-loop control. We take advantage of linear synthesis methods in each iteration step to construct a sequence of controllers. The convergence of the controller sequence is proved in appropriate functional spaces. When compared with previous iterative schemes for optimal control of bilinear systems, the proposed scheme avoids repeated numerical computation of the Riccati equation and therefore reduces significantly the number of ODEs that must be solved at each iteration step. A numerical simulation study shows the effectiveness of this approach.     

High order parameter-robust numerical method for time dependent singularly perturbed reaction–diffusion problems

We introduce a high order parameter-robust numerical method to solve a Dirichlet problem for one-dimensional time dependent singularly perturbed reaction-diffusion equation. A small parameter ε is multiplied with the second order spatial derivative in the equation. The parabolic boundary layers appear in the solution of the problem as the perturbation parameter ε tends to zero. To obtain the approximate solution of the problem we construct a numerical method by combining the Crank–Nicolson method on an uniform mesh in time direction, together with a hybrid scheme which is a suitable combination of a fourth order compact difference scheme and the standard central difference scheme on a generalized Shishkin mesh in spatial direction. We prove that the resulting method is parameter-robust or ε-uniform in the sense that its numerical solution converges to the exact solution uniformly well with respect to the singular perturbation parameter ε. More specifically, we prove that the numerical method is uniformly convergent of second order in time and almost fourth order in spatial variable, if the discretization parameters satisfy a non-restrictive relation. Numerical experiments are presented to validate the theoretical results and also indicate that the relation between the discretization parameters is not necessary in practice.     

Hierarchical clustering of mixed data based on distance hierarchy

Data clustering is an important data mining technique which partitions data according to some similarity criterion. Abundant algorithms have been proposed for clustering numerical data and some recent research tackles the problem of clustering categorical or mixed data. Unlike the subtraction scheme used for numerical attributes, there is no standard for measuring distance between categorical values. In this article, we propose a distance representation scheme, distance hierarchy, which facilitates expressing the similarity between categorical values and also unifies distance measuring of numerical and categorical values. We then apply the scheme to mixed data clustering, in particular, to integrate with a hierarchical clustering algorithm. Consequently, this integrated approach can uniformly handle numerical data and categorical data, and also enables one to take the similarity between categorical values into consideration. Experimental results show that the proposed approach produces better clustering results than conventional clustering algorithms when categorical attributes are present and their values have different degree of similarity.     

Stability properties of a higher order scheme for a GKdV-4 equation modelling surface water waves

This work is devoted to the study of a higher order numerical scheme for the critical generalized Korteweg-de Vries equation (GKdV with p=4) in a bounded domain. The KdV equation and some of its generalizations as the GKdV type equations appear in Physics, for example in the study of waves on shallow water. Based on the analysis of stability of the first order scheme introduced by Pazoto et al. (Numer. Math. 116:317–356, 2010), we add a vanishing numerical viscosity term to a semi-discrete scheme so as to preserve similar properties of stability, and thus able to prove the convergence in L ⁴-strong. The semi-discretization of the spatial structure via central finite difference method yields a stiff system of ODE. Hence, for the temporal discretization, we resort to the two-stage implicit Runge-Kutta scheme of the Gauss-Legendre type. The resulting system is unconditionally stable and possesses favorable nonlinear properties. On the other hand, despite the formation of blow up for the critical case of GKdV, it is known that a localized damping term added to the GKdV-4 equation leads to the exponential decay of the energy for small enough initial conditions, which is interesting from the standpoint of the Control Theory. Then, combining the result of convergence in L ⁴-strong with discrete multipliers and a contradiction argument, we show that the presence of the vanishing numerical viscosity term allows the uniform (with respect to the mesh size) exponential decay of the total energy associated to the semi-discrete scheme of higher-order in space with the localized damping term. Numerical experiments are provided to illustrate the performance of the method and to confirm the theoretical results.     

DIG: Degree of inter-reference gap for a dynamic buffer cache management

The effectiveness of the buffer cache replacement is critical to the performance of I/O systems. In this paper, we propose a degree of inter-reference gap (DIG) based block replacement scheme. This scheme keeps the simplicity of the least recently used (LRU) scheme and does not depend on the detection of access regularities. The proposed scheme is based on the low inter-reference recency set (LIRS) scheme, which is currently known to be very effective. However, the proposed scheme employs several history information items whereas the LIRS scheme uses only one history information item. The overhead of the proposed scheme is almost negligible. To evaluate the performance of the proposed scheme, the comprehensive trace-driven computer simulation is used in general access patterns. Our simulation results show that the cache hit ratio (CHR) in the proposed scheme is improved as much as 65.3% (with an average of 26.6%) compared to the LRU for the same workloads, and up to 6% compared to the LIRS in multi3 trace.     

Joint precoding selection diversity with limited feedback

Coordinated multiple-point transmission (CoMP) is one of important techniques for the reduction of inter-cluster interference. Three major schemes have been presented for CoMP-joint processing transmission (CoMP-JPT) under limited-feedback environments: global, local, and single-frequency network precoding methods. However, most previous studies have demonstrated effectiveness only in specific environments without presenting numerical analyses. In this paper, we verify the characteristics of each precoding scheme based on zero-forcing beamforming (ZFBF) with semi-orthogonal user selection (SUS) by exploiting numerical analysis. In addition, we propose a selection algorithm that achieves the diversity of the precoding schemes based on limited feedback according to the downlink channel status of cellular systems. In addition, for the 3rd Generation Partnership Project Long Term Evolution-Advanced (3GPP LTE-Advanced), a network protocol that is required to adapt the CoMP-JPT scheme is implemented. Through simulations, we demonstrate that the proposed system can effectively improve the quality of service for cell-edge users while guaranteeing fairness compared to the conventional precoding schemes.     

Flux-gradient and source-term balancing for certain high resolution shock-capturing schemes

We present an extension of Marquina’s flux formula, as introduced in Fedkiw et al. [Fedkiw RP, Merriman B, Donat R, Osher S. The penultimate scheme for systems of conservation laws: finite difference ENO with Marquina’s flux splitting. In: Hafez M, editor. Progress in numerical solutions of partial differential equations, Arcachon, France; July 1998], for the shallow water system. We show that the use of two different Jacobians at cell interfaces prevents the scheme from satisfying the exact C-property [Bermúdez A, Vázquez ME. Upwind methods for hyperbolic conservation laws with source terms. Comput Fluids 1994;23(8):1049-71] while the approximate C-property is satisfied for higher order versions of the scheme. The use of a single Jacobian in Marquina’s flux splitting formula leads to a numerical scheme satisfying the exact C-property, hence we propose a combined technique that uses Marquina’s two sided decomposition when the two adjacent states are not close and a single decomposition otherwise. Finally, we propose a special treatment at wet/dry fronts and situations of dry bed generation.     

A novel fuzzy identity based signature scheme based on the short integer solution problem

Lattice-based cryptosystems have recently acquired much importance. In this work, we construct a fuzzy identity based signature (FIBS) scheme based on the Small Integer Solution (SIS) Problem. FIBS schemes allow a user with identity id to issue a signature which could be verified under identity id′ if and only if id and id′ are close to each other. To our best knowledge, no lattice based FIBS schemes were known before, and the existing security model of FIBS schemes is not correct indeed. We propose a modified security model and prove that our scheme is existentially unforgetable against adaptively chosen message and identity attacks in the random oracle model. To break the bottleneck of designing lattice-based FIBS scheme, the secret key of each identity bit is generated by employing the Bonsai Tree techniques in the fuzzy extract algorithm. We also use some techniques to prove its security. Then we show the performance comparisons of all existing FIBS schemes. Finally, we give its application in biometric authentication.     

A treatment of discontinuities for nonlinear systems with linearly degenerate fields

In this paper we propose an artificial compression technique to avoid the numerical diffusion that standard numerical methods present in contact discontinuities. The main idea is to replace contact discontinuities by shocks. For nonlinear 1D systems we replace locally linearly degenerate fields by genuinely nonlinear fields, in such a way the solution does not vary. We apply this technique to a family of numerical schemes and we deduce that this can be seen as a discretization of the system modified by a new term, when we are in a jump of a contact discontinuity. We have also extended this technique for the multidimensional case. We prove by applying the artificial compression technique that the numerical scheme is stable under the same CFL condition. We also present different numerical schemes: Sod’s problem for 1D Euler equations, transport of a discontinuity, a stationary contact discontinuity and in the multidimensional case the transversal transport of two different geometries. We observe that in all cases the numerical diffusion is reduced.     

Time domain computation of flow induced sound

We present a recently developed numerical scheme for computational aeroacoustics (CAA). Therewith, we solve the flow field by a large eddy simulation (LES) and the generation as well as propagation of acoustic noise by Lighthill’s analogy applying the finite element method. The developed scheme allows a direct coupling in time domain as well as a sequential coupling in frequency domain and provides the acoustic sound field not only in the far field but also in the region of the flow. Furthermore, we can directly investigate the acoustic source terms in the flow region. The scheme is well suited for interior aeroacoustic problems with complex geometries as well as for fluid-structure interaction problems. Implementation is validated and a two-dimensional simple application example is used to investigate the acoustic sources and to evaluate the acoustic pressure field from both transient and harmonic analyses.     

A matrix-free cone complementarity approach for solving large-scale,nonsmooth, rigid body dynamics

This paper proposes an iterative method that can simulate mechanical systems featuring a large number of contacts and joints between rigid bodies. The numerical method behaves as a contractive mapping that converges to the solution of a cone complementarity problem by means of iterated fixed-point steps with separable projections onto convex manifolds. Since computational speed and robustness are important issues when dealing with a large number of frictional contacts, we have performed special algorithmic optimizations in order to translate the numerical scheme into a matrix-free algorithm with O(n) space complexity and easy implementation. A modified version, that can run on parallel computers is discussed. A multithreaded version of the method has been used to simulate systems with more than a million contacts with friction.     

Second-order, exact charge conservation for electromagnetic particle-in-cell simulation in complex geometry

A second-order, exact charge-conserving algorithm for accumulating charge and current on the spatial grid for electromagnetic particle-in-cell (EM-PIC) simulation in bounded geometry is presented. The algorithm supports standard EM-PIC exterior boundary conditions and complex internal conductors on non-uniform grids. Boundary surfaces are handled by smoothly transitioning from second to first-order weighting within half a cell of the boundary. When a particle is exactly on the boundary surface (either about to be killed, or just created), the weighting is fully first-order. This means that particle creation and particle/surface interaction models developed for first-order weighting do not need to be modified. An additional feature is the use of an energy-conserving interpolation scheme from the electric field on the grid to the particles. Results show that high-density, cold plasmas with ωpeΔt∼1, and Δx/λD?1, can be modeled with reasonable accuracy and good energy conservation. This opens up a significant new capability for explicit simulation of high-density plasmas in high-power devices.     

Upwinding of the source term at interfaces for Euler equations with high friction

We consider Euler equations with a friction term that describe an isentropic gas flow in a porous domain. More precisely, we consider the transition between low and high friction regions. In the high friction region the system is reduced to a parabolic equation, the porous media equation. In this paper we present a hyperbolic approach based on a finite volume technique to compute numerical solutions for the system in both regimes. The Upwind Source at Interfaces (USI) scheme that we propose satisfies the following properties. Firstly it preserves the nonnegativity of gas density. Secondly, and this is the motivation, the scheme is asymptotically consistent with the limit model (porous media equation) when the friction coefficient goes to infinity. We show analytically and through numerical results that the above properties are satisfied. We shall also compare results given with the use of USI, hyperbolic–parabolic coupling and classical centered sources schemes.     

A new kind of discretization scheme for solving a two-dimensional time-independent Schrödinger equation

In this paper we present a new kind of discretization scheme for solving a two-dimensional time-independent Schrödinger equation. The scheme uses a symmetrical multi-point difference formula to represent the partial differentials of the two-dimensional variables, which can improve the accuracy of the numerical solutions to the order of Δx2Nq+2 when a (2Nq+1)-point formula is used for any positive integer Nq with Δx=Δy, while Nq=1 equivalent to the traditional scheme. On the other hand, the new scheme keeps the same form of the traditional matrix equation so that the standard algebraic eigenvalue algorithm with a real, symmetric, large sparse matrix is still applicable. Therefore, for the same dimension, only a little more CPU time than the traditional one should be used for diagonalizing the matrix. The numerical examples of the two-dimensional harmonic oscillator and the two-dimensional Henon-Heiles potential demonstrate that by using the new method, the error in the numerical solutions can be reduced steadily and extensively through the increase of Nq, which is more efficient than the traditional methods through the decrease of the step size.     

A Dual-Petrov-Galerkin Method for the Kawahara-Type Equations

An efficient and accurate numerical scheme is proposed, analyzed and implemented for the Kawahara and modified Kawahara equations which model many physical phenomena such as gravity-capillary waves and magneto-sound propagation in plasmas. The scheme consists of dual-Petrov-Galerkin method in space and Crank-Nicholson-leap-frog in time such that at each time step only a sparse banded linear system needs to be solved. Theoretical analysis and numerical results are presented to show that the proposed numerical is extremely accurate and efficient for Kawahara type equations and other fifth-order nonlinear equations. This work is partially supported by the National Science Council of the Republic of China under the grant NSC 94-2115-M-126-004 and 95-2115-M-126-003. This work is partially supported by NSF grant DMS-0610646.     

Efficient Numerical Methods for Strongly Anisotropic Elliptic Equations

In this paper, we study an efficient numerical scheme for a strongly anisotropic elliptic problem which arises, for example, in the modeling of magnetized plasma dynamics. A small parameter ε induces the anisotropy of the problem and leads to severe numerical difficulties if the problem is solved with standard methods for the case 0<ε?1. An Asymptotic-Preserving scheme is therefore introduced in this paper in a 2D framework, with an anisotropy aligned to one coordinate axis and an ε-intensity which can be either constant or variable within the simulation domain. This AP scheme is uniformly precise in ε, permitting thus the choice of coarse discretization grids, independent of the magnitude of the parameter ε.