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.     

An energy preserving/decaying scheme for nonlinearly constrained multibody systems

Several numerical time integration methods for multibody system dynamics are described: an energy preserving scheme and three energy decaying ones, which introduce high-frequency numerical dissipation in order to annihilate the nondesired high-frequency oscillations. An exhaustive analysis of these four schemes is done, including their formulation, and energy preserving and decaying properties by taking into account the presence of nonlinear algebraic constraints and the incrementation of finite rotations. A new energy preserving/decaying scheme is developed, which is well suited for either stiff or nonstiff nonlinearly constrained multibody systems. Examples on a series of test cases show the performance of the algorithms.     

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.     

平行系统方法与复杂系统的管理和控制

提出平行系统方法的基本思想、概念和运行的基本框架，并讨论了控制系统与平行系统的关系和异同之处，平行系统是控制系统和计算机仿真随着系统复杂程度的增加以及计算技术和分析方法的进一步发展而必然迈上的一个更高的台阶，是弥补很难甚至无法对复杂系统进行精确建模和实验之不足的一种有效手段，也是对复杂系统进行管理和控制的一种可行方式。     

Partitioned and Implicit–Explicit General Linear Methods for Ordinary Differential Equations

Implicit–explicit (IMEX) time stepping methods can efficiently solve differential equations with both stiff and nonstiff components. IMEX Runge–Kutta methods and IMEX linear multistep methods have been studied in the literature. In this paper we study new implicit–explicit methods of general linear type. We develop an order conditions theory for high stage order partitioned general linear methods (GLMs) that share the same abscissae, and show that no additional coupling order conditions are needed. Consequently, GLMs offer an excellent framework for the construction of multi-method integration algorithms. Next, we propose a family of IMEX schemes based on diagonally-implicit multi-stage integration methods and construct practical schemes of order up to three. Numerical results confirm the theoretical findings.     

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.     

A computational model of time for stiff hybrid systems applied to control synthesis

Computation has quickly become of paramount importance in the design of engineered systems, both to support their features as well as their design. Tool support for high-level modeling formalisms has endowed design specifications with executable semantics. Such specifications typically include not only discrete-time and discrete-event behavior, but also continuous-time behavior that is stiff from a numerical integration perspective. The resulting stiff hybrid dynamic systems necessitate variable-step solvers to simulate the continuous-time behavior as well as solver algorithms for the simulation of discrete-time and discrete-event behavior. The combined solvers rely on complex computer code which makes it difficult to directly solve design tasks with the executable specifications. To further leverage the executable specifications in design, this work aims to formalize the semantics of stiff hybrid dynamic systems at a declarative level by removing implementation detail and only retaining ‘what’ the computer code does and not ‘how’ it does it. A stream-based approach is adopted to formalize variable-step solver semantics and to establish a computational model of time that supports discrete-time and discrete-event behavior. The corresponding declarative formalization is amenable to computational methods and it is shown how model checking can automatically generate, or synthesize, a feedforward control strategy for a stiff hybrid dynamic system. Specifically, a stamper in a surface mount device is controlled to maintain a low acceleration of the stamped component for a prescribed minimum duration of time.     

An optimal coarse-grained arc consistency algorithm

The use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algorithms for general constraints: fine-grained algorithms where the removal of a value for a variable will be propagated to the corresponding values for other variables, and coarse-grained algorithms where the removal of a value will be propagated to the related variables. One big advantage of coarse-grained algorithms, like AC-3, over fine-grained algorithms, like AC-4, is the ease of integration when implementing an algorithm in a constraint solver. However, fine-grained algorithms usually have optimal worst case time complexity while coarse-grained algorithms do not. For example, AC-3 is an algorithm with non-optimal worst case complexity although it is simple, efficient in practice, and widely used. In this paper we propose a coarse-grained algorithm, AC2001/3.1, that is worst case optimal and preserves as much as possible the ease of its integration into a solver (no heavy data structure to be maintained during search). Experimental results show that AC2001/3.1 is competitive with the best fine-grained algorithms such as AC-6. The idea behind the new algorithm can immediately be applied to obtain a path consistency algorithm that has the best-known time and space complexity. The same idea is then extended to non-binary constraints.     

Stabilized starting algorithms for collocation Runge-Kutta methods

