American Journal of Computational Mathematics, 2011, 1, 72-82
doi:10.4236/ajcm.2011.12008 Published Online June 2011 (http://www.scirp.org/journal/ajcm)
Strong-Stability-Preserving, K-Step, 5- to 10-Stage,
Hermite-Birkhoff Time-Discretizations of Order 12
Truong Nguyen-Ba, Huong Nguyen-Thu, Re´mi Vaillancourt
Department of Mathematics and Statistics, University of Ottawa, Ottawa, Canada
Received March 14, 2011; revised April 8, 2011; accepted April 20, 2011
Abstract
We construct optimal k-step, 5- to 10-stage, explicit, strong-stability-preserving Hermite-Birkhoff (SSP HB)
methods of order 12 with nonnegative coefficients by combining linear k-step methods of order 9 with 5- to
10-stage Runge-Kutta (RK) methods of order 4. Since these methods maintain the monotonicity property,
they are well suited for solving hyperbolic PDEs by the method of lines after a spatial discretization. It is
seen that the 8-step 7-stage HB methods have largest effective SSP coefficient among the HB methods of
order 12 on hand. On Burgers’ equations, some of the new HB methods have larger maximum effective CFL
numbers than Huang’s 7-step hybrid method of order 7, thus allowing larger step size.
Keywords: Strong Stability Preserving, Hermite-Birkhoff Method, SSP Coefficient, Time Discretization,
Method of Lines, Comparison with Other SSP Methods
1. Introduction
We are concerned with the numerical solution of initial
value problems
d(, ())
d
y
f
tyt
t, 00
()yt y. (1)
where the function
f
is such that
()()
y
tt yt , (2)
for all 0t . Here  may be a norm or, more gener-
ally, any convex functional. It is also assumed that
f
satisfies the discrete analog of (2),
(, )
nnnn
y
tf tyy ,
F
E
tt , (3)
for the forward Euler method. Here n
y is a numerical
approximation to 0 ()ytn t . We are interested in
higher-order accurate multistep HB methods that pre-
serve the monotonicity property
1
max
nnj
jk
yy


, (4)
for max 0
F
E
tt ct  whenever condition (3) holds.
Here k represents the number of previous steps used
to compute the next solution value and c, called the
SSP coefficient, depends only on the numerical integra-
tion method but not on
f
. The monotonicity property
(4) is desirable as it mimics property (2) of the true solu-
tion and prevents growth of errors.
Strong-stability-preserving (SSP) methods have been
developed to satisfy the monotonicity property (4) for
system (1) whenever condition (3) is fulfilled. The
monotonicity property is guaranteed under the maximum
time step max
F
E
tct

 . Considerable research effort
has been devoted to find numerical methods with the
largest value c among various classes of methods.
The main application of such monotonicity results are
found in the numerical solution of hyperbolic PDEs, in
particular, of conservation laws. For the one-dimensional
equation
() 0
tx
ygy

, 0 (, 0)()yxy x, (5)
the spatial derivative ()
x
g
y can be approximated by a
conservative finite difference or finite element at ,
j
x
j
1, 2,,N

, (see, for example, [1-4]). This spatialsemi-
discretization will lead to system (1) of ODEs.
In this paper, to solve system (1), we construct new
explicit, multistep, multistage, SSP general linear time-
discretization methods of order 12 with nonnegative co-
efficients. These methods, which we call SSP Hermite-
Birkhoff (SSP HB), because their construction involves
HB interpolation polynomials (see Section 2), are com-
binations of linear k-step methods of order 9 and
s
-stage RK methods of order 4. The objective of
high-order SSP HB time discretizations is to maintain the

T. NGUYEN-BA ET AL. 73
1
monotonicity property (4) while achieving higher-order
accuracy in time, perhaps with a modified CFL restric-
tion, measured here with an SSP coefficient, ()cHBks:
()
F
E
tcHBkst , (6)
The SSP coefficient, historically called CFL coeffi-
cient, describes the ratio of the strong-stability- preserv-
ing time step to the strongly-stable forward Euler time
step (see [5]). Since our arguments are based on convex
decompositions of high- order methods in terms the SSP
FE method, such high-order methods preserve SSP in
any norm once FE is shown to be strongly stable.
Several new explicit 6- to 10-stage SSP HB methods
with nonnegative coefficients presented here have been
found by computer search.
On Burgers’ equations, some of the new HB methods
have larger maximum effective CFL numbers than
Huang’s 7-step hybrid method of order 7 [6], thus al-
lowing larger step size.
In particular, no counterparts of k-step HB methods
of order 12 have been found in the literature among hy-
brid and general linear multistep methods. Moreover, the
8-step, 7-stage HB method has largest effective SSP co-
efficient among the 12th-order HB methods on hand.
Section 2 introduces 5- to 10-stage SSP HB methods.
Order conditions are listed in Section 3. Section 4 de-
rives the Shu-Osher representation of k-step 5- to
10-stage HB methods of order 12. New SSP HB methods
are formulated as solutions of optimization problems in
Section 5. Section 6 compares the effective SSP coeffi-
cients of different methods and lists several new SSP HB
methods. Numerical results for several methods applied
to Burgers’ equations are presented in Section 7. Appen-
dix A lists the Shu-Osher representation of some of the
best
H
Bks methods considered in this paper.
2. K-step,
S
-stage SSP HB Methods of
Order 12
Notation 1: The following notation will be used:
• k denotes the number of steps of a given method,
•
s
denotes the number of stages of a given method,
•
H
Bks denotes k-step,
s
-stage SSP Hermite-
Birkhoff methods of order 12,
• HMk denotes k-step SSP hybrid methods of order
7. All
H
Bks methods considered in this work are SSP
and of order 12 unless specified otherwise. Therefore the
denominations “SSP” and “order 12” will often be omit-
ted in what follows.
Notation 2: The abscissa vector

123
,,,,ccc  

T
s
c, 01
j
c, defines the off-step points nj tct

.
An
H
Bks method requires the following
s
formu-
lae to perform integration from n
t to 1n t, where, for
simplicity, 10c is used in the summations. By con-
vention, 0
11c

.
Let :(, )
j
nj j
F
ftc tY

 be the jth stage deriva-
tive and set 1n
Yy

.
An HB polynomial of degree 23ki is used as
predictor i
P to obtain the thi stage value i Y to order
9,
111
011
,
2, 3,,.
ij
kik
iijnjijj nj
jjj
YytaFf
is














(7)
An HB polynomial of degree 22ks is used as
integration formula to obtain 1n
y to order 12:
11
1011
j
ksk
nj njjjnj
jjj
yytbFf 

 






. (8)
3. Order Conditions of
H
Bks
To derive the order conditions for
H
Bks we shall use
the following expressions coming from the backsteps of
the methods:
1
11
11
() ()
() ,
!(1)!
1, 2,,12, 2, 3,,.
jj
kk
iil il
ll
ll
Bj jj
jis










(9)
As in the construction of RK methods, we impose the
following simplifying conditions on the abscissa vector

123
,,,, T
s
ccc c  :
1
1(1)
i
iili
j
caB



, 2, 3,,is. (10)
Forcing an expansion of the numerical solution pro-
duced by formulae (7)-(8) to agree with a Taylor expan-
sion of the true solution, we obtain multistep- and
RK-type order conditions that must be satisfied by
H
Bks . To reduce the large number of RK-type order
conditions, we impose the following simplifying as-
sumptions, as in similar searches for ODE solvers [7]:
11
1
1
!( 1),
1
2, 3,,, =1,2,,8.
ikk
ij jii
j
ackB kc
k
isk







(11)
Note that (11) with 0k

reduces to (10). There are
seven sets of equations to be solved:
1
01
k
il
j




, 2, 3,,is, (12)
1
0
1
k
i
i




, (13)
1
1
!( 1)1
sk
ii i
i
bck Bkk



, 0,1, ,11k, (14)

T. NGUYEN-BA ET AL. 74
9
1
21
1
(10) (11)
9! 11!
si i
iij i
ij
c
ba BB






 , (15)
9
1
21
1
(10) (12)
11 9!12!
si
ii
iiji
ij
cc
baB B






 , (16)
10
1
21
1
(11) (12)
10! 12!
si i
iij i
ij
c
ba BB






 , 17)
