Parallel execution of embedded and iterated Runge–Kutta methods

In this paper, we consider the parallel solution of non-stiff ordinary differential equations with two different classes of Runge–Kutta (RK) methods providing embedded solutions: classical embedded RK methods and iterated RK methods which were constructed especially for parallel execution. For embedded Runge–Kutta methods, mainly the potential system parallelism is exploited. Iterated RK methods provide an additional source of parallelism in the form of independent function evaluations, but they usually require a higher number of function evaluations. We put the emphasis on the parallel execution time of these methods. Copyright © 1999 John Wiley & Sons, Ltd.     

Stability of explicit Runge—Kutta methods

The classical theory of stability of explicit Runge—Kutta methods is concerned with Lipschitzian problems. It is not useful for stable problems with “large” Lipschitz constants. The classical theory of absolute stability considers some very special problems of this kind. The problems treated arise when a general problem is linearized. It is hoped that the behavior in the case of the special problem provide guidelines as to the behavior in the case of a general problem. A synthesis is proposed here which responds to this unsatisfactory state of affairs in the classical theory.     

Error analysis of variable stepsize Runge–Kutta methods for a class of multiply-stiff singular perturbation problems

In this paper, we present some results on the error behavior of variable stepsize stiffly-accurate Runge–Kutta methods applied to a class of multiply-stiff initial value problems of ordinary differential equations in singular perturbation form, under some weak assumptions on the coefficients of the considered methods. It is shown that the obtained convergence results hold for stiffly-accurate Runge–Kutta methods which are not algebraically stable or diagonally stable. Some results on the existence and uniqueness of the solution of Runge–Kutta equations are also presented.     

基于四阶循环多谱的频谱感知算法

目前,大部分基于能量检测和信号循环平稳的频谱感知算法能够在平稳噪声环境中取得优异的检测性能,在非平稳噪声环境中的检测性能则急剧下降。为了更好地消除频谱感知过程中非平稳噪声的影响,利用信号四阶循环多谱抑制非平稳噪声的性质,提出了一种基于四阶循环多谱的频谱感知算法。该算法首先计算四阶循环多谱的切片形式;然后通过简化的四阶循环多谱幅度平方和对协同用户截取的信号进行检测;最后计算其峰值系数,实现对主用户信号存在性的判断。仿真结果表明,在非平稳噪声环境中,所提出的算法比传统的频谱感知算法识别概率更高,性能更好。     

Construction of the ef-based Runge–Kutta methods revisited

The purpose of this paper is to revisit the exponential fitting (ef) technique when building up Runge–Kutta methods for solving ordinary differential equations. We propose a modification in such a way that the contamination of the final stage by the errors produced in the internal stages becomes visible. The modified technique is illustrated on a simple version, namely the two-stage explicit Runge–Kutta method, for which we obtain new expressions for the coefficients. The version obtained in this way is then compared for accuracy and stability with that obtained by means of the standard ef technique.     

Improvements to Burrows–Wheeler compression algorithm

In 1994 Burrows and Wheeler presented a new algorithm for lossless data compression. The compression ratio that can be achieved using their algorithm is comparable with the best known other algorithms, whilst its complexity is relatively small. In this paper we explain the internals of this algorithm and discuss its various modifications that have been presented so far. Then we propose new improvements for its effectiveness. They allow us to obtain a compression ratio equal to 2.271 bpc for the Calgary Corpus files, which is the best result in the class of Burrows–Wheeler transform based algorithms. Copyright © 2000 John Wiley & Sons, Ltd.     

Symmetric and symplectic exponentially fitted Runge–Kutta methods of high order

