Efficient classes of Runge-Kutta methods for two-point boundary value problems

The standard approach to applying IRK methods in the solution of two-point boundary value problems involves the solution of a non-linear system ofn×s equations in order to calculate the stages of the method, wheren is the number of differential equations ands is the number of stages of the implicit Runge-Kutta method. For two-point boundary value problems, we can select a subset of the implicit Runge-Kutta methods that do not require us to solve a non-linear system; the calculation of the stages can be done explicitly, as is the case for explicit Runge-Kutta methods. However, these methods have better stability properties than the explicit Runge-Kutta methods. We have called these new formulas two-point explicit Runge-Kutta (TPERK) methods. Their most important property is that, because their stages can be computed explicity, the solution of a two-point boundary value problem can be computed more efficiently than is possible using an implicit Runge-Kutta method. We have also developed a symmetric subclass of the TPERK methods, called ATPERK methods, which exhibit a number of useful properties.     

Implementation of parallel three-point block codes for solving large systems of ordinary differential equations

The three-point fully implicit block methods are developed for solving large systems of ordinary differential equations using variable step size on a parallel shared memory computer. The methods calculate the numerical solution at three points simultaneously and are suitable for parallelization across the method. The methods are in a simple form as Adams Moulton method with the specific aim of gaining efficiency. For large problems, the parallel implementation produced a good speed-up with respect to the sequential timing and hence better efficiency for the methods developed.     

Parallel implementation of a high-order implicit collocation method for the heat equation

We combine a high-order compact finite difference approximation and collocation techniques to numerically solve the two-dimensional heat equation. The resulting method is implicit and can be parallelized with a strategy that allows parallelization across both time and space. We compare the parallel implementation of the new method with a classical implicit method, namely the Crank–Nicolson method, where the parallelization is done across space only. We find the set of conditions for which each method is more advantageous than the other. Numerical experiments are carried out on the SGI Origin 2000.     

High order A-stable numerical methods for stiff problems

Stiff problems pose special computational difficulties because explicit methods cannot solve these problems without severe limitations on the stepsize. This idea is illustrated using a contrived linear test problem and a discretized diffusion problem. Even though the Euler method can solve these problems if the stepsize is small enough, there is no such limitation for the implicit Euler method. To obtain high order A-stable methods, it is traditional to turn to Runge-Kutta methods or to linear multistep methods. Each of these has limitations of one sort or another and we consider, as a middle ground, the use of general linear (or multivalue multistage) methods. Methods possessing the property of inherent Runge-Kutta stability are identified as promising methods within this large class, and an example of one of these methods is discussed. The method in question, even though it has four stages, out-performs the implicit Euler method if sufficient accuracy is required, because of its higher order.     

Initial value problems: numerical methods and mathematics

A number of questions and results concerning Runge-Kutta and general linear methods are surveyed. These include order conditions and order bounds for Runge-Kutta methods, the A-stability of implicit Runge-Kutta methods based on Gaussian quadrature and transformation methods of implementation which lead to singly-implicit methods. The sections dealing with general linear methods include a discussion of the order conditions and an algebraic structure for carrying out order analyses as well as an introduction to a special function associated with parallel methods for stiff problems.     

Preconditioning in parallel Runge-Kutta methods for stiff initial value problems

From a theoretical point of view, Runge-Kutta methods of collocation type belong to the most attractive step-by-step methods for integrating stiff problems. These methods combine excellent stability features with the property of superconvergence at the step points. Like the initial-value problem itself, they only need the given initial value without requiring additional starting values, and therefore, are a natural discretization of the initial-value problem. On the other hand, from a practical point of view, these methods have the drawback of requiring in each step the solution of a system of equations of dimension sd, s and d being the number of stages and the dimension of the initial-value problem, respectively. In contrast, linear multistep methods, the main competitor of Runge-Kutta methods, require the solution of systems of dimension d. However, parallel computers have changed the scene and have motivated us to design parallel iteration methods for solving the implicit systems in such a way that the resulting methods become efficient step-by-step methods for integrating stiff initial-value problems.     

A-stability of Runge-Kutta methods with single and multiple nodes