9
1
1
21 1
(10) (11)
9!
1
(12)12!
j
si k
iij jkji
ijk
c
baBB
B



 









 , (18)
where the backstep parts, ()Bj, are defined by
1
11
11
() ()
() ,
!(1)!
1, 2,,12.
jj
kk
ii
ll
ii
Bj jj
j










(19)
4. Shu-Osher Representation of
H
Bks
We rewrite
H
Bks in the Shu-Osher representation as-
convex combi natio ns of FE to show that they satisfy SSP
conditions.
Firstly, if we let
1
1
1
0, 1, 3, 4,,,
and 0, 1,
il
sl
i
il
j
s
sl
l
is
uu









(20)
then formulae (7) and (8) become
11
0
11
11
11
, 3, 4,,,
ij
ik
iilinijnj
lj
ik
ijjn j
jj
Yyy
taFf is
 












 



 
(21)
1
111
11
11
j
sk
nslonjnj
lj
ik
jj nj
jj
yuyy
tbF f













 




(22)
Replacing the index i by m in formula (7), we ex-
press n
y as a function of m Y,
1
1
11
0
11
1,
2,3,,,
mj
k
mmjnj
j
nmk
mmjjnj
jj
Yy
y
taFf
ms
























(23)
For 3, 4,,is

 and 1, 2 ,,1li, we replace
the variable n
y in the terms 0
il in
y


in (21) by the
right-hand side of (23) with =lm. Similarly, n
y in the
terms 0
sl n
uy

in (22) is replaced by the right-hand
sides of (23) with =lm.
Secondly, we rewrite (7) with 2i, and (21) with
3, 4,,is

 as (24), and (22) as (25) in the Shu-Osher
equivalent form:
11
00
11
21
, 2, 3,,,
ij
kk
iijnjnj
jj
ii
ij jijj
jj
YAytBf
eYt gFis










 



 
(24)
11
100
22
i
kk
nj njnj
jj
ss
jjj j
jj
yAytBf
eYtgF

 


















, (25)
where the coefficients are
1
, 2, 0, 1,...,1, 2, 3,,
i
iji jillj
l
A
ej kis 


 
,
2, 0, 1,1
s
jj llj
l
A
ej k 



,
1
, 2
, 0, 1,,1, 2, 3,,
i
iji jillj
l
Bejkis 


 
,
2
, 0, 1,,1
s
jj llj
l
Bejk 



,
1
1, 3, 4,,, 2, 3,,1
i
ijijillj
lj
g
aeai sj i



 
,
1
1, j2, 3,,
i
jj llj
lj
g
beas


 
,
which follow from setting
00
/, 2, 3,,1, 3, 4,,
ijij ij
ejiis



,
10
, 2, 3,,
ii
ai s


,
00
/, 2, 3,,
sl
jj
eu js  ,
10
b


.
Thirdly, the representation (24,25), under the assump-
tions that all coefficients are nonnegative, implies that
the
H
Bkp are SSP. In fact, one finds that the following
functions are convex combinations of forward Euler
steps:
• In (24) fo r 2, 3,,is

, the first and second brack-
eted terms are sums of FE steps with step sizes ij
ij
Bt
A

,

T. NGUYEN-BA ET AL. 75
0, ,1jk, and ij
ij
gt
e, 2, 3,,1ji, respec-
tively.
• In (25), the first and second bracketed terms are
sums of FE steps with step sizes i
i
Bt
A, 0,,1jk,
and j
j
gt
e, 2, 3,,1ji, respectively.
One can easily verify that
11 1
02 02
1, 2, 3,,, 1
kik s
ij ijjj
jj jj
Aei sAe
 
 
 
 
.
Provided all the coefficients ij
A
, ij e,
j
A
,
j
e are
nonnegative, the following straightforward extension of a
result presented in [6,8] holds.
Theorem 1: If the forward Euler method FE is SSP
under the CFL condition FE
tt , then the k-step,
s
-stage
H
Bks methods (24,25) are SSP provided
()
F
E
tcHBkst ,
where the SSP coefficient ()cHBks is the minimum of
the four numbers:
0, 1,,10, 1,,1
j2, 3,,2, 3,,1
min, min, 2, 3,,,
min, min, 3, 4,,,
jij
jk jk
jij
jij
sji
jij
AA
is
BB
ee
is
gg
 

 
 
 
 
 
 
 
 
 
 