The construction of high order symmetric, symplectic and exponentially fitted Runge–Kutta (RK) methods for the numerical integration of Hamiltonian systems with oscillatory solutions is analyzed. Based on the symplecticness, symmetry, and exponential fitting properties, three new four-stage RK integrators, either with fixed- or variable-nodes, are constructed. The algebraic order of the new integrators is also studied, showing that they possess eighth-order of accuracy as the classical four-stage RK Gauss method. Numerical experiments with some oscillatory test problems are presented to show that the new methods are more efficient than other symplectic four-stage eighth-order RK Gauss codes proposed in the scientific literature.     

A fourth-order algorithm with automatic stepsize control for thetransient analysis of DSPNs

This paper presents an efficient and numerically reliable method for the transient analysis of deterministic and stochastic Petri nets. The transient behavior is described by state equations derived by the method of supplementary variables. Significant features of the proposed solution algorithm of fourth order are an automatic stepsize control and a two-stage relative error control. Furthermore, a formal way of dealing with discontinuities in the transient state equations is developed. This resolves the problems posed by initially enabled deterministic transitions and also improves the accuracy of numerical results. Experiments with a queueing system with failure and repair illustrate the efficiency (with respect to both CPU-time and memory space) and the numerical quality of the new algorithm     

A sensitivity formula for risk-sensitive cost and the actor–critic algorithm

We propose for risk sensitive control of finite Markov chains a counterpart of the popular ‘actor–critic’ algorithm for classical Markov decision processes. The algorithm is based on a ‘sensitivity formula’ for the risk sensitive cost and is shown to converge with probability one to the desired solution. The proof technique is an adaptation of the ordinary differential equations approach for the analysis of two time-scale stochastic approximation algorithms.     

A particle swarm optimization algorithm for part–machine grouping

Although in the last years different metaheuristic methods have been used to solve the cell formation problem in group technology, this paper presents the first particle swarm optimization (PSO) algorithm designed to address this problem. PSO is a population-based evolutionary computation technique based on a social behavior metaphor. The criterion used to group the machines in cells is based on the minimization of inter-cell movements. A maximum cell size is imposed. Some published exact results have been used as benchmarks to assess the proposed algorithm. The computational results show that the PSO algorithm is able to find the optimal solutions on almost all instances.     

Post BWT stages of the Burrows–Wheeler compression algorithm

The lossless Burrows–Wheeler compression algorithm has received considerable attention over recent years for both its simplicity and effectiveness. It is based on a permutation of the input sequence—the Burrows–Wheeler transformation (BWT)—which groups symbols with a similar context close together. In the original version, this permutation was followed by a Move‐To‐Front transformation and a final entropy coding stage. Later versions used different algorithms, placed after the BWT, since the following stages have a significant influence on the compression rate. This paper describes different algorithms and improvements for these post BWT stages including a new context‐based approach. The results for compression rates are presented together with compression and decompression times on the Calgary corpus, the Canterbury corpus, the large Canterbury corpus and the Lukas 2D 16‐bit medical image corpus. Copyright © 2010 John Wiley & Sons, Ltd.     

Second step algorithms in the Burrows–Wheeler compression algorithm

In this paper we focus our attention on the second step algorithms of the Burrows–Wheeler compression algorithm, which in the original version is the Move To Front transform. We discuss many of its replacements presented so far, and compare compression results obtained using these replacements. Then we propose a new algorithm that yields a better compression ratio than the previous algorithms. Copyright © 2001 John Wiley & Sons, Ltd.     

Generalized Needleman–Wunsch algorithm for the recognition of T-cell epitopes

In this paper, we propose a new encoding technique that combines the different physicochemical properties of amino acids together with Needleman–Wunsch algorithm. The algorithm was tested in the recognition of T-cell epitopes. A series of SVM classifiers, where each SVM is trained using a different physicochemical property, combined with the “max rule” enables us to obtain an improvement over the state-of-the-art approaches.     

Extended Ho–Kalman algorithm for systems represented in generalized orthonormal bases

