Une méthode de décomposition en temps avec des schémas dʼintégration réversible pour la résolution de système dʼéquations différentielles ordinaires

We propose a time domain decomposition method that breaks the sequentiality of the integration scheme for systems of ODE. Under the condition of differentiability of the flow, we transform the initial value problem into a well-posed boundary values problem using the symmetrization of the interval of time integration and time-reversible integration scheme. For systems of linear ODE, we explicitly construct the block tridiagonal system satisfied by the solutions at the time sub-intervals extremities. We then propose an iterative algorithm of Schwarz type for updating the interfaces conditions which can extend the method to systems of nonlinear ODE.     

计算高维带弱奇异核发展型方程的交替方向隐式欧拉方法

本文主要研究高维带弱奇异核的发展型方程的交替方向隐式(ADI)差分方法.向后欧拉(Euler)方法联立一阶卷积求积公式处理时间方向的离散,有限差分方法处理空间方向的离散,并进一步构造了ADI全离散差分格式.然后将二维问题延伸到三维问题,构造三维空间问题的ADI差分格式.基于离散能量法,详细证明了全离散格式的稳定性和误差分析.随后给出了2个数值算例,数值结果进一步验证了时间方向的收敛阶为一阶,空间方向的收敛阶为二阶,和理论分析结果一致.     

Long Time Asymptotic Behavior of Solution of Difference Scheme for a Semilinear Parabolic Equation

In this paper we prove that the solution of implicit difference scheme for a semilinear parabolic equation converges to the solution of difference scheme for the corresponding nonlinear stationary problem as $t\rightarrow\infty$. For the discrete solution of nonlinear parabolic problem, we get its long time asymptotic behavior which is similar to that of the continuous solution. For simplicity, we consider one-dimensional problem.     

Finite-difference schemes for a diffusion equation with fractional derivatives in a multidimensional domain

In a multidimensional domain, we consider a partial differential equation with fractional space and time derivatives. For the first initial-boundary value problem, we consider a purely implicit scheme based on the approximate factorization method. We prove the stability of the implicit scheme for the considered class of problems.     

A second order scheme for a time-dependent,singularly perturbed convection–diffusion equation

We consider a numerical scheme for a one-dimensional, time-dependent, singularly perturbed convection–diffusion problem. The problem is discretized in space by a standard finite element method on a Bakhvalov–Shishkin type mesh. The space error is measured in an L² norm. For the time integration, the implicit midpoint rule is used. The fully discrete scheme is shown to be convergent of order 2 in space and time, uniformly in the singular perturbation parameter.     

First-order inertial algorithms involving dry friction damping

We present a Branch-and-Cut algorithm for a class of nonlinear chance-constrained mathematical optimization problems with a finite number of scenarios. Unsatisfied scenarios can enter a recovery mode. This class corresponds to problems that can be reformulated as deterministic convex mixed-integer nonlinear programming problems with indicator variables and continuous scenario variables, but the size of the reformulation is large and quickly becomes impractical as the number of scenarios grows. The Branch-and-Cut algorithm is based on an implicit Benders decomposition scheme, where we generate cutting planes as outer approximation cuts from the projection of the feasible region on suitable subspaces. The size of the master problem in our scheme is much smaller than the deterministic reformulation of the chance-constrained problem. We apply the Branch-and-Cut algorithm to the mid-term hydro scheduling problem, for which we propose a chance-constrained formulation. A computational study using data from ten hydroplants in Greece shows that the proposed methodology solves instances faster than applying a general-purpose solver for convex mixed-integer nonlinear programming problems to the deterministic reformulation, and scales much better with the number of scenarios.

     

扩散方程一种无条件稳定的保正并行有限差分方法

本文针对扩散方程提出了一种保正的并行差分格式,并且这个格式为无条件稳定的.我们在每个时间层将计算区域分成许多个子区域以便于实施并行计算.格式构造中首先我们使用前两个时间层的计算结果在分区界面处通过一种非线性的保正外插来预估子区域界面值.然后在每个子区域内部使用经典的全隐格式进行计算.最后在界面处使用全隐格式进行校正（本质上这一步计算是显式计算）.我们给出了一维与二维情形下的保正并行差分格式,并相应的给出了无条件稳定性证明.数值实验显示此并行格式具有二阶数值精度,而且无条件稳定性与保正性也均在数值实验中得到验证.     