(26)
with the convention that /0


 , under the assump-
tion that all coefficients of (24) - (25) are nonnegative.
5. Construction of Optimal
H
Bks
Since
H
Bks contain many free parameters when k is
sufficiently large, we use the Matlab Optimization Tool-
box to search for the methods with largest ()cHBks for
different k and
s
. To optimize
H
Bks , we maximize
()cHBks of Theorem 1 by solving the nonlinear pro-
gramming problem
, , , , , , ,
max( )
ijijijij j jjj
ABegABeg
cHBks, (27)
where all the numbers in all pairs

, , 0, 1,,1
jj
A
Bj k,

, , 2, 3,,, 0, 1,,1
ij ij
A
Bisjk
,

, , 2, 3,,
jj
eg js,

, , 3, 4,,, 2, 3,,1
ij ij
eg isji ,
are nonnegative. Null pairs, {0, 0}, are not included in
the minimization process if they occur. Besides the non-
negativity constraints on all variables, the objective func-
tion (27) is subject to
• the convex combinations constraints (20),
• the simplifying assumptions (10) and (11) for
H
Bks ,
• the order conditions (12) to (18) for
H
Bks ,
• the conditions on the abscissa vector: 10c

,
01
i
c

, 2, 3,,is

.
6. Comparing Effective SSP Coefficients
Definition 1: (See [9]) The effective SSP coefficients
of an SSP method M is denoted by
()
()
eff cM
cM l  (28)
where l is the number of function evaluations of
method
M
per time step and ()cM is the SSP coeffi-
cient of
M
.
The SSP coefficients, ()cHM, of hybrid methods are
defined in [6]. In this paper, 5, 6 ,,10l for
H
B
methods and 2l

for hybrid methods. The numbers
()
eff
cHB and ()
eff
cHM will be used below.
The effective SSP coefficients, eff
c, provide a fair
comparison between methods of the same order, al-
though, in practice, starting methods and storage issues
may also be important. Gottlieb [10] pointed out that one
looks for highorder SSP methods
M
with ()cM as
large as possible, taking their computational costs and
orders into account.
We briefly review the developments of SSP methods.
Shu and Osher [11] constructed a series of second- to
fifth-order SSP RK methods, several of which are
downwinded ones. Shu [12] found a class of first-order
SSP RK methods with very large SSP coefficients, as
well as one- to five-step SSP methods of orders two to
five. Gottlieb and Shu [13] derived optimal
s
-stage SSP
RK methods of order s for 2, 3 s, and proved that for
4s

there is no such SSP method with nonnegative
coefficients. Spiteri and Ruuth [14,15] studied optimal
s
-stage SSP RK methods of order p with
s
p for
4p

. They proved the nonexistence of fifth order SSP
RK methods with nonnegative coefficients [16] and con-
structed some fifth-order methods of seven to nine stages
with downwind-biased spatial discretization [9]. A 10-
stage method of order 5 was given in [17]. Hunds-dorfer,
Ruuth and Spiteri [18] proved that the implicit Euler me-
thod can unconditionally preserve the strong stability of
the FE method (see also [19]) and studied multistep me-
thods with specific starting procedures.
Ruuth and Hundsdorfer [20] pointed out that linear
multistep methods of order five require at least seven
steps. Huang [6] introduced the 7-step hybrid method
7
H
Mwith (7)0.234cHM

and(7) 0.117.
eff
cHM


T. NGUYEN-BA ET AL. 76
Table 1. ()
eff
cHBks, for , 78k, as a Function of s.
s
(7)
eff
cHBs (8)
eff
cHBs
5 0.010 0.057
6 0.035 0.091
7 0.060 0.096
8 0.055 0.091
9 0.051 0.083
10 0.047 0.076
In the literature, we have found no general linear
methods of or d e r 12 . W e no w l ist our be st methods.
5
H
Bk . Our best 5-stage SSP HBk5 method has step
number 8k with (85)0.288cHB

and (85)
eff
cHB
0.057.
6
H
Bk . Our best 6-stage 6
H
Bk has 8k

with
(86) 0.544cHB  and (86)0.091
eff
cHB.
7
H
Bk . Our best 7-stage HBk7 have 7, 8k. Our
87
H
B has largest effective SSP coefficient among the
12th-order
H
B methods on hand. The coefficients
(87) 0.669cHB  and (87) 0.096
eff
cHB are listed in
boldface in Tabl e 1.
According to our search, it seems that (87)
eff
cHB
cannot be improved up to 10 stages and 8 steps.
The formulae of some of our best new
H
Bks are
listed in Appendix A with their ()cHBks, ()
eff
cHBks
and abscissa vector

.
Table 1 lists ()
eff
cHBks as a function of
s
for
7, 8k. We note that, for a given k, ()
eff
cHBks first
increases with s and then decreases. We see that
(87) 0.096
eff
cHB  is largest for the values of k and
s
on hand.
Definition 2: The percentage efficiency gain (PEG )
of the SSP coefficients (2)
eff
cM of method 2 over
(1)
eff
cM of method 1 is
(2) (1)
((2), (1))(1)
eff eff
eff effeff
cM cM
PEG cMcMcM

. (29)
7. Numerical Results
From now on, we use the total variation semi-norm,
, 1,
()
nnjnj
j
TV yyy


, (30)
and say that a method is total variation diminishing
(TVD ) if
1
() ()
nn
TV yTV y


. (31)
We compare our new methods numerically with
7
H
M of Huang.
7.1. Starting Procedure
To maintain the TVD property (31), the necessary
starting values for
H
Bkp were obtained by RK54 with
small initial step size, 11.0 0.4he

 (approximatively).
