Linearly implicit quantization-based integration methods for stiff ordinary differential equations

In this paper, new integration methods for stiff ordinary differential equations (ODEs) are developed. Following the idea of quantization-based integration (QBI), i.e., replacing the time discretization by state quantization, the proposed algorithms generalize the idea of linearly implicit algorithms. Also, the implementation of the new algorithms in a DEVS simulation tool is discussed. The efficiency of these new methods is verified by comparing their performance in the simulation of two benchmark problems with that of other numerical stiff ODE solvers. In particular, the advantages of these new algorithms for the simulation of electronic circuits are demonstrated.     

Second-order stabilized explicit Runge-Kutta methods for stiff problems

Stabilized Runge-Kutta methods (they have also been called Chebyshev-Runge-Kutta methods) are explicit methods with extended stability domains, usually along the negative real axis. They are easy to use (they do not require algebra routines) and are especially suited for MOL discretizations of two- and three-dimensional parabolic partial differential equations. Previous codes based on stabilized Runge-Kutta algorithms were tested with mildly stiff problems. In this paper we show that they have some difficulties to solve efficiently problems where the eigenvalues are very large in absolute value (over 10⁵). We also develop a new procedure to build this kind of algorithms and we derive second-order methods with up to 320 stages and good stability properties. These methods are efficient numerical integrators of very large stiff ordinary differential equations. Numerical experiments support the effectiveness of the new algorithms compared to well-known methods as RKC, ROCK2, DUMKA3 and ROCK4.     

Numerical integration of semidiscrete evolution systems

Methods and algorithms for integrating initial value systems are examined. Of particular interest is efficient and accurate numerical integration of systems of ordinary differential equations that arise on semidiscrete spatial differencing or finite element projection for evolution problems characterized by partial differential equations. Integration schemes for general systems are described. Stiff and oscillatory systems are considered and these motivate selection of specific types of algorithms for certain problem classes. For example, we show that Runge-Kutta methods with extended regions of stability are particularly efficient for moderately stiff dissipative systems derived from parabolic transport equations. The theoretical developments of an earlier paper [1] determine bounds on stiffness and stability and may be used to examine the stiff dissipative or oscillatory nature of the system qualitatively. Order control and stepsize adjustment in variable-order, variable-step algorithms are compared for several integrators applied to stiff and nonstiff initial-value systems arising from representative parabolic evolution problems.     

Inexact Methods in the Numerical Solution of Stiff Initial Value Problems

Inexact Newton methods can be effectively used in codes for large stiff initial value problems for ordinary differential equations. In this paper we give a new convergence result for Inexact Newton methods. Further, we indicate how this general result can be used and actually implemented to obtain an efficient code for solving stiff initial value problems. Received: March 12, 1998; revised March 31, 1999     

Solving stiff differential equations for simulation

Computer simulation of dynamic systems very often leads to the solution of a set of stiff ordinary differential equations. The solution of this set of equations involves the eigenvalues of its Jacobian matrix. The greater the spread in eigenvalues, the more time consuming the solutions become when existing numerical methods are employed. Extremely stiff differential equations can become a very serious problem for some systems, rendering accurate numerical solutions completely uneconomic. In this paper, we propose new techniques for solving extremely stiff systems of differential equations. These algorithms are based on a class of implicit Runge-Kutta procedure with complete error estimate. The new techniques are applied to solving mathematical models of the relaxation problem behind blast waves.     

Asymptotic error expansions for stiff equations: Applications

In a series of foregoing papers we have studied the structure of the global discretization error for the implicit Euler scheme and the implicit midpoint and trapezoidal rules applied to a general class of nonlinear stiff initial value problems. Full asymptotic error expansions (in the conventional sense) exist only in special situations; for the general case, asymptotic expansions in a weaker sense have been derived. In the present paper we demonstrate how these results can be used for an analysis of acceleration techniques applied to stiff problems. In particular, extrapolation and defect correction algorithms are considered. Various numerical results are presented and discussed.     

Comparison of two algorithms for solving STIFF differential equations

Many algorithms are available for solving differential equations. Of these, two methods—GEAR and STIFF3, which were developed specifically for stiff differential equations, are compared based on their performance on five test problems. The performance criteria are both accuracy of the numerical solution and efficiency of the method. The results indicate that GEAR, although the older of the two methods, is the preferred algorithm, for stiff differential equations.     

Parametric Evaluation of Routing Algorithms in Network on Chip Architecture