This paper gives the proofs of the conjectures of Ehle [5] concerning the A-stability of classes of implicit Runge-Kutta methods. Next the attention is turned to implicit RK methods with multiple nodes (“multiderivative methods” [7]), which have the advantage that, for higher orders, the implicit system to be solved has much lower dimension. These methods, if based on Gaussian (Turan) quadrature, are shown to be A(α)-stable (α<π/2) only. Thus, in this paper, methods based on Lobatto quadrature (with multiple nodes) are constructed, which turn out to be A-stable. The coefficients are tabulated up to order 22.     

Parallel hybrid particle/finite volume algorithm for transported PDF methods employing sub-time stepping

A previously presented hybrid finite volume/particle method for the solution of the joint-velocity-frequency-composition probability density function (JPDF) transport equation in complex 3D geometries is extended for parallel computing. The parallelization strategy is based on domain decomposition. The finite volume method (FVM) and the particle method (PM) are parallelized separately and the algorithm is fully synchronous. For the FVM a standard method based on transferring data in ghost cells is used. Moreover, a subdomain interior decomposition algorithm to efficiently solve the implicit time integration for hyperbolic systems is described. The parallelization of the PM is more complicated due to the use of a sub-time stepping algorithm for the particle trajectory integration. Hereby, each particle obeys its local CFL criterion, and the covered distances per global time step can vary significantly. Therefore, an efficient algorithm which deals with this issue and has minimum communication effort was devised and implemented. Numerical tests to validate the parallel vs. the serial algorithm are presented, where also the effectiveness of the subdomain interior decomposition for the implicit time integration was investigated. A 3D dump-combustor configuration test case with about 2.5 × 10⁵ cells was used to demonstrate the good performance of the parallel algorithm. The hybrid algorithm scales well and the maximum speedup on 60 processors for this configuration was 50 (≈80% parallel efficiency).     

Efficient parallelization of a parabolized flow solver

This article describes application of our theory of parallelization of implicit ADI schemes to parabolized flows. A parallel multi-domain version of a turbulent developing flow in a straight duct (case A) and viscous flow in a curved duct (case B) are presented. Semi-implicit and explicit methods for the determination of boundary values for the auxiliary ADI functions on the interfaces between the sub-domains are utilized. Numerical runs show that the proposed algorithm is valid in the regions with rapidly varying fields of governing variables (near-entrance region for the case A, region 30°<θ<60° for the case B) as well as in the regions with slow axial modification of the flowfield. The algorithm is suitable for small transverse velocity (case A) and for transverse velocity of order of streamwise velocity (case B). A simplified version of our theoretical model of parallel efficiency is developed and utilized for optimal multidomain partitioning. Computer runs of the multi-domain code are done on a Meiko CS and on a DEC Alpha farm with PVM communication software. The predictions of parallel efficiency obtained by the model compare well with those of actual computer runs. The parallelization parameters obtained are quite different for two considered MIMD machines. This fact confirms the importance of a priori estimation of parallelization efficiency of an algorithm and correct choice of a parallel computer.     

On symmetric Runge-Kutta methods of high order

The usual characterization of symmetry for Runge-Kutta methods is that given by Stetter. In this paper an equivalent characterization of symmetry based on theW-transformation of Hairer and Wanner is proposed. Using this characterization it is simple to show symmetry for some well-known classes of high order Runge-Kutta methods which are based on quadrature formulae. It can also be used to construct a one-parameter family of symmetric and algebraically stable Runge-Kutta methods based on Lobatto quadrature. Methods constructed in this way and presented in this paper extend the known class of implicit Runge-Kutta methods of high order.     

One-step implicit methods or solving delay differential equations

Two one-step implicit methods—the second order Trapezium method and the fourth order implicit Runge-Kutta method for solving the delay differential equations (DDE) are developed. The significance of implicit methods lie in their 4-stability for ordinary differential equations. Different techniques are used to approximate the delay term. We also discuss the local truncation error estimate. Numerical examples are solved to show the effectiveness of the methods so developed.     

The interpolation property of the Runge-Kutta methods