7.2. Comparing HBks with 7HM with a Unit
Downstep Initial Condition
As a first comparison of
H
Bks of order 12 with
Huang’s 7-step 7
H
M of order 7 [6], we consider Bur-
gers’ equation in Problem 1.
Problem 1: Burgers’ equation with a unit downstep
initial condition:
2
1
(, )(, )0,
2
ux tuxt
tt







1, 10,
(, 0)0, 01.
x
ux x
 


 (32)
and boundary condition (1, ) 1ut

 for 0t.
We discretize the spatial derivative of the flux func-
tion 2
()(, )/2fu uxt by the weighted essentially
nonoscillatory finite difference scheme of order 5
(WENO5) of Jiang and Shu [21] with spatial stepsize
1/150x

. This leads to the semi-discrete system
(1/2) (1/2)
1
()
jjj
dutff
dtx 



, (33)
where (, )
jj
uuxt

with j
x
jx, 149,,1,j 
0, 1,,150 , and (1 /2)j
f is the numerical flux, which
typically is a Lipschitz continuous function of several
neighboring values ()
j
ut (see [21] for details). A time
discretization can then be applied to (33).
We consider the total variation norm of the numerical
solution at 1.8
final
t

. For this purpose, we let eff n be
the largest effective CFL number defined as
1
max
eff t
t
n
x
l






, (34)
such that the TV error in the numerical solution satisfies
the inequality
((, ))((, 0)5.002
final
TV u xtTV u xe

, (35)
and we let maxnum eff tlxn

 be the maximum nu-
merical step size. Here l is the number of function
evaluations per time step. We note that Inequality (35) is
used because
f
inal
tis small.
Finally, we let max theor t

of
H
Bks for Problem 1
be taken as
FE
max()
theor
tcHBkst

, (36)
where the SSP coefficients ()cHBks of some of the
H
Bks are listed in Appendix A.
The numerical results for Problem 1 show that the
forward Euler method,
F
E, has TVD property (31)
with error (35) under the time step restriction

T. NGUYEN-BA ET AL. 77
FE 0.325tt x. (37)
It was also observed numerically that the TVD prop-
erty (31) holds with error (35) for the methods listed in
Table 1 with max num tt . This confirms the result of
Theorem 1 that
H
Bks are also TVD with maxt


num
t when combined with the WENO5 space discreti-
zation since
H
Bks are convex combinations of
F
E.
The same situation holds for Problem 2 below.
Definition 3: The eff n percentage efficiency gain of
method 2 over method 1 is
(method 2)(method 1)
() (method 1)
eff eff
eff eff
nn
PEG nn

. (38)
Table 2 lists (())
eff
PEG nHBks, (7)
eff
nHM for
H
Bks and (7) 0.127
eff
nHM for Problem 1. It is
seen that
a) (8)( 7)
eff eff
nHBs nHM for all 8
H
Bs on hand,
b) quite remarkably, even though (8)
eff eff
cHBsc

(7)HM , in this example, 8
H
Bs methods allow a larger
step size since (8)( 7)
eff eff
nHBs nHM,
c) ((8))
eff
PEG nHBs, (7)0
eff
nHM and increases
as
s
increases,
d) the ratios /nt
R of
H
Bks are clearly higher than
the ratio of 7
H
M. For example, /(85) 7.310
nt
RHB


/
3.34( 7)
nt
RHM.
The ()
eff
nHBks, for 7, 8k, as a function of s for
Problem 1 are listed in Table 3.
7.3. Comparing HBks and 7HM with a
Square-Wave Initial Condition
As a second comparison, we consider Burgers’ equation
with a square-wave initial value in Problem 2, which is
test case 4 of Laney’s five test problems [22, p.312].
Problem 2: Burgers’ equation with a square wave ini-
tial condition:
2
1
(, )(, )0,
2
1,
1, 3
(, 0)0, 11.
3
ux tuxt
tt
x
ux
x













(39)
and boundary condition (1, )0ut for 0t.
We discretize the spatial derivative of Problem 2 by
WENO5 and compute the total variation of the numerical
solution as a function of the effective CFL number,
/( )tlx, at 0.6
final
t. In this case, 0.325
eff
n in
the time step restriction (37) is replaced by 0.183
eff
n

.
Table 4 lists((), (7))
eff eff
PEGnHBksn HM for
H
Bks where (7) 0.122
eff
nHM for Problem 2. It is
seen that the results for Problem 2 listed in Table 4 con-
Table 2. , (()(7))
eff eff
PEGn HBksn HM for HBks and
7HM , and ratio //max max
n tnumtheor
R
tt for Problem
1. Here ()70.127
eff
nHM

and ().
/73 340 nt
RHM.
H
Bks ()
eff
nHB /nt
R
PEG
85
H
B0.137 7.310 8%
86
H
B0.170 5.772 34%
77
H
B0.145 7.402 14%
87
H
B0.210 6.756 65%
Table 3. ()
eff
nHBks, for HBks HBks applied to Problem 1.
s
(7)
eff
nHBs (8)
eff
nHBs
5 0.075 0.137
6 0.084 0.170
7 0.145 0.210
Table 4. (,
ee
()(7))
ff ff
PEGn HBksn HM for HBks and
7HM , and ratio //
nmax max tnum theor
R
tt for Problem
2. Here .
e(7)0 122 ff
nHM

and ()
t/75.689 n
RHM.
H
Bks ()
eff
nHB /nt
R
PEG
85
H
B 0.137 12.999 12%
86
H
B 0.158 9.541 30%
77
H
B 0.138 12.536 14%
87
H
B 0.203 11.608 67%
Table 5. ef()
f
nHBks, for HBks applied to Problem 2.
s
(7)
eff
nHBs (8)
eff
nHBs
5 0.075 0.137
6 0.083 0.158
7 0.138 0.20
firm the observations (a-d) obtained for Problem 1 as
listed in Table 2.
We observe that, as with hybrid methods, the ratio
max/max
num theor
tt

 of