Considering that routing algorithms for the Network on Chip (NoC) architecture is one of the key issues that determine its ultimate performance, several things have to be considered for developing new routing algorithms. This includes examining the strengths, capabilities, and weaknesses of the commonly proposed algorithms as a starting point for developing new ones.
Because most of the algorithms presented are based on the well-known algorithms that are studied and evaluated in this research. Finally, according to the results produced under different conditions, better decisions can be made when using the aforementioned algorithms as well as when presenting new routing algorithms. In this research, we first describe the existing algorithms include: XY, YX, Odd- Even and DyAD. We then evaluate each of the routing algorithms which naturally have their own strengths and weaknesses under different conditions. In the first scenario, based on the criteria of average latency, average throughput and average energy consumption in determining the final performance of the network on the chip, we show the algorithms in terms of their performance by deterministic and adaptive routing algorithms. In the second scenario, we evaluate the algorithms based on the network size and the number of cores on the chip. As a result, these algorithms can make better decisions when using these algorithms as well as when presenting new routing algorithms, considering the results produced under different condition.     

A comparative evaluation of DRE integration algorithms for real-time simulation of biologically activated sludge process

An activated sludge process is considered in this work for comparative tests of new integration algorithms. Based on the configuration of the process and on the process kinetics for heterotrophic bacterial growth, the mathematical model of the considered process has been derived in the form of a state ordinary differential equation system. The state ordinary differential equation system describing the considered process may be both stiff and non-stiff for operator's control changes of the oxygen feeding flow rate. In the work, new discrete response equivalent (DRE) integration algorithms are proposed for simulation runs with a fixed integration step size, which is independent of the process dynamics (this possibility is due to self-adaptive features of the algorithms). The proposed algorithms have been compared with most other frequently used integration algorithms. The comparative tests show that, among the compared algorithms, only the DRE integration algorithms may be used with a fixed, arbitrarily chosen integration step size for simulation of the state ordinary differential equation system which may be both stiff and non-stiff during simulation.     

Solving Initial Value Problems for Ordinary Differential Equations by two approaches: BDF and piecewise-linearized methods

Many scientific and engineering problems are described using Ordinary Differential Equations (ODEs), where the analytic solution is unknown. Much research has been done by the scientific community on developing numerical methods which can provide an approximate solution of the original ODE. In this work, two approaches have been considered based on BDF and Piecewise-linearized Methods. The approach based on BDF methods uses a Chord-Shamanskii iteration for computing the nonlinear system which is obtained when the BDF schema is used. Two approaches based on piecewise-linearized methods have also been considered. These approaches are based on a theorem proved in this paper which allows to compute the approximate solution at each time step by means of a block-oriented method based on diagonal Padé approximations. The difference between these implementations is in using or not using the scale and squaring technique.Five algorithms based on these approaches have been developed. MATLAB and Fortran versions of the above algorithms have been developed, comparing both precision and computational costs. BLAS and LAPACK libraries have been used in Fortran implementations. In order to compare in equality of conditions all implementations, algorithms with fixed step have been considered. Four of the five case studies analyzed come from biology and chemical kinetics stiff problems. Experimental results show the advantages of the proposed algorithms, especially when they are integrating stiff problems.     

A new variable step size block backward differentiation formula for solving stiff initial value problems

A new block backward differentiation formula of order 4 with variable step size is formulated. By varying a parameter in the formula, different sets of formulae with A-stability property can be generated. At the cost of an additional function evaluation, the accuracy of the method is seen to outperform some existing backward differentiation formula algorithms. The strategy involved in controlling the step size ratio is also described. The problems tested with the method show its efficiency in solving stiff initial value problems.     

Rational one-step methods for initial value problems

