The Waveform Relaxation method for systems of differential/algebraic equations

This paper reports efforts towards establishing a parallel numerical algorithm known as Waveform Relaxation (WR) for simulating large systems of differential/algebraic equations. The WR algorithm was established as a relaxation based iterative method for the numerical integration of systems of ODEs over a finite time interval. In the WR approach, the system is broken into subsystems which are solved independently, with each subsystem using the previous iterate waveform as “guesses” about the behavior of the state variables in other subsystems. Waveforms are then exchanged between subsystems, and the subsystems are then resolved repeatedly with this improved information about the other subsystems until convergence is achieved.

In this paper, a WR algorithm is introduced for the simulation of generalized high-index DAE systems. As with ODEs, DAE systems often exhibit a multirate behavior in which the states vary as differing speeds. This can be exploited by partitioning the system into subsystems as in the WR for ODEs. One additional benefit of partitioning the DAE system into subsystems is that some of the resulting subsystems may be of lower index and, therefore, do not suffer from the numerical complications that high-index systems do. These lower index subsystems may therefore be solved by less specialized simulations. This increases the efficiency of the simulation since only a portion of the problem must be solved with specially tailored code. In addition, this paper established solvability requirements and convergence theorems for varying index DAE systems for WR simulation.     

Adaptive partitioning techniques for index 1 IDEs

Many implicit differential equations (IDEs) modelling practical problems can be partitioned into loosely coupled subsystems. In this paper the objective of the partitioning is to permit the numerical integration of one time step to be performed as the solution of a sequence of small subproblems. This reduces the computational complexity compared to solving one large system and permits efficient parallel execution under appropriate conditions. The subsystems are integrated using methods based on low order backward differentiation formulas.     

Parallel algorithms for solving nonlinear two-point boundary-value problems which arise in optimal control

This paper describes a collection of parallel optimal control algorithms which are suitable for implementation on an advanced computer with the facility for large-scale parallel processing. Specifically, a parallel nongradient algorithm and a parallel variablemetric algorithm are used to search for the initial costate vector that defines the solution to the optimal control problem. To avoid the computational problems sometimes associated with simultaneous forward integration of both the state and costate equations, a parallel shooting procedure based upon partitioning of the integration interval is considered. To further speed computations, parallel integration methods are proposed. Application of this all-parallel procedure to a forced Van der Pol system indicates that convergence time is significantly less than that required by highly efficient serial procedures.This research was supported in part by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-77-3418.     

Adaptive Model Reduction for Chemical Kinetics

An adaptive model reduction algorithm is proposed for systems of ODEs from chemical kinetics. Its goal is to provide an accurate approximation to the solution of these systems faster than could be obtained through straightforward numerical integration. The algorithm approximates a system with a sequence of reduced models, each one appropriate to the dynamics of the system during a period of the trajectory. Reduced models are identical to the original system except for the deletion of some chemical reactions. This saves the cost of computing unimportant reaction coefficients. Both the reduced models and the durations for which they are used are selected adaptively in order to efficiently yield an accurate approximate solution. The performance of the algorithm is assessed through numerical experiments.     

偏微分方程的区间小波自适应精细积分法

利用插值小波理论构造了拟Shannon区间小波,并结合外推法给出了一种求解非线性常微分方程组的时间步长自适应精细积分法,在此基础上构造了求解非线性偏微分方程的区间小波自适应精细积分法（AIWPIM）．数值结果表明,该方法在计算精度上优于将小波和四阶Runge-Kutta法组合得到的偏微分方程的数值求解方法,而计算量则相差不大．该文方法通过Burgers方程给出,但适用于一般情形．     

A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem

In this paper, we describe a generalization of the multidimensional two-way number partitioning problem (MDTWNPP) where a set of vectors has to be partitioned into p sets (parts) such that the sums per every coordinate should be exactly or approximately equal. We will call this generalization the multidimensional multi-way number partitioning problem (MDMWNPP). Also, an efficient memetic algorithm (MA) heuristic is developed to solve the multidimensional multi-way number partitioning problem obtained by combining a genetic algorithm (GA) with a powerful local search (LS) procedure. The performances of our memetic algorithm have been compared with the existing numerical results obtained by CPLEX based on an integer linear programming formulation of the problem. The solution reveals that our proposed methodology performs very well in terms of both quality of the solutions obtained and the computational time compared with the previous method of solving the multidimensional two-way number partitioning problem.     