H
Bks for Problems 1 and 2
are greater than 1. The theo retical stro ng-stability b ounds
of
H
Bks are thus verified in the numerical comparison
of the maximum time steps for Problem 1 and confirmed
again with Problem 2.
Table 5 lists ()
eff
nHBks for 7, 8k as a function
s for Problem 2.
8. Conclusions
New optimal explicit k-step,
s
-stage (5, 6, ...,10s)
SSP Hermite-Birkhoff methods,
H
Bks, of orders 12
with nonnegative coefficients are constructed by combin-
ing linear k-step methods of order 9 with 5- to 10-stage
Runge-Kutta methods of order 4. No counterparts of
H
Bks of order 12 have been found in the literature
among hybrid and general linear multistep methods.

T. NGUYEN-BA ET AL. 78
Moreover, the 8-step 7-stage 87
H
B has largest effec-
tive SSP coefficient among the 12th-order
H
B meth-
ods on hand. It is found that some of new
H
Bks have
larger effective SSP coefficients and larger maximum
effective CFL numbers than Huang’s 7-step hybrid
method of or de r 7 on Burgers’ equation s .
9. References
[1] A. Harten, “High Resolution Schemes for Hyperbolic
Conservation Laws,” Journal of Computational Physics
Vol. 49, No. 3, 1983, pp. 357-393.
doi:10.1016/0021-9991(83)90136-5
[2] S. Osher and S. Chakravarthy , “High Resolution Schemes
and the Entropy Condition,” SIAM Journal on Numerical
Analysis, Vol. 21, No. 5, 1984, pp. 955-984.
doi:10.1137/0721060
[3] P. K. Sweby, “High Resolution Schemes Using Flux
Limiters for Hyperbolic Conservation Laws,” SIAM
Journal on Numerical Analysis, Vol. 21, No. 5, 1984, pp.
995-1011. doi:10.1137/0721062
[4] B. Cockburn and C. W. Shu, “TVB Runge-Kutta Local
Projection Discontinuous Galerkin Finite Element
Method for Conservation Laws II: General Framework,”
Mathematics of Computation, Vol. 52, No. 186, 1989, pp.
411-435.
[5] S. Gottlieb, D. I. Ketcheson and C. W. Shu, “High Order
Strong Stability Preserving Time Discretization,” Journal
of Scientific Computing, Vol. 38, No. 3, 2009, pp.
251-289.
[6] C. Huang, “Strong Stability Preserving Hybrid Methods,”
Applied Numerical Mathematics, Vol. 59, No. 5, 2009, pp.
891-904. doi:10.1016/j.apnum.2008.03.030
[7] T. Nguyen-Ba, E. Kengne and R. Vaillancourt,
“One-Step 4-Stage Hermite-Birkhoff-Taylor ODE Solver
of Order 12,” The Canadian Applied Mathematics Quar-
terly, Vol. 16, No. 1, 2008, pp. 77-94.
[8] S. Gottlieb, C. W. Shu and E. Tadmor, “Strong Stability-
Preserving Highorder Time Discretization Methods,”
SIAM Review, Vol. 43, No. 1, 2001, pp. 8-112
doi:10.1137/S003614450036757X
[9] S. J. Ruuth and R. J. Spiteri, “High-Order Strong-Stabil-
ity-Preserving Runge-Kutta Methods with Down-Biased
Spatial Discretizations,” SIAM Journal on Numerical
Analysis, Vol. 42, No. 3, 2004, pp. 974-996.
doi:10.1137/S0036142902419284
[10] S. Gottlieb, “On High Order Strong Stability Preserving
Runge-Kuttaand Multi Step Time Discretizations,” Jour-
nal of Scientific Computing, Vol. 25, No. 1-2, 2005, pp.
105-128.
[11] C. W. Shu and S. Osher, “Efficient Implementation of
Essentially Nonoscillatory Shock-Capturing Schemes,”
Journal of Scientific Computing, Vol. 77, No. 2, 1988, pp.
439-471. doi:10.1016/0021-9991(88)90177-5
[12] C. W. Shu, “Total-Variation-Diminishing Time Discreti-
zations,” SIAM Journal on Numerical Analysis, Vol. 9,
No. 6, 1988, pp. 1073-1084. doi:10.1137/0909073
[13] S. Gottlieb and C. W. Shu, “Total Variation Diminishing
Runge-Kutta Schemes,” Mathematics of Computation,
Vol. 67, No. 221, 1998, pp. 73-85.
doi:10.1090/S0025-5718-98-00913-2
[14] R. J. Spiteri and S. J. Ruth, “A New Class of Optimal
High-Order Strong-Stability-Preserving Time-Stepping
Schemes,” SIAM Journal on Numerical Analysis, Vol. 40,
No. 2, 2002, pp. 469-491.
doi:10.1137/S0036142901389025
[15] R. J. Spiteri, S. J. Ruuh, “Nolinear Evoluton Using Opti-
mal Fourth-Order Strong-Stability-Preserving Runge-
Kutta Methods, Journal of Mathematics and Computers
in Simulation, Vol. 62, No. 1-2, 2003, pp. 125-135.
doi:10.1016/S0378-4754(02)00179-9
[16] S. J. Ruuth and R. J. Piteri, “Two Barriers on Strong-
Stability-Preserving Time Discretization Methods,”
Journal on Scientific Computing, Vol. 17, No. 1-4, 2002,
pp. 211-220. doi:10.1023/A:1015156832269
[17] S. J. Ruuth, “Global Optimization of Explicit Strong-
Stability-Preserving Runge-Kutta Methods,” Mathemat-
ics of Computation, Vol. 75, No. 253, 2006, pp. 183-207.
doi:10.1090/S0025-5718-05-01772-2
[18] W. Hundsdorfer, S. J. Ruuth and R. J. Spiteri,
“Monotonicity Preserving Linear Multistep Methods,”
SIAM Journal on Numerical Analysis, Vol. 41, No. , 2003,
pp. 605-623. doi:10.1137/S0036142902406326
[19] I. Higueras, “On Strong Stability Preserving Methods,”
Journal of Scientific Computing, Vol. 21, No. , 2004, pp.
193-223. doi:10.1023/B:JOMP.0000030075.59237.61
[20] S. J. Ruuth and W. Hundsdorfer, “High-Order Linear
Multistep Methods with General Monotonicity and
Boundedness Properties,” Journal of Computational
Physics, Vol. 209, No. 1, 2005, pp. 226-248.
doi:10.1016/j.jcp.2005.02.029
[21] G. Jiang and C. W. Shu, “Efficient Implementation of
Weighted ENO Schemes,” Journal of Computational
Physics, Vol. 126, No. 1, 1996, pp. 202-228.
doi:10.1006/jcph.1996.0130
[22] C. Laney, “Computational Gasdynamics,” Cambridge
University Press, Cambridge, 1998.
doi:10.1017/CBO9780511605604

