HNUE JOURNAL OF SCIENCE
Natural Science, 2024, Volume 69, Issue 2, pp. 3-16
This paper is available online at http://hnuejs.edu.vn/ns
DOI: 10.18173/2354-1059.2024-0015
EXPLICIT PSEUDO THREE-STEP RUNGE-KUTTA METHODS
FOR NONSTIFF INITIAL VALUE PROBLEMS
Nguyen Thu Thuy
Faculty of Mathematics, Hanoi National University of Education, Hanoi city, Vietnam
Corresponding author: Nguyen Thu Thuy, e-mail: ntthuy@hnue.edu.vn
Received May 17, 2024. Revised June 16, 2024. Accepted June 23, 2024.
Abstract. This paper investigates a class of explicit pseudo three-step Runge-Kutta
methods for arbitrarily high order nonstiff initial value problems for systems
of first-order differential equations. By using collocation techniques and by
suitably choosing collocation points we can obtain a stable s-stage explicit pseudo
three-step Runge-Kutta method (EPThRK method) of order p= 2srequiring only
one effective sequential f- evaluation per step on s-processor parallel computers.
By a few widely-used test problems, we show the superiority of the new EPThRK
methods proposed in this paper over red well-known parallel PIRK codes and
efficient sequential ODEX,DOPRI5 and DOP853 codes available in the literature.
Keywords: Runge-Kutta methods, three-step methods, stability, parallelism.
1. Introduction
We consider numerical solutions of following nonstiff initial value problem (IVP)
of first-order ordinary differential equations (ODEs)
y′(t) = f(t, y(t)),y(t0) = y0, t0⩽t⩽T, (1.1)
where y,f∈Rd. The most efficient numerical methods for solving this problem are the
explicit Runge-Kutta methods (RK methods). In the literature, the sequential explicit RK
methods up to order 10 can be found in e.g., [1]-[4]. In order to exploit the facility
of parallel computers, a number of parallel RK-type methods have been investigated
in e.g., [5]-[27]. A common challenge in these mentioned papers is how to reduce,
for a given order of accuracy, the required number of sequential f-evaluations per step
by using parallel processors. In the present paper, we investigate a particular class of
numerical methods called explicit pseudo three-step RK methods (EPThRK methods)
for the numerical solution of the problem (1.1). The three-step nature of the methods
considered in this paper is similar to the two-step nature of the methods investigated
3
Nguyen TT
in [10]. The approach that we apply here is to approximate the stage values at the present
step by using the stage values from the preceding steps. By using collocation techniques,
we can obtain an s-stage EPThRK method possessing step point order p∗and stage order
q∗with s⩽p∗, q∗⩽2s, requiring sf-evaluations per step. However, each of these
sf-evaluations can be computed in parallel. Consequently, when an s-stage EPThRK
method is implemented on an s-processor computer, only one sequential f-evaluation per
step is required. The approach used in this paper can be extended to the case of special
second-order ODEs (cf. [28] ).
In Section 2, we introduce the proposed EPThRK methods. We also study their
order conditions and stability properties. In Section 3, we present numerical comparisons
of EPThRK methods with the most efficient parallel and sequential numerical codes
available in up-to-date literarture.
2. Explicit pseudo three-step Runge-Kutta methods
We suppose that an s-dimensional collocation vector c=(c1, . . . , cs)Twith distinct
abscissas ciis given. An s-stage EPThRK method for solving the problem (1.1) is
defined by
Yn,i =yn+h
s
X
j=1
bijf(tn−2+hcj,Yn−2,j)
+h
s
X
j=1
aijf(tn−1+hcj,Yn−1,j), i = 1, . . . , s, (2.1a)
yn+1 =yn+h
s
X
j=1
bjf(tn+hcj,Yn,j).(2.1b)
In Eq. (2.1),yn+1 ≈y(tn+1),yn≈y(tn),his the stepsize, the s×smatrices
A= (aij), B = (bij ), and the s-dimensional vector b= (bj)are the method parameters
matrices and vectors. The vector components Yn,j ,Yn−1,j and Yn−2,j denote the jth
vector components of the stage vectors representing numerical approximations to the
exact solutions y(tn+hcj),y(tn−1+hcj)and y(tn−2+hcj), respectively. The method
parameters matrices A, B and vector bwill be determined by order conditions (see
Section 2.1). This method is similar to a RK method but it is not a RK method. It has no
implicit relation and carries information from preceding nth, (n−1)th and (n−2)th steps,
and we, therefore, call method (2.1) the s-stage explicit pseudo three-step Runge-Kutta
method (EPThRK method) based on the collocation vector c. For convenience, we specify
this EPThRK method by the following tableau
BAcO
yn+1 bT
4
Explicit pseudo three-step Runge-Kutta methods for nonstiff initial value problems
In order to start the method (2.1), an appropriate starting procedure is needed to generate
a sufficiently accurate starting vector components Y0,j,Y1,j, j = 1, . . . , s and value y2
from y0. This can be done, for example, by using an appropriate BPIRK-type method
(cf. e.g., [19]). For the EPThRK method (2.1), at each step, we need to compute 3s
f-evaluations of f(tn−2+hcj,Yn−2,j),f(tn−1+hcj,Yn−1,j),f(tn+hcj,Yn,j ),j=
1, . . . , s. However, 2sf-evaluations of f(tn−2+hcj,Yn−2,j),f(tn−1+hcj,Yn−1,j ),j=
1, . . . , s are already available from the two preceding steps so that only sf-evaluations of
f(tn+hcj,Yn,j),j= 1, . . . , s are required. These sf-evaluations can be evaluated in
parallel on sprocessors. Consequently, the s-stage EPThRK method (2.1) implemented
on an s-processor computer, requires just one effective sequential f-evaluation per step.
The order and stage order of EPThRK method (2.1) can be studied in the same
way as the order and stage order of RK methods. Thus suppose that yn=y(tn)and
Yn−2,j =y(tn−2+hcj),Yn−1,j =y(tn−1+hcj),j= 1, . . . , s. Then we have the
following orders definition
Definition 2.1. The EPThRK method (2.1) is said to be of order p∗if
y(tn+1)−yn+1 =O(hp∗+1)
and stage order q∗=min{p∗, q}if in addition,
y(tn+hci)−Yn,i =O(hq+1), i = 1, . . . , s.
Notice that the local stage order of the method (2.1) equals q+ 1. Now in the next
section, we shall consider the order conditions for EPThRK methods.
2.1. Order conditions
In this section we consider order conditions for the EPTRK methods. For the (fixed)
stepsize h, the qth-order conditions for (2.1a)and the pth-order conditions for (2.1b)are
derived by replacing Yn−2,j,Yn−1,j ,yn,Yn,j and yn+1 by the exact solution values
y(tn−2+hcj) = y(tn+h(cj−2)),y(tn−1+hcj) = y(tn+h(cj−1)),y(tn),y(tn+hcj)
and y(tn+1) = y(tn+h), respectively. On substitution of these exact solution values into
(2.1), we are led to the relations
y(tn+hci)−y(tn)−h
s
X
j=1
bijy′(tn+h(cj−2)) (2.2a)
−h
s
X
j=1
aijy′(tn+h(cj−1)) = O(hq+1), i = 1, . . . , s
y(tn+h)−y(tn)−h
s
X
j=1
bjy′(tn+hcj) = O(hp+1).(2.2b)
5
Nguyen TT
By using the Taylor expansions in the neighbourhood of tn, we can expand the left-hand
sides of (2.1) in powers of hand obtain
q
X
l=1
C(l)
ihd
dtl
y(tn) + C(q+1)
ihd
dtq+1
y(t∗
i) = O(hq+1),(2.3a)
p
X
l=1
D(l)hd
dtl
y(tn) + D(p+1)hd
dtp+1
y(t∗) = O(hp+1),(2.3b)
where, t∗
iand t∗are suitably chosen points in the interval [tn−1, tn+1]and
C(l)
i=(ci)l
l−
s
X
j=1
bij(cj−2)l−1−
s
X
j=1
aij(cj−1)l−1, i = 1, . . . , s, (2.3c)
D(l)=1
l−
s
X
j=1
bj(cj)l−1,(2.3d)
For the order and stage order of EPThRK methods, we have the following theorem:
Theorem 2.1. If the function fis Lipschitz continuous, and if
(ci)l
l=
s
X
j=1
bij(cj−2)l−1+
s
X
j=1
aij(cj−1)l−1, i = 1, . . . , s, l = 1, . . . , q, (2.4a)
1
l=
s
X
j=1
bj(cj)l−1, l = 1, . . . , p, (2.4b)
then the EPThRK method (2.1) has order p∗=min{p, q + 1}and stage order q∗=
min{p, q}for any collocation vector c= (c1, . . . , cs)Twith distinct abscissas ci.
Proof. Suppose that yn=y(tn)and Yn−2,i =y(tn−2+hci),Yn−1,i =y(tn−1+hci),
i= 1, . . . , s. The Eq. (2.3) and (2.4) ensure that the Eq. (2.2) are satisfied, then we have
the following local order relations
y(tn+hci)−Yn,i =O(hq+1), i = 1, . . . , s. (2.5)
Furthermore
y(tn+1)−yn+1 =y(tn+1)−y(tn)−h
s
X
j=1
bjy′(tn+hcj)
+h
s
X
j=1
bj[f(tn+hcj,y(tn+hcj)) −f(tn+hcj,Yn,j )] = O(hp+1) + O(hq+2)
(2.6)
Definition (2.1) and Eq. (2.5),(2.6) give us p∗=min{p, q + 1},q∗=min{p, q}and
Theorem (2.1) is proved.
6
Explicit pseudo three-step Runge-Kutta methods for nonstiff initial value problems
In order to express the parameter vector and matrices b= (bi),B= (bij ),A=
(aij)explicitly in terms of the collocation vector c, we define the following matrices and
vector
P:=c,c2
2,c3
3,...,cs
s, P ∗:=cs+1
s+ 1,cs+2
s+ 2,...,c2s
2s,
Q:=e,(c−e),...,(c−e)s−1, Q∗:=(c−e)s,...,(c−e)2s−1,
V:=e,(c−2e),...,(c−2e)s−1, V ∗:=(c−2e)s,...,(c−2e)2s−1,
R:=e,c,c2,c3,...,cs−1,g:=1,1
2,1
3,1
4,...,1
sT.
Then the order conditions (2.4) in Theorem (2.1) for q= 2s, p =scan be presented in
the form
AQ +BV =P, (2.7a)
AQ∗+BV ∗=P∗,(2.7b)
bTR−gT= 0.(2.7c)
Since the abscissas ciof the vector care assumed to be distinct, the matrices Vand Rare
nonsingular, assuming that the matrix QV −1V∗−Q∗is also nonsingular, from (2.7), we
can write
A= (P V −1V∗−P∗)(QV −1V∗−Q∗)−1, B = (P−AQ)V−1,bT=gTR−1.(2.8)
In view of Theorem 2.1, it follows from (2.8) that
y(tn+1)−yn+1 =O(hmin{p,2s+1})
y(tn+hci)−Yn,i =O(hmin{p,2s}), i = 1, . . . , s.
Notice that the vector bdefined in (2.8) by the condition (2.7c)is the vector of weights
of the collocation implicit RK method based on collocation vector cso that pat least
equals s. With a special choice of the vector c, it is possible to increase the order p
beyond s(superconvergence) by satisfying the orthogonality relation (see [3, p. 207].
The following theorem is a direct consequence of Theorem (2.1), the explicit expressions
of the parameters of EPThRK methods and the application of the orthogonality relation.
Theorem 2.2. Suppose that c= (c1, . . . , cs)Tis a collocation vector with distinct
abscissas ciand the matrix QV −1V∗−Q∗is nonsingular, then an s-stage EPThRK method
defined by (2.1) is of order p∗⩾sand of stage order q∗⩾sif the method parameter
matrices A, B and vector bsatisfy the relations in (2.8). It has order p∗=s+rand
stage order q∗=s+rif, in addition, the following orthogonality relation is satisfied
Pj(1) = 0, Pj(x) := Zx
0
ξj−1
s
Y
i=1
(ξ−ci)dξ, j = 1, . . . , r. (2.9)
7