Du Fort-Frankel格式及DFF-I并行格式的稳定性

 本文对抛物型方程的Du Fort-Frankel(DFF)格式以及基于该格式构造的并行差分格式(DFF-I)进行了稳定性分析。采用矩阵分析方法, 证明了其无条件(LR)稳定性, 给出了DFF格式的稳定性系数的最小值的上界估计, 结果表明其与网格比有关, 从而DFF格式并非绝对稳定。本文改进了并行差分格式(DFF-I)的稳定性分析结果, 证明了其增长矩阵的谱半径严格小于1, 从而具有长时间稳定性。数值算例验证了DFF-I格式具有空间二阶精度, 且有很好的稳定性。     

The coordination of transportation and batching scheduling

We study a coordinated scheduling problem of production and transportation in which each job is transported to a single batching machine for further processing. There are m vehicles that transport jobs from the holding area to the batching machine. Each vehicle can transport only one job at a time. The batching machine can process a batch of jobs simultaneously where there is an upper limit on the batch size. Each batch to be processed occurs a processing cost. The problem is to find a joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized. For a special case of the problem where the job assignment to the vehicles is predetermined, we provide a polynomial time algorithm. For the general problem, we prove that it is NP-hard (in the ordinary sense) and present a pseudo-polynomial time algorithm. A fully polynomial time approximation scheme for the general problem is obtained by converting an especially designed pseudo-polynomial dynamic programming algorithm.     

An algebraic multigrid method for high order time-discretizations of the div-grad and the curl-curl equations

We present an algebraic multigrid algorithm for fully coupled implicit Runge–Kutta and Boundary Value Method time-discretizations of the div-grad and curl-curl equations. The algorithm uses a blocksmoother and a multigrid hierarchy derived from the hierarchy built by any algebraic multigrid algorithm for the stationary version of the problem. By a theoretical analysis and numerical experiments, we show that the convergence is similar to or better than the convergence of the scalar algebraic multigrid algorithm on which it is based. The algorithm benefits from several possibilities for implementation optimization. This results in a computational complexity which, for a modest number of stages, scales almost linearly as a function of the number of variables.     

A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem

In this paper we present a genetic algorithm for the multi-mode resource-constrained project scheduling problem (MRCPSP), in which multiple execution modes are available for each of the activities of the project. We also introduce the preemptive extension of the problem which allows activity splitting (P-MRCPSP). To solve the problem, we apply a bi-population genetic algorithm, which makes use of two separate populations and extend the serial schedule generation scheme by introducing a mode improvement procedure. We evaluate the impact of preemption on the quality of the schedule and present detailed comparative computational results for the MRCPSP, which reveal that our procedure is amongst the most competitive algorithms.     

A fast numerical solution of the 3D nonlinear tempered fractional integrodifferential equation

In this paper, we investigate the numerical solution of the three-dimensional (3D) nonlinear tempered fractional integrodifferential equation which is subject to the initial and boundary conditions. The backward Euler (BE) method in association with the first-order convolution quadrature rule is employed to discretize this equation for time, and the Galerkin finite element method is applied for space, which is combined with an alternating direction implicit (ADI) algorithm, in order to reduce the computational cost for solving the three-dimensional nonlocal problem. Then a fully discrete BE ADI Galerkin finite element scheme can be obtained by linearizing the non-linear term. Thereafter we prove a positive-type lemma, from which the stability and convergence of the proposed numerical scheme are derived based on the energy method. Numerical experiments are performed to verify the effectiveness of the proposed approach.     

Total Variation Diminishing Implicit Runge-Kutta Methods for Dissipative Advection-Diffusion Problems in Astrophysics