T. NGUYEN-BA ET AL. 79
Appendix
This appendix lists the Shu-Osh er represen tation of some
of the best
H
Bks methods considered in th is paper with
large ()cHBks , eff ()cHBks and abscissa vector


12
[, ,...]cc . For concision, 77n yy


 and 77n
f
f



,
etc., that is, the n is omitted.
85
H
B. 0.288c, 0.0575
eff
c, and

=[0, 0.26168792578970829, 0.57645868591351512,
0.64259830897152903, 0.84768581516148367]T.
2
Y=2.5088663215922309 7 3ey


+1.7925867066588250 6
1ey


+8.3882346204594546 5 2ey


+5.3490887614261351 4 2ey


+1.5355696110214626 3 1ey


+1.0519373621484439 2 1ey


+2.4588790492868035 1 1ey


+1.7622062694799823 0 1ey


+6.0965642854921308 6 2ehf


+2.91573176976848 5 1ehf


+1.8593314024575333 4 1ehf


+5.3376059470557180 3 1ehf


+3.6565109649432631 2 1ehf


+8.5470090983589497 1 1ehf


+6.1253899506765896 0 1ehf


3
Y=2.6128898286558854 7 4ey


+1.6160083267835362 6 1ey


+9.4862179832725935 5 2ey


+5.6365573282506388 4
3ey


+2.0977946829698155 3 1ey


+1.4916019106552419 2 2ey


+3.0292902279685230 1 1ey


+9.0823471553059566 7 4ehf


+3.7634075368106784 6 2ehf


+3.2973883540780097 5 1ehf


+1.9592548393933151 4 2ehf


+7.2918878409381671 3 1ehf


+5.1847751946960174 2
2ehf


+1.0529745717881731 1 0ehf


+2.1001463097741810 2 1eY
+7.3000620436093744 3 1ehF,
4
Y=4.2596681035936669 7 3ey


+5.4580922815710267 6 2ey


+1.2619581254827076 5 2ey


+4.6309759376721930 4
2ey


+8.5864031653139994 2 2ey


+2.5760590697067362 1 2ey


+6.9756199296789845 0 1ey


+3.3666866480073193 6 2ehf


+4.3865384852407319 5 2ehf


+1.6097169759141286 4 1ehf


+2.9846147169135057 2 1ehf


+8.9543242531916173 1 2ehf


+5.2321449943060860 0 1ehf


+7.3043453131041394 3 2eY
+2.5389742479104255 3
1ehF
5
Y=1.9031575432429105 7 2ey


+9.4390087983054396 6
3ey


+4.9434657715702020 5
3ey


+1.6566124692029068 4 2ey


+1.1104031717607358 3
2ey


+2.6842037578605454 2 2ey


+1.8775366097652471 1
2ey


+7.5605047579112805 0 1ey


+5.4836011749628891 7
3ehf


+3.2809785459763291 6 2ehf


+1.7183377498495377 5 2ehf


+5.7583482403654469 4 2ehf


+3.8597368238337690 3 2ehf


+9.3302327932468482 2 2ehf


+6.5262756583411866 1 2ehf


+3.5880557446886407 0 1ehf


+1.3724791412067294 4 1eY
+4.7707070872820062 1ehF
1n
y

=3.6675474446860911 7 4ey


+1.8187060855967201 6 2ey


+8.3994945677018339 5 3ey


+4.9736412857637512 4 3ey


+1.8712919442613503 3 2ey


+1.6346596041633132 2 6ey


+5.0971099921212137 1 1ey


+1.6214093549108249 0
1ey


+6.5806701062719308 6 3ehf


+2.9196457024832888 5 2ehf


+1.7288266917287534 4 2ehf


+6.5045693394014711 3 2ehf


+5.6820405678545405 2 6ehf


+3.2159785087110521 1 1ehf


+5.6359829950182783 0 1ehf


+1.4048847659544447 2 1eY
+1.1567333760542281 2
1ehF
+ 9.47751752497812303 11eY
+4.2595421684290258 4 2eY
+1.4806074206442218 4 1ehF
+9.4422661366167060 5 2eY
+3.2821107895566276 5 1ehF.
86
H
B. 0.544c

, 0.091
eff
c

,

=[0, 0.21131780320298513, 0.44627527172505960,
0.60194043865046165, 0.68474825481971757,
0.88846370798458207]T.
2
Y=1.2056356845857071 7 4ey


+2.5194380079479200 6 2ey


+3.2952118982459200 5 2ey


+1.1957054109007751 4 2ey


+9.9102593302822214 3 2ey


+6.2284629866456040 2 2ey



T. NGUYEN-BA ET AL. 80
+2.3317040497514951 1
1ey


+5.3521825511616750 0 1ey


+2.2172094474490973 7
4ehf


+ 5.27188062448966886
3ehf


+6.0600188311846041 5
2ehf


+2.1989473000097962 4
2ehf


+1.8225340287039474 3 1ehf


+1.1454378095836737 2
1ehf


+4.2880915967088845 1 1ehf


+4.1727467824309650 0
1ehf

,
3
Y=2.1266363269138659 7 2ey


+1.5771836376798177 6
2ey


+4.3926172811566480 5 2ey


+1.7082987843641939 3 1ey


+3.2188412399962563 2 2ey


+3.7020209932015796 1 1ey


+1.1154991421676907 0 1ey


+7.0377902093498815 7 3ehf


+2.9005001316193480 6 2ehf