In this paper, we propose a technique to stabilize some starting algorithms often used in the Newton-type iterations appearing when collocation Runge-Kutta methods are applied to solve stiff initial value problems. By following the ideas given in [1], we analyze the order (classical and stiff) of the new starting algorithms and pay special attention to their error amplifying functions. From the computational point of view, the new algorithms require the solution of an additional linear system per integration step, but as shown in the numerical experiments, this extra cost is compensated in most of the problems by their better stability properties.     

Recursive and Residual Algorithms for the Efficient Numerical Integration of Multi-Body Systems

In this paper a family of methods for multi-body dynamic simulation is introduced. Equations of motion are obtained using a set of Cartesian coordinates and projected onto a set of independent relative coordinates using the concept of velocity transformation. Open-chain systems are solved directly following either a fully recursive or a semi-recursive procedure. Closed-chain systems are solved in two steps; kinematic loops are opened by removing either some kinematic joints or a rigid body, and the resulting open-chain system is solved; closure-of-the-loop conditions are imposed by means of a second velocity transformation. The dynamic formalisms have been developed so as to handle both non-stiff and stiff systems. Non-stiff systems are solved by means of an Adams–Bashforth–Moulton numerical integration scheme, which requires the computation of the function derivatives. Stiff problems are integrated by using either BDF or NDF methods, which require the computation of the residual of the equations of motion and, optionally, the evaluation of the Jacobian matrix. The proposed algorithms have been implemented using an Object-Oriented Programming approach that makes it possible to re-use the source code, keeping programs smaller, cleaner and easier to maintain. Practical examples that illustrate the performance of these implementations are included. These examples have also been solved using a commercial multi-body simulation package and comparative results are included. In most cases, the algorithms here presented outperform those implemented in the commercial package, leading to important savings in terms of total computation times.     

Stochastic projective methods for simulating stiff chemical reacting systems

In this paper, stochastic projective methods are proposed to improve the stability and efficiency in simulating stiff chemical reacting systems. The efficiency of existing explicit tau-leaping methods can often severely be limited by the stiffness in the system, forcing the use of small time steps to maintain stability. The methods presented in this paper, namely stochastic projective (SP) and telescopic stochastic projective (TSP) method, can be considered as more general stochastic versions of the recently developed stable projective numerical integration methods for deterministic ordinary differential equations. SP and TSP method are developed by fully re-interpreting and extending the key projective integration steps in the deterministic regime under a stochastic context. These new stochastic methods not only automatically reduce to the original deterministic stable methods when applied to simulating ordinary differential equations, but also carry the enhanced stability property over to the stochastic regime. In some sense, the proposed methods are stochastic generalizations to their deterministic counterparts. As such, SP and TSP method can adopt a much larger effective time step than is allowed for explicit tau-leaping, leading to noticeable runtime speedup. The explicit nature of the proposed stochastic simulation methods relaxes the need for solving any coupled nonlinear systems of equations at each leaping step, making them more efficient than the implicit tau-leaping method with similar stability characteristics. The efficiency benefits of SP and TSP method over the implicit tau-leaping is expected to grow even more significantly for large complex stiff chemical systems involving hundreds of active species and beyond.     

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.     

Curvature-based grid step selection for stiff Cauchy problems

A new method of automatic step selection is proposed for the numerical integration of the Cauchy problem for ordinary differential equations. The method is based on using the geometrical characteristics (cuvature and slope) of the integral curve. Formulas have been constructed for the curvature of the integral curve for different choices of multidimensional space. In the two-dimensional case, they turn into well-known formulas, but their general multidimensional form is nontrivial. These formulas have a simple form, are convenient for practical use, and are of independent interest for the differential geometry of multidimensional spaces. For the grids constructed by our method, a procedure of step splitting is proposed that allows one to apply Richardson’s method and to calculate posterior asymptotically precise error estimation for the obtained solution (no such estimates have been found for traditional algorithms of automatic step selection). Therefore, the proposed methods demonstrate significantly superior reliability and validity of the results as compared to calculations by conventional algorithms. In the existing automatic procedures for step selection, steps can be unexpectedly reduced by 2–4 orders of magnitude for no apparent reason. This undermines the reliability of the algorithms. The cause of this phenomenon is explained. The proposed methods are especially effective for highly stiff problems, which is illustrated by examples of calculations.     

Forward,tangent linear,and adjoint Runge–Kutta methods for stiff chemical kinetic simulations