Backward error analysis for multi-symplectic integration methods

Summary. A useful method for understanding discretization error in the numerical solution of ODEs is to compare the system of ODEs with the modified equations obtained through backward error analysis, and using symplectic integration for Hamiltonian ODEs provides more incite into the modified equations. In this paper, the ideas of symplectic integration are extended to Hamiltonian PDEs, and this paves the way for the development of a local modified equation analysis solely as a useful diagnostic tool for the study of these types of discretizations. In particular, local conservation laws of energy and momentum are not preserved exactly when symplectic integrators are used to discretize, but the modified equations are used to derive modified conservation laws that are preserved to higher order along the numerical solution. These results are also applied to the nonlinear wave equation. Mathematics Subject Classification (1991):65M06, 65P10, 37K05     

Online identification of Takagi–Sugeno fuzzy models based on self-adaptive hierarchical particle swarm optimization algorithm

This paper presents an approach for online learning of Takagi–Sugeno (T-S) fuzzy models. A novel learning algorithm based on a Hierarchical Particle Swarm Optimization (HPSO) is introduced to automatically extract all fuzzy logic system (FLS)’s parameters of a T–S fuzzy model. During online operation, both the consequent parameters of the T–S fuzzy model and the PSO inertia weight are continually updated when new data becomes available. By applying this concept to the learning algorithm, a new type T–S fuzzy modeling approach is constructed where the proposed HPSO algorithm includes an adaptive procedure and becomes a self-adaptive HPSO (S-AHPSO) algorithm usable in real-time processes. To improve the computational time of the proposed HPSO, particles positions are initialized by using an efficient unsupervised fuzzy clustering algorithm (UFCA). The UFCA combines the K-nearest neighbour and fuzzy C-means methods into a fuzzy modeling method for partitioning of the input–output data and identifying the antecedent parameters of the fuzzy system, enhancing the HPSO’s tuning. The approach is applied to identify the dynamical behavior of the dissolved oxygen concentration in an activated sludge reactor within a wastewater treatment plant. The results show that the proposed approach can identify nonlinear systems satisfactorily, and reveal superior performance of the proposed methods when compared with other state of the art methods. Moreover, the methodologies proposed in this paper can be involved in wider applications in a number of fields such as model predictive control, direct controller design, unsupervised clustering, motion detection, and robotics.     

A parallel solver for adaptive finite element discretizations

A parallel solver for the adaptive finite element analysis is presented. The primary aim of this work has been to establish an efficient parallel computational procedure which requires only local computations to update the solution of the system of equations arising from the finite element discretization after a local mesh-adaptation step. For this reason a set of algorithms has been developed (two-level domain decomposition, recursive hierarchical mesh-refinement, selective solution-update of linear systems of equations) which operate upon general and easily available partitioning, meshing and linear systems solving algorithms. AMS subject classification 15A23, 65N50, 65N60     

Optimal control of impulsive switched systems with minimum subsystem durations

This paper presents a new computational approach for solving optimal control problems governed by impulsive switched systems. Such systems consist of multiple subsystems operating in succession, with possible instantaneous state jumps occurring when the system switches from one subsystem to another. The control variables are the subsystem durations and a set of system parameters influencing the state jumps. In contrast with most other papers on the control of impulsive switched systems, we do not require every potential subsystem to be active during the time horizon (it may be optimal to delete certain subsystems, especially when the optimal number of switches is unknown). However, any active subsystem must be active for a minimum non-negligible duration of time. This restriction leads to a disjoint feasible region for the subsystem durations. The problem of choosing the subsystem durations and the system parameters to minimize a given cost function is a non-standard optimal control problem that cannot be solved using conventional techniques. By combining a time-scaling transformation and an exact penalty method, we develop a computational algorithm for solving this problem. We then demonstrate the effectiveness of this algorithm by considering a numerical example on the optimization of shrimp harvesting operations.     