+8.0781886761716257 5 2ehf


+3.1416258262624769 3 1ehf


+5.9195703133247138 2 2ehf


+6.8081560837360267 1 1ehf


+2.0514449499605397 0 1ehf


+2.3426532316918772 2 1eY
+4.3082275548183158 2 1ehF,
4
Y=5.3099276098768008 7 5ey


+5.4961729571656546 6 4ey


+1.1637244430341524 5
3ey


+2.3085416780083620 3 3ey


+3.9189061446081950 2 3ey


+8.0147132511805186 0 1ey


+4.2610525709387915 7 5ehf


+2.1401330951890396 5 3ehf


+4.2454951224084048 3 3ehf


+7.2070160485316233 2 3ehf


+1.7712502856993173 0 1ehf


+1.9053478604448212 3
1eY
+3.5040065011901728 3 1ehF
5
Y=3.0086399419988188 7 3ey


+ 2.44588599330437086 2ey


+3.1107392915270225 5 3ey


+ 6.49425303651048474 2ey


+1.4504001607980657 2 1ey


+ 1.14835976677798801
1ey


+5.0132225682684406 0 1ey


+ 1.98392243025731016 2ehf


+5.7207667572438340 5 3ehf


+ 1.19431760114366604 1ehf


+2.6673405409431139 2 1ehf


+ 2.11187687667484111 1ehf


+5.6014248925231536 0 1ehf


+ 1.43280980883876034 1eY
+2.6349912209563475 4 1ehF
6
Y=3.8364653662411327 7 4ey


+1.9538912222846316 6
2ey


+4.6039554350891257 5
2ey


+1.2188103769706057 3
1ey


+5.3347382574306705 2
2ey


+2.4574345904392714 1 1ey


+2.6965321938536446 0
1ey


+7.0554043510781647 7 4ehf


+2.6945695396165658 6
4ehf


+7.1279472038856595 5 2ehf


+2.2414382031142641 3
1ehf


+9.8107846468628329 2 2ehf


+4.5193147980540027 1 1ehf


+4.9590242989675859 0 1ehf


+2.4341278818897943 5 1eY
+4.4764528829286226 5 1ehF
1n
y

=3.0057309944696390 7 4ey


+ 1.84184168858024736 2ey


+1.8025732157544459 5 2ey


+ 1.89904044771057534 2ey


+5.3350392235820249 3 2ey


+5.6588063024340191 2 2ey


+2.8208800017277152 1 1ey


+2.1570341210469796 0 1ey


+6.3394334033130204 6 3ehf


+3.3150000574699620 5 2ehf


+3.4924069315339902 4 2ehf


+9.8113381349543630 3
2ehf


+1.0406757991202498 2 1ehf


+3.3081996436653333 1 1ehf


+3.9668670169619830 0 1ehf


+9.1404198485699903 2eY
+1.6809576475720123 1ehF
+1.2805484845172674 5 1eY
+2.3549769089357700 5 1ehF
+1.1707595890504358 6 1eY
+2.1530709937689432 6
1ehF.
87
H
B. 0.669c

, 0.096
eff
c

, and

=[0, 0.24630671392471543, 0.34372959589592622,
0.46965773869833194, 0.60188693905557489,
0.74797892054340487, 0.88945490483914114]T.
2
Y=3.7974982255302016 7 3ey


+4.5089590734417921 5 2ey


+1.3429764576528219 3
1ey


+5.6617416306819886 2 2ey


+4.0351426372574184 1 1ey


+3.5668358524220800 0 1ey


+1.6821020062433984 7 3ehf


+4.1148530730146071 5 2ehf


+2.0060641782382357 3 1ehf


+8.4571974490169566 2 2ehf


+5.5717589231755449 1 1ehf



T. NGUYEN-BA ET AL. 81
+5.3279427144280755 0 1ehf

,
3
Y=2.9172400973803583 7 5ey


+1.5457113291505844 6
5ey


+1.1177286333803951 5
4ey


+2.8614723012174159 3
4ey


+5.4885374083531169 2
4ey


+8.5268194936899200 0 1ey


+1.1450336076905814 7
5ehf


+2.3088983501061465 6 5ehf


+1.6696013989213592 5
4ehf


+4.2743095366881700 3 4ehf


+8.1984745325029522 2
4ehf


+9.0476868364274501 0 2ehf


+1.4632664728244774 2 1eY
+2.1857467698879354 2 1ehF,
4
Y=3.8475518352648985 7 5ey


+8.7276046172694814 6 5ey


+3.9160153529198250 5 4ey


+8.4698793426668008 3 4ey


+1.9159825166593124 2 3ey


+8.0838239885846730 0 1ey


+2.0756050912562519 7 5ehf


+5.8495277978687062 5 4ehf


+1.2651838717277304 3 3ehf


+2.8619890325691857 2 3ehf


+1.2798384206338995 0 1ehf


+1.8833727759078944 3 1eY
+2.8132783999960803 3 1ehF
5
Y=3.945885121420493 7 4ey


+3.0224741261588189 6 3ey


+2.7859199581055545 5 5ey


+1.1690557783204216 4 2ey


+3.2441888015861495 2 2ey


+2.6344135585813794 1 2ey


+7.2046178550821049 0 1ey


+2.5773136196436813 6 3ehf


+4.1614536126434194 5 5ehf


+3.9351417073771384 1
2ehf


+2.4931199806475163 0 1ehf


+2.0561671126902800 4 1eY
+3.0713890520825726 4 1ehF
6
Y=1.1157847037721505 7 3ey


+8.2716022628498732 6 3ey


+3.1541447869261996 4 2ey


+1.9317942446706354 3
3ey


+8.3536788648073387 2 2ey


+8.3768231333280554 1 2ey


+5.5987874866806642 0 1ey


+7.1766023733280809 6 3ehf


+4.7114875573382890 4 2ehf


+2.8856077199845985 3 3ehf


+1.2478264850959904 2 1ehf


+1.2512836483058420 1 1ehf


+3.9923163881741003 0 1ehf


+2.2995560227002496 5 1eY
+3.4349499849412118 5
1ehF
7
Y=7.0665184156984342 7 5ey