We investigate the properties of dissipative full discretizations for the equations of motion associated with models of flow and radiative transport inside stars. We derive dissipative space discretizations and demonstrate that together with specially adapted total-variation-diminishing (TVD) or strongly stable Runge-Kutta time discretizations with adaptive step-size control this yields reliable and efficient integrators for the underlying high-dimensional nonlinear evolution equations. For the most general problem class, fully implicit SDIRK methods are demonstrated to be competitive when compared to popular explicit Runge-Kutta schemes as the additional effort for the solution of the associated nonlinear equations is compensated by the larger step-sizes admissible for strong stability and dissipativity. For the parameter regime associated with semiconvection we can use partitioned IMEX Runge-Kutta schemes, where the solution of the implicit part can be reduced to the solution of an elliptic problem. This yields a significant gain in performance as compared to either fully implicit or explicit time integrators. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Implicit and explicit algorithms for solving the split feasibility problem

Very recently, Dang and Gao (Inverse Probl 27:015007, 2011) introduced a KM-CQ algorithm with strong convergence for the split feasibility problem. In this paper, we will continue to consider the split feasibility problem. We present two algorithms. First, we introduce an implicit algorithm. Consequently, by discretizing the continuous implicit algorithm, we obtain an explicit algorithm. Under some weaker conditions, we show the strong convergence of presented algorithms to some solution of the split feasibility problem which solves some special variational inequality. As special cases, we obtain two algorithms which converge strongly to the minimum norm solution of the split feasibility problem. Results obtained in this paper include the corresponding results of Dang and Gao (2011) and extend a recent result of Wang and Xu (J Inequalities Appl 2010, doi:10.1155/2010/102085).     

A simple but NP-hard problem of mixed-discrete programming and its solution by approximate algorithms

A NP-hard problem (P) of mixed-discrete linear programming is considered which consists in the minimization of a linear objective function subject to a special non-connected subset of an unbounded polymatroid. For this problem we describe three polynomial approximate algorithms including a greedy algorithm and a fully polynomial approximation scheme solving a special subproblem of (P).     

An implicit finite difference scheme for the nonlinear size-structured population model

In this paper we consider the "fully nonlinear" size structured population model. We develop an implicit finite difference scheme to approximate the solution of this nonlinear partial differential equation. The convergence of this approximation to a unique bounded variation solution of this model is obtained. Numerical results to an example problem are presented.     

Numerical analysis for a locally damped wave equation

We consider a semi-discrete finite element formulation with artificial viscosity for the numerical approximation of a problem that models the damped vibrations of a string with fixed ends. The damping coefficient depends on the spatial variable and is effective only in a sub-interval of the domain. For this scheme, the energy of semi-discrete solutions decays exponentially and uniformly with respect to the mesh parameter to zero. We also introduce an implicit in time discretization. Error estimates for the semi-discrete and fully discrete schemes in the energy norm are provided and numerical experiments performed.     

Approximation algorithms for combinatorial fractional programming problems

We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0–1 knapsack problem.     

Numerical analysis and simulations of a quasistatic frictional contact problem with damage in viscoelasticity

We consider a quasistatic problem which models the bilateral contact between a viscoelastic body and a foundation, taking into account the damage and the friction. The damage which results from tension or compression is then involved in the constitutive law and it is modelled using a nonlinear parabolic inclusion. The variational problem is formulated as a coupled system of evolutionary equations for which we state the existence of a unique solution. Then, we introduce a fully discrete scheme using the finite element method to approximate the spatial variable and the Euler scheme to discretize the time derivatives. Error estimates are derived and, under suitable regularity hypotheses, the convergence of the numerical scheme obtained. Finally, a numerical algorithm and results are presented for some two-dimensional examples.     

A posteriori error estimates for discontinuous Galerkin method to the elasticity problem

This work concerns with the discontinuous Galerkin (DG) method for the time‐dependent linear elasticity problem. We derive the a posteriori error bounds for semidiscrete and fully discrete problems, by making use of the stationary elasticity reconstruction technique which allows to estimate the error for time‐dependent problem through the error estimation of the associated stationary elasticity problem. For fully discrete scheme, we make use of the backward‐Euler scheme and an appropriate space‐time reconstruction. The technique here can be applicable for a variety of DG methods as well.