The Runge-Kutta methods possessing the interpolation property, i.e., methods in which all coefficients belong to the interval [0, 1] are studied. Explicit and implicit methods of up to the fifth order inclusive that satisfy or almost satisfy the interpolation condition are considered.     

Parallel computation for shallow water flow: A domain decomposition approach

This paper describes a strategy for the parallelization of a finite element code for the numerical simulation of shallow water flow. The numerical scheme adopted for the discretization of the equations in the scalar algorithm is briefly described, with emphasis on the aspects concerning its porting to a parallel architecture. The parallelization strategy is of the domain decomposition type: the implicit computational kernel of the scheme, a Poisson problem, is solved by an additive Schwarz preconditioning technique within conjugate gradient iterations. Both the theoretical and the implementation aspects of the domain decomposition method are described as applied in the present context. Finally, some computational examples are shown and discussed.     

显式和对角隐式Rung-Kutta方法求解中立型泛函微分方程的非线性稳定性

本文致力于研究巴拿赫空间中非线性中立型泛函微分方程显式和对角隐式Rung-Kutta方法的稳定性．获得了一些显式和对角隐式Rung-Kutta方法求解非线性中立型泛函微分方程的数值稳定性和条件收缩性结果,数值试验验证了这些结果．     

A Parallel Implementation of the Simplex Function Minimization Routine

This paper generalizes the widely used Nelder and Mead (Comput J 7:308–313, 1965) simplex algorithm to parallel processors. Unlike most previous parallelization methods, which are based on parallelizing the tasks required to compute a specific objective function given a vector of parameters, our parallel simplex algorithm uses parallelization at the parameter level. Our parallel simplex algorithm assigns to each processor a separate vector of parameters corresponding to a point on a simplex. The processors then conduct the simplex search steps for an improved point, communicate the results, and a new simplex is formed. The advantage of this method is that our algorithm is generic and can be applied, without re-writing computer code, to any optimization problem which the non-parallel Nelder–Mead is applicable. The method is also easily scalable to any degree of parallelization up to the number of parameters. In a series of Monte Carlo experiments, we show that this parallel simplex method yields computational savings in some experiments up to three times the number of processors.     

Implementation of functional parallel typified language (FPTL) on multicore computers

A functional programming language supporting implicit parallelization of programs is described. The language is based on four operations of composition, of which three can perform parallel processing. Functional programs are represented schematically to use a dynamic parallelization algorithm. The implemented algorithms make it possible to dynamically distribute the load between processors and control the grain of parallelism. Experimental results for the efficiency of the implemented system obtained on examples of typical problems are presented.     

Singly-implicit Runge-Kutta methods for retarded and ordinary differential equations

A continuous singly-implicit Runge-Kutta method is implemented for stiff retarded differential equations. The choice of this implicit Runge-Kutta method is based on stability investigations of wide classes of interpolationintegration schemes. The numerical results show the effectiveness of these methods for both stiff ordinary and retarded differential equations.     

Interpolating Runge-Kutta methods for vanishing delay differential equations

In the numerical solution of delay differential equations by a continuous explicit Runge-Kutta method a difficulty arises when the delay vanishes or becomes smaller than the stepsize the method would like to use. In this situation the standard explicit sequential process of computing the Runge-Kutta stages becomes an implicit process and an iteration scheme must be adopted. We will consider alternative iteration schemes and investigate their order.     

Some Modified Runge-Kutta Methods for the Numerical Solution of Initial-Value Problems with Oscillating Solutions

Two new modified Runge-Kutta methods with minimal phase-lag are developed for the numerical solution of initial-value problems with oscillating solutions which can be analyzed to a system of first order ordinary differential equations. These methods are based on the well known Runge-Kutta RK5(4)7FEq1 method of Higham and Hall (1990) of order five. Also, based on the property of the phase-lag a new error control procedure is introduced. Numerical and theoretical results show that this new approach is more efficient compared with the well known Runge-Kutta Dormand-Prince RK5(4)7S method [see Dormand and Prince (1980)] and the well known Runge-Kutta RK5(4)7FEq1 method of Higham and Hall (1990).