This paper considers the construction of minimal state space models of linear time-invariant systems on the basis of system representations in terms of generalized orthogonal basis function expansions. Starting from the classical Ho–Kalman algorithm that solves the problem using Markov parameter expansions, a generalization is obtained by analysing the matrix representations of the Hankel operators in generalized orthonormal bases. Using the so-called Hambo-domain techniques an efficient algorithm is given to implement the proposed method.     

Extended Games–Chan algorithm for the 2-adic complexity of FCSR-sequences

Binary sequences generated by feedback shift registers with carry operation (FCSR) share many of the important properties enjoyed by sequences generated by linear feedback shift registers. We present an FCSR analog of the (extended) Games–Chan algorithm, which efficiently determines the linear complexity of a periodic binary sequence with period length T = 2ⁿ or pⁿ, where p is an odd prime and 2 is a primitive element modulo p². The algorithm to be presented yields an upper bound for the 2-adic complexity, an FCSR analog of the linear complexity, of a pⁿ-periodic binary sequence.     

A scheduling quasi–min-max model predictive control algorithm for nonlinear systems

In this paper, a model predictive control algorithm is designed for nonlinear systems. Combination of a linear model with a linear parameter varying model approximates the nonlinear behavior. The linear model is used to express the current nonlinear dynamics, and the linear parameter varying model is used to cover the future nonlinear behavior. In the algorithm, a “quasi-worst-case” value of an infinite horizon objective function is minimized. Closed-loop stability is guaranteed when the algorithm is implemented in a receding horizon fashion by including a Lyapunov constraint in the formulation. The proposed approach is applied to control a jacketed styrene polymerization reactor.     

A multiobjective GRASP–VND algorithm to solve the waste collection problem

In this paper, the waste collection problem (WCP) of a city in the south of Spain is addressed as a multiobjective routing problem that considers three objectives. From the company's perspective, the minimization of the travel cost is desired as well as that of the total number of vehicles. Additionally, from the employee's point of view, a set of balanced routes is also sought. Four variants of a multiobjective hybrid algorithm are proposed. Specifically, a GRASP (greedy randomized adaptive search procedure) with a VND (variable neighborhood descent) is combined. The best GRASP–VND algorithm found is applied in order to solve the real‐world WCP of a city in the south of Spain.     

Computational experience with an algorithm for 0–1 integer programming

In a previous paper in this journal, the authors described an implicit enumeration algorithm for the all integer programming problem. In this paper, a specialization of the aforementioned algorithm for 0–1 integer programming problems is developed. The computational efficiency of this specialization is investigated by solving a set of test problems, using a computer code of the algorithm written for this purpose.     

Size optimization of space trusses using Big Bang–Big Crunch algorithm

A Hybrid Big Bang–Big Crunch (HBB–BC) optimization algorithm is employed for optimal design of truss structures. HBB–BC is compared to Big Bang–Big Crunch (BB–BC) method and other optimization methods including Genetic Algorithm, Ant Colony Optimization, Particle Swarm Optimization and Harmony Search. Numerical results demonstrate the efficiency and robustness of the HBB–BC method compared to other heuristic algorithms.     

Time second-order finite difference/finite element algorithm for nonlinear time-fractional diffusion problem with fourth-order derivative term

In this article, we study and analyze a Galerkin mixed finite element (MFE) method combined with time second-order discrete scheme for solving nonlinear time fractional diffusion equation with fourth-order derivative term. We firstly introduce an auxiliary variable $\sigma =△u$, reduce the fourth-order problem into a coupled system with two equations, discretize the obtained coupled system at time $t_{k?\frac{\alpha }{2}}$ by a second-order difference scheme with second-order approximation for fractional derivative, then formulate mixed weak formulation and fully discrete MFE scheme. Further, we give the detailed proof for stability of scheme, the existence and uniqueness of MFE solution, and a priori error estimates. Finally, by some numerical computations, we test the theoretical results, which illustrate that we can obtain the numerical results for two variables, moreover, we arrive at second-order time convergence orders, which are higher than the ones yielded by the $L1$-approximation.