Computational bounds on polynomial differential equations

In this paper we study from a computational perspective some properties of the solutions of polynomial ordinary differential equations.We consider elementary (in the sense of Analysis) discrete-time dynamical systems satisfying certain criteria of robustness. We show that those systems can be simulated with elementary and robust continuous-time dynamical systems which can be expanded into fully polynomial ordinary differential equations in Q[π]. This sets a computational lower bound on polynomial ODEs since the former class is large enough to include the dynamics of arbitrary Turing machines.We also apply the previous methods to show that the problem of determining whether the maximal interval of definition of an initial-value problem defined with polynomial ODEs is bounded or not is in general undecidable, even if the parameters of the system are computable and comparable and if the degree of the corresponding polynomial is at most 56.Combined with earlier results on the computability of solutions of polynomial ODEs, one can conclude that there is from a computational point of view a close connection between these systems and Turing machines.     

A heuristic method for non-homogeneous redundancy optimization of series-parallel multi-state systems

This paper develops an efficient heuristic to solve the non-homogeneous redundancy allocation problem for multi-state series-parallel systems. Non identical components can be used in parallel to improve the system availability by providing redundancy in subsystems. Multiple component choices are available for each subsystem. The components are binary and chosen from a list of products available on the market, and are characterized in terms of their cost, performance and availability. The objective is to determine the minimal-cost series-parallel system structure subject to a multi-state availability constraint. System availability is represented by a multi-state availability function, which extends the binary-state availability. This function is defined as the ability to satisfy consumer demand that is represented as a piecewise cumulative load curve. A fast procedure is used, based on universal generating function, to evaluate the multi-state system availability. The proposed heuristic approach is based on a combination of space partitioning, genetic algorithms (GA) and tabu search (TS). After dividing the search space into a set of disjoint subsets, this approach uses GA to select the subspaces, and applies TS to each selected subspace. The design problem, solved in this study, has been previously analyzed using GA. Numerical results for the test problems from previous research are reported, and larger test problems are randomly generated. These results show that the proposed approach is efficient both in terms of both of solution quality and computational time, as compared to existing approaches.     

Computational aspects of continuous–discrete extended Kalman-filtering

This paper elaborates how the time update of the continuous–discrete extended Kalman-filter (EKF) can be computed in the most efficient way. The specific structure of the EKF-moment differential equations leads to a hybrid integration algorithm, featuring a new Taylor–Heun-approximation of the nonlinear vector field and a modified Gauss–Legendre-scheme, generating positive semidefinite solutions for the state error covariance. Furthermore, the order of consistency and stability behavior of the outlined procedure is investigated. The results are incorporated into an algorithm with adaptive controlled step size, assuring a fixed numerical precision with minimal computational effort.     

A Parallel Algorithm for Adaptive Local Refinement of Tetrahedral Meshes Using Bisection