This paper investigates numerical methods for direct decoupled sensitivity and discrete adjoint sensitivity analysis of stiff systems based on implicit Runge–Kutta schemes. Efficient implementations of tangent linear and adjoint schemes are discussed for two families of methods: fully implicit three-stage Runge–Kutta and singly diagonally-implicit Runge–Kutta. High computational efficiency is attained by exploiting the sparsity patterns of the Jacobian and Hessian. Numerical experiments with a large chemical system used in atmospheric chemistry illustrate the power of the stiff Runge–Kutta integrators and their tangent linear and discrete adjoint models. Through the integration with the Kinetic PreProcessor KPP–2.2 these numerical techniques become readily available to a wide community interested in the simulation of chemical kinetic systems.     

Split-step double balanced approximation methods for stiff stochastic differential equations

In the modelling of many important problems in science and engineering we face stiff stochastic differential equations (SDEs). In this paper, a new class of split-step double balanced (SSDB) approximation methods is constructed for numerically solving systems of stiff Itô SDEs with multi-dimensional noise. In these methods, an appropriate control function has been used twice to improve the stability properties. Under global Lipschitz conditions, convergence with order one in the mean-square sense is established. Also, the mean-square stability (MS-stability) properties of the SSDB methods have been analysed for a one-dimensional linear SDE with multiplicative noise. Therefore, the MS-stability functions of SSDB methods are determined and in some special cases, their regions of MS-stability have been compared to the stability region of the original equation. Finally, simulation results confirm that the proposed methods are efficient with respect to accuracy and computational cost.     

Linearly implicit time integration methods in real-time applications: DAEs and stiff ODEs

The methods for the dynamical simulation of multi-body systems in real-time applications have to guarantee that the time integration of the equations of motion is always successfully completed within an a priori fixed sampling time interval, typically in the range of 1.0–10.0 ms. Model structure, model complexity and numerical solution methods have to be adapted to the needs of real-time simulation. Standard solvers for stiff and for constrained mechanical systems are implicit and cannot be used straightforwardly in real-time applications because of their iterative strategies to solve the nonlinear corrector equations and because of adaptive strategies for stepsize and order selection. As an alternative, we consider in the present paper noniterative fixed stepsize time integration methods for stiff ordinary differential equations (ODEs) resulting from tree-structured multi-body system models and for differential algebraic equations (DAEs) that result from multi-body system models with loop-closing constraints.     

Genetic algorithms for match-up rescheduling of the flexible manufacturing systems

Scheduling plays a vital role in ensuring the effectiveness of the production control of a flexible manufacturing system (FMS). The scheduling problem in FMS is considered to be dynamic in its nature as new orders may arrive every day. The new orders need to be integrated with the existing production schedule immediately without disturbing the performance and the stability of existing schedule. Most FMS scheduling methods reported in the literature address the static FMS scheduling problems. In this paper, rescheduling methods based on genetic algorithms are described to address arrivals of new orders. This study proposes genetic algorithms for match-up rescheduling with non-reshuffle and reshuffle strategies which accommodate new orders by manipulating the available idle times on machines and by resequencing operations, respectively. The basic idea of the match-up approach is to modify only a part of the initial schedule and to develop genetic algorithms (GAs) to generate a solution within the rescheduling horizon in such a way that both the stability and performance of the shop floor are kept. The proposed non-reshuffle and reshuffle strategies have been evaluated and the results have been compared with the total-rescheduling method.     

Improving nonlinear electronic circuit simulation

The resolution of systems of stiff differential equations is required in the transient analysis of a large electronic network simulation. Resultant stability problems and the methods used in solving first order stiff nonlinear differential equations are reviewed. An improved algorithm is presented using BDF formulas given by Brayton et al. IEEE Vol 60 (1972) pp 98–108 and has been implemented in the IMAG electronic circuit simulation program. Reducing computer time has been achieved by controlling the number of Newton iterations, the number of integration steps, and the number of Jacobian matrix evaluations without producing additional errors or instability phenomena. Experimental results are shown.     

Exponential fitting BDF-Runge-Kutta algorithms

In other papers, the authors presented exponential fitting methods of BDF type. Now, these methods are used to derive some BDF-Runge-Kutta type formulas (of second-, third- and fourth-order), 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. Theorems of the truncation error reveal the good behavior of the new methods for stiff problems. Plots of their absolute stability regions that include the whole of the negative real axis are provided. Different procedures to find the parameter of the method are proposed, using these techniques there will not be necessary to compute the exponential matrix at each step, even when nonlinear problems are integrated. Numerical examples underscore the efficiency of the proposed codes, especially when they are integrating stiff problems.     

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.