First, second and third order explicit nonlinear one-step methods are proposed for singular and stiff initial value problems (ivp's). The algorithms are based on the representation of the solution by a finite continued fraction. Numerical examples are provided to illustrate the algorithms.     

ADER Schemes for Nonlinear Systems of Stiff Advection�CDiffusion�CReaction Equations

In this article we extend the high order ADER finite volume schemes introduced for stiff hyperbolic balance laws by Dumbser, Enaux and Toro (J. Comput. Phys. 227:3971?C4001, 2008) to nonlinear systems of advection?Cdiffusion?Creaction equations with stiff algebraic source terms. We derive a new efficient formulation of the local space-time discontinuous Galerkin predictor using a nodal approach whose interpolation points are tensor-products of Gauss?CLegendre quadrature points. Furthermore, we propose a new simple and efficient strategy to compute the initial guess of the locally implicit space-time DG scheme: the Gauss?CLegendre points are initialized sequentially in time by a second order accurate MUSCL-type approach for the flux term combined with a Crank?CNicholson method for the stiff source terms. We provide numerical evidence that when starting with this initial guess, the final iterative scheme for the solution of the nonlinear algebraic equations of the local space-time DG predictor method becomes more efficient. We apply our new numerical method to some systems of advection?Cdiffusion?Creaction equations with particular emphasis on the asymptotic preserving property for linear model systems and the compressible Navier?CStokes equations with chemical reactions.     

Model Checking Semi-Continuous Time Models Using BDDs

The verification of timed systems is extremely important, but also extremely difficult. Several methods have been proposed to assist in this task, including extensions to symbolic model checking. One possible use of model checking to analyze timed systems is by modeling passage of time as the number of taken transitions and applying quantitative algorithms to determine the timing parameters of the system. The advantage of this method is its simplicity and efficiency. In this paper we extend this technique in two ways. First, we present new quantitative algorithms that are more efficient than their predecessors. The new algorithms determine the number of occurrences of events in all paths between a set of starting states and a set of final states. We then use these algorithms to introduce a new model of time, in which the passage of time is dissociated from the occurrence of events. With this new model it is possible to verify systems that were previously thought to require dense time models. We use the new method to verify two such examples previously analyzed by the HyTech tool: a steam boiler example and a fuel injection controller.     

An improved initial basis for the Simplex algorithm

A lot of research has been done to find a faster (polynomial) algorithm that can solve linear programming (LP) problems. The main branch of this research has been devoted to interior point methods (IPM). The IPM outperforms the Simplex method in large LPs. However, there is still much research being done in order to improve pivoting algorithms. In this paper, we present a new approach to the problem of improving the pivoting algorithms: instead of starting the Simplex with the canonical basis, we suggest as initial basis a vertex of the feasible region that is much closer to the optimal vertex than the initial solution adopted by the Simplex. By supplying the Simplex with a better initial basis, we were able to improve the iteration number efficiency of the Simplex algorithm in about 33%.     

Split-step Adams–Moulton Milstein methods for systems of stiff stochastic differential equations

In this paper we discuss new split-step methods for solving systems of Itô stochastic differential equations (SDEs). The methods are based on a L-stable (strongly stable) second-order split Adams–Moulton Formula for stiff ordinary differential equations in collusion with Milstein methods for use on SDEs which are stiff in both the deterministic and stochastic components. The L-stability property is particularly useful when the drift components are stiff and contain widely varying decay constants. For SDEs wherein the diffusion is especially stiff, we consider balanced and modified balanced split-step methods which posses larger regions of mean-square stability. Strong order convergence one is established and stability regions are displayed. The methods are tested on problems with one and two noise channels. Numerical results show the effectiveness of the methods in the pathwise approximation of stiff SDEs when compared to some existing split-step methods.     

A note on optimal policies for two group scheduling problems with deteriorating setup and processing times

Conventionally, job processing times are known and fixed. However, there are many situations where the job processing time deteriorates as time passes. In this note, we consider the makespan problems under the group technology with deteriorating setup and processing times. That is, the job processing times and group setup times are linearly increasing (or decreasing) functions of their starting times. For both linear functions, we show that the makespan problems remain polynomially solvable. In addition, the constructive algorithms are also provided.     

Convergence Results of One-Leg and Linear Multistep Methods for Multiply Stiff Singular Perturbation Problems

One-leg methods and linear multistep methods are two class of important numerical methods applied to stiff initial value problems of ordinary differential equations. The purpose of this paper is to present some convergence results of A-stable one-leg and linear multistep methods for one-parameter multiply stiff singular perturbation problems and their corresponding reduced problems which are a class of stiff differential-algebraic equations. Received April 14, 2000; revised June 30, 2000     

Adapted BDF Algorithms: Higher-order Methods and Their Stability

We present BDF type formulas of high-order (4, 5 and 6), capable of the exact integration (with only round-off errors) of differential equations whose solutions are linear combinations of an exponential with parameter A and ordinary polynomials. For A = 0, the new formulas reduce to the classical BDF formulas. Theorems of the local truncation error reveal the good behavior of the new methods with stiff problems. Plots of their 0-stability regions in terms of the eigenvalues of the parameter A h are provided. Plots of their absolute stability regions that include the whole of the negative real axis are provided. The weights of the method usually require the evaluation of a matrix exponential. However, if the dimension of the matrix is large, we shall not perform this calculus and shall only approximate those coefficients once. Numerical examples underscore the efficiency of the proposed codes, especially when one is integrating stiff oscillatory problems.      

Monotone Finite Volume Schemes for Diffusion Equation with Imperfect Interface on Distorted Meshes

In this paper we consider the numerical solution of stiff problems in which the eigenvalues are separated into two clusters, one containing the “stiff”, or fast, components and one containing the slow components, that is, there is a gap in their eigenvalue spectrum. By using exponential fitting techniques we develop a class of explicit Runge–Kutta methods, that we call stability fitted methods, for which the stability domain has two regions, one close to the origin and the other one fitting the large eigenvalues. We obtain the size of their stability regions as a function of the order and the fitting conditions. We also obtain conditions that the coefficients of these methods must satisfy to have a given stiff order for the Prothero–Robinson test equation. Finally, we construct an embedded pair of stability fitted methods of orders 2 and 1 and show its performance by means of several numerical experiments.