Local mesh refinement is one of the key steps in the implementations of adaptive finite element methods. This paper presents a parallel algorithm for distributed memory parallel computers for adaptive local refinement of tetrahedral meshes using bisection. This algorithm is used in PHG, Parallel Hierarchical Grid (http: //lsec. cc. ac. cn/phg/J, a toolbox under active development for parallel adaptive finite element solutions of partial differential equations. The algorithm proposed is characterized by allowing simultaneous refinement of submeshes to arbitrary levels before synchronization between submeshes and without the need of a central coordinator process for managing new vertices. Using the concept of canonical refinement, a simple proof of the independence of the resulting mesh on the mesh partitioning is given, which is useful in better understanding the behaviour of the bisectioning refinement procedure.AMS subject classifications: 65Y05, 65N50     

A piecewise-linearized algorithm based on the Krylov subspace for solving stiff ODEs

Numerical methods for solving Ordinary Differential Equations (ODEs) have received considerable attention in recent years. In this paper a piecewise-linearized algorithm based on Krylov subspaces for solving Initial Value Problems (IVPs) is proposed. MATLAB versions for autonomous and non-autonomous ODEs of this algorithm have been implemented. These implementations have been compared with other piecewise-linearized algorithms based on Padé approximants, recently developed by the authors of this paper, comparing both precisions and computational costs in equal conditions. Four case studies have been used in the tests that come from stiff biology and chemical kinetics problems. Experimental results show the advantages of the proposed algorithms, especially when the dimension is increased in stiff problems.     

A novel 2D partial unwinding adaptive Fourier decomposition method with application to frequency domain system identification

This paper proposes a two‐dimensional (2D) partial unwinding adaptive Fourier decomposition method to identify 2D system functions. Starting from Coifman in 2000, one‐dimensional (1D) unwinding adaptive Fourier decomposition and later a type called unwinding AFD have been being studied. They are based on the Nevanlinna factorization and a maximal selection. This method provides fast‐converging rational approximations to 1D system functions. However, in the 2D case, there is no genuine unwinding decomposition. This paper proposes a 2D partial unwinding adaptive Fourier decomposition algorithm that is based on algebraic transforms reducing a 2D case to the 1D case. The proposed algorithm enables rational approximations of real coefficients to 2D system functions of real coefficients. Its fast convergence offers efficient system identification. Numerical experiments are provided, and the advantages of the proposed method are demonstrated.     

A multirate time stepping strategy for stiff ordinary differential equations

To solve ODE systems with different time scales which are localized over the components, multirate time stepping is examined. In this paper we introduce a self-adjusting multirate time stepping strategy, in which the step size for a particular component is determined by its own local temporal variation, instead of using a single step size for the whole system. We primarily consider implicit time stepping methods, suitable for stiff or mildly stiff ODEs. Numerical results with our multirate strategy are presented for several test problems. Comparisons with the corresponding single-rate schemes show that substantial gains in computational work and CPU times can be obtained. AMS subject classification (2000)  65L05, 65L06, 65L50     

Application of multistage homotopy-perturbation method for the solutions of the Chen system

In this paper, a new reliable algorithm based on an adaptation of the standard homotopy-perturbation method (HPM) is applied to the Chen system which is a three-dimensional system of ODEs with quadratic nonlinearities. The HPM is treated as an algorithm in a sequence of intervals for finding accurate approximate solutions to the Chen system. We shall call this technique as the multistage HPM (for short MHPM). In particular we look at the accuracy of the HPM as the Chen system changes from a nonchaotic system to a chaotic one. Numerical comparisons between the MHPM and the classical fourth-order Runge–Kutta (RK4) numerical solutions reveal that the new technique is a promising tool for the nonlinear chaotic and nonchaotic systems of ODEs.     

New Algorithm for Computing LQ Suboptimal Output Feedback Gains of Decentralized Control Systems

In this paper, the problem of computing the suboptimal output feedback gains of decentralized control systems is investigated. First, the problem is formulated. Then, the gradient matrices based on the index function are derived and a new algorithm is established based on some nice properties. This algorithm shows that a suboptimal gain can be computed by solving several ordinary differential equations (ODEs). In order to find an initial condition for the ODEs, an algorithm for finding a stabilizing output feedback gain is exploited, and the convergence of this algorithm is discussed. Finally, an example is given to illustrate the proposed algorithm.     

Quadpack computation of Feynman loop integrals

The paper addresses a numerical computation of Feynman loop integrals, which are computed by an extrapolation to the limit as a parameter in the integrand tends to zero. An important objective is to achieve an automatic computation which is effective for a wide range of instances. Singular or near singular integrand behavior is handled via an adaptive partitioning of the domain, implemented in an iterated/repeated multivariate integration method. Integrand singularities possibly introduced via infrared (IR) divergence at the boundaries of the integration domain are addressed using a version of the Dqags algorithm from the integration package Quadpack, which uses an adaptive strategy combined with extrapolation. The latter is justified for a large class of problems by the underlying asymptotic expansions of the integration error. For IR divergent problems, an extrapolation scheme is presented based on dimensional regularization.