+1.1357098866877038 6
2ey


+1.9489725260200538 5
2ey


+1.1371636634757204 4 2ey


+7.0530362148945702 3
2ey


+6.7156684867183417 2 2ey


+2.2796040165854331 1
1ey


+2.5634355593341113 0 1ey


+1.0555575548486729 7
4ehf


+2.3467533365446628 6 3ehf


+2.9112676894221846 5 2ehf


+1.6986323751942745 4 2ehf


+1.0535436580359381 3 1ehf


+1.0031495271089685 2 1ehf


+3.8291186859596027 0 1ehf


+1.2182135533209280 3 1eY
+1.8197002314043459 3 1ehF
+2.1389851411383179 6 1eY
+3.1950980562391240 6 1ehF
1n
y

=1.8273596102868513 7 4ey


+1.1489248786967506 6 2ey


+1.4564465260880323 5 2ey


+1.9394836900481112 4 2ey


+5.2821409707040239 3 2ey


+7.9212845840518423 2 2ey


+1.9373980081939868 1
1ey


+2.7692442403851641 0 1ey


+3.9204470975736996 6 3ehf


+ 2.17555950951750025 2ehf


+2.8970937894792437 4 2ehf


+7.8901709150237184 3 2ehf


+1.1832378117387013 2 1ehf


+2.8939783129338997 1 1ehf


+4.1365443450426853 0 1ehf


+5.2243622611154630 4
2eY
+7.8038642646651585 4 2ehF
+1.3856684832443625 5 1eY
+2.0698351719496980 5 1ehF
+1.6085976174957770 7 1eY
+2.4028344199700516 7 1ehF.
77
H
B. 0.422c

, 0.060
eff
c

,

=[0, 0.24553329633115092, 0.34381434970186381,
0.46996349805312904, 0.59741148855197324,
0.74861321481234733, 0.93726371152609467]T.
2
Y=7.3010787905497990 6 2ey


+5.8928786071653340 5 2ey


+3.2361722721541197 4 2ey


+1.4144020818838035 3 1ey


+9.4746286693606921 2 2ey


+2.8032846082374741 1 1ey



T. NGUYEN-BA ET AL. 82
+3.1918374759557272 0
1ey


+2.0216798040263967 6 2ehf


+1.3966929029116232 5
1ehf


+7.6701713142726322 4
2ehf


+3.3523265645222677 3
1ehf


+2.2456167015095949 2
1ehf


+6.6441682888323905 1 1ehf


+5.4103154682409460 0
1ehf

,
3
Y=2.1115317946545937 6 4ey


+1.5683574504977375 5
4ey


+1.4918080498094698 4 4ey


+2.4632407047148717 3
4ey


+6.2170015127662251 2 4ey


+9.0363491063395274 0 1ey


+6.1209542801914530 6 5ehf


+5.8382176857588175 3 4ehf


+1.4735144687543986 2 3ehf


+9.7164614733266222 0 2ehf


+9.4979895414803089 2 2eY
+2.2511535480103231 2 1ehF,
4
Y=4.2291768720718013 6 7ey


+1.2580709591111811 5 3ey


+1.0608502734091687 4 3ey


+3.9605051502427150 3 4ey


+2.9582053774373411 2 3ey


+8.7179307769714254 0 1ey


+1.0023728157574881 6 6ehf


+2.5143603774916003 4 3ehf


+9.3869393959055553 3
4ehf


+7.0113517203593250 2 3ehf


+1.4425410174792175 0 1ehf


+1.2253332226018823 3 1eY
+2.9042074846559973 3 1ehF
5
Y=5.3214622874936398 6 5ey


+1.0124744704382351 5 4ey


+6.7489031345744424 4 3ey


+6.2012840133771428 3 3ey


+1.2292552008659938 2
3ey


+1.5676690480087496 1 1ey


+6.9948617940629676 0 1ey


+2.3997031018436723 5 4ehf

5
+1.5377805444918592 4 3ehf


+1.4697892062279427 3 2ehf


+2.9135031100574705 2 3ehf


+1.2941301137409206 4
1eY
+3.0672655348921618 4 1ehF
6
Y=1.5883904892195118 6 3ey


+6.5792844833798811 5 2ey


+4.3448235545907821 4 2ey


+5.0430317113692086 3
2ey


+9.0475494963689174 2
2ey


+1.3063404640238935 1
1ey


+4.6491915432714381 0
1ey


+2.5214268095918969 5 2ehf


+1.0297826627077401 4
1ehf


+1.1952675542752805 3 1ehf


+2.1443930908325182 2
1ehf


+3.0962057366495105 1 1ehf


+4.9881872517581938 0
1ehf


+1.5271151632415950 5 1eY
+3.6194719976664513 5 1ehF
7
Y=5.0565957696390162 6 3ey


+ 4.23539162426581075 3ey


+9.0603416352126546 4 3ey


+1.8723784992724177 3 2ey


+4.9888911059116470 1 1ey


+2.7778379949012472 0 1ey


+1.3708345905699068 6 3ehf


+1.0038457971067822 5 2ehf


+5.6604476160364535 4 3ehf


+4.4377933703203629 3 2ehf


+2.7937851702809663 1 1ehf


+6.5838563316055287 0 1ehf


+1.8625097589686893 6 1eY
+4.4144031047782634 1ehF
1n
y

=1.0109380023947052 6 5ey


+ 3.15173949574987365 3ey


+2.7187605964756889 4 3ey


+ 1.27072349154431082 1ey


+7.5811479542621490 1 2ey


+ 4.83618326056246990 1ey


+8.7898513623300566 5 4ehf


+ 6.44383480969069804 3ehf


+6.2026529973672723 2 2ehf


+ 1.79683585043920491
1ehf


+3.1560924195242474 0 1ehf


+ 1.47745108183533722 3eY
+3.5017613257625627 2 3ehF
+ 1.68201280039804955 1eY
+3.9866006030837425 1ehF
+ 6.53510564686001916 2eY
+7.2587448184210451 7
2eY
+ 1.72042189357299797 1ehF.