ACMAC

Borcea, Liliana

Issa, Leila

Tsogka, Chrysoula

English

Source localization in random acoustic waveguides

del Cueto, F. Gonzalez

Papanicolaou, George

Filtering random layering effects in imaging

Karavelas, Menelaos I.

ACMAC’s PrePrint Repository
Exact geometric and algebraic computations in CGAL
Menelaos I. Karavelas
Original Citation:
Karavelas, Menelaos I.
(2010)
Exact geometric and algebraic computations in CGAL.
Proceedings of the 3rd International Congress on Mathematical Software (ICMS 2010), Lecture
Notes in Computer Science, Springer, 6327. pp. 96-99. ISSN 0302-9743
This version is available at: http://preprints.acmac.uoc.gr/8/
Available in ACMAC’s PrePrint Repository: September 2011
ACMAC’s PrePrint Repository aim is to enable open access to the scholarly output of ACMAC.
http://preprints.acmac.uoc.gr/Exact geometric and algebraic computations
in CGAL?
Menelaos I. Karavelasy;z
yDept. Applied Mathematics, University of Crete, GR-714 09 Heraklion, Greece
mkaravel@tem.uoc.gr
http://www.tem.uoc.gr/~mkaravel
zInstitute of Applied and Computational Mathematics,
Foundation for Research and Technology - Hellas,
P.O. Box 1385, GR-711 10 Heraklion, Greece
Abstract. We summarize recent progress and on-going developments
for exact geometric and algebraic computations within the Computa-
tional Geometry Algorithms Library (Cgal). We detail the existing ma-
chinery used in ecient, exact and robust implementations of various
geometric entities.
1 Introduction
Implementing geometric algorithms is far from being a trivial and straightfor-
ward process. Not only do we have to accommodate potentially complicated data
structures, but also account for computations involving numerical data. These
computations, called predicates, are functions of a constant number of geometric
objects (e.g., points) returning a small number of values (e.g., a sign), and aect
the choices made by the algorithm. The correct or consistent evaluation of pred-
icates is vital in order for an implementation to be robust and for the outcome
of the algorithm to be usable. However, even the simplest possible calculations
may lead to inconsistent or wrong results [16], especially when the geometric
input data are in degenerate or almost degenerate congurations.
This phenomenon that has given rise to a variety of methodologies for en-
suring robustness of the implementation, while providing some guaranties for
the output. These methodologies include adaptive precision oating-point arith-
metic, the \topology-oriented approach", symbolic perturbations, controlled per-
turbations, and exact geometric computation | see [19] for a nice overview.
The exact geometric computation paradigm, along with the continued evolution
of software libraries oering exact number types [9,12,18], provides a platform
for implementing correct and robust geometric algorithms without the need for
arithmetic considerations. When combined with arithmetic and geometric lter-
ing techniques, as well as lazy geometric evaluation considerations the overhead
? Partially supported by the FP7-REGPOT-2009-1 project \Archimedes Center for
Modeling, Analysis and Computation".2 Menelaos I. Karavelas
of exact geometric computation can turn out to be negligible, not only when
taking into account the easiness of development and the correctness guarantees
that it provides, but also in absolute terms.
2 The Computational Geometry Algorithms Library
The Computational Geometry Algorithms Library (Cgal) [8] is a software li-
brary for computational geometry algorithms and data structures. It started in
1995 as a European project, and currently it is a mature Open Source project. It
has gone through more than 15 public releases and its latest version, version 3.6
[23], is comprised of more than 600,000 lines of C++ code. The goal of the Cgal
Open Source project is \to provide easy access to ecient and reliable geometric
algorithms in the form of a C++ library", as it is stated in the project web page.
Due to the dual nature of geometric algorithms, namely combinatorics/data
structures and computations on geometric objects, the design paradigm for the
algorithms in Cgal follows a clear-cut separation between the combinatorial
aspects of these algorithms and the numerical computations. This separation is
evident in the template parameters Cgal classes. For example, algorithms for
computing triangulated Delaunay graphs have two template parameters called
respectively (triangulation) traits and (triangulation) data structure. All com-
binatorial operations, as well as the data structures representing the Delaunay
graphs are provided by the data structure template parameter, whereas all nu-
merical issues are abstracted and encapsulated in the traits template parameter.
Currently, the Cgal library oers algorithms for tackling a variety of geo-
metric problems | see the Package Overview section of the latest Cgal manual
[23] for a complete listing of the packages oered. Algorithms in Cgal rely on
concepts; the library typically provides at least one model for each concept. This
design allows for modularity and exchangeability of components, making Cgal
an ideal platform for benchmarking dierent ways of implementing the same
concept. Flexibility is gained by means of template parameters and has proven
to go quite far with respect to the kind and complexity of the functionality
provided to the end-user; see, e.g., the case of 2D and 3D triangulations [3],
as well as that of 2D arrangements [25]. Robustness is ensured via exact predi-
cates provided by either a kernel or a geometric traits class. The use of various
arithmetic/geometric ltering techniques [5,20,24,15], and symbolic perturba-
tions (e.g., [10]) has counter-balanced the additional cost of performing exact
arithmetic in degenerate or almost degenerate congurations of the input data.
3 Algebraic computations in CGAL
During the last decade a considerable amount of work in Computational Geom-
etry has shifted towards computing geometric entities involving non-linear geo-
metric objects [4]. If we are to categorize these eorts, they should be split into
two categories: (1) problems/implementations involving computations on alge-
braic numbers of small/bounded algebraic degree (2) problems/implementationsExact geometric and algebraic computations in Cgal 3
involving computations on algebraic numbers of large/arbitrary algebraic degree
What is common in both cases, however, is that, either at the analysis or at the
implementation level, the need for support for algebraic tools became apparent.
Cgal started as a project oering geometric algorithms for simple objects,
such as points, linear segments and circles; as a result the provided algorithms
required support for the exact computation of quantities involving only ratio-
nal operations (or limited support for square roots). Cgal's evolution over the
years reects the shift in interest towards curvilinear objects. As of release 3.0,
Cgal oers packages for computing the 2D additively weighted Voronoi diagram
(it requires support for algebraic numbers of degree 2) [11], and for computing
arrangements of conic curves [24]. A package for computing the 2D Euclidean
segment Voronoi diagram was introduced in release 3.1 (it requires support for
algebraic number of algebraic degree 4) [15], while in release 3.2 we have the
introduction of the 2D Circular Kernel, the rst kernel designed for non-linear
geometric objects [7], accompanied by a specialized, and with limited function-
ality, algebraic kernel for degree 2 algebraic numbers. In the same release a
framework for Kinetic Data Structures was introduced [22], while the Cgal ar-
rangements' package extended its applicability arbitrary degree B ezier curves
[13]: in both cases, support for operations on large/arbitrary degree polynomials
and large/arbitrary degree algebraic numbers, namely root isolation and root
comparison, has been the computational core, and relied primarily on either in-
ternal (to the package) code for algebraic computations, or on algebraic numbers
provided by external libraries, such as CORE [9].
A parallel eort had been underway by the EXACUS project [1]; as of Cgal's
release 3.3 the two projects started to merge, and Cgal changed its underlying
structure: the library moved from being number-type centric to relying on a
concrete and well-designed platform of algebraic foundations [14]. In release 3.4
we have the formal introduction on polynomials and modular arithmetic, whereas
on the geometry side the 2D Circular Kernel got a three-dimensional counterpart:
the 3D Spherical Kernel [6]. With the latest public release 3.6, Cgal provides
the rst model of an algebraic kernel for arbitrary degree univariate polynomials
[17] based on the RS library [21], while work for a univariate algebraic kernel
based on the bitstream Descartes' algorithm and a bivariate algebraic kernel
based on the curve analysis approach, is currently underway and is expected to
be part of the next public release of Cgal [2].
References
1. Berberich, E., Eigenwillig, A., Hemmer, M., Hert, S., Kettner, L., Mehlhorn, K.,
Reichel, J., Schmitt, S., Sch omer, E., Wolpert, N.: EXACUS: Ecient and Ex-
act Algorithms for Curves and Surfaces. In: Proc. 13th European Symposium on
Algorithms (ESA). pp. 155{166 (2005)
2. Berberich, E., Hemmer, M., Kerber, M.: A generic algebraic kernel for non-linear
geometric applications. Research Report 7274, INRIA (2010)
3. Boissonnat, J.D., Devillers, O., Pion, S., Teillaud, M., Yvinec, M.: Triangulations
in CGAL. Comput. Geom.-Theor. Appl. 22, 5{19 (2002)4 Menelaos I. Karavelas
4. Boissonnat, J.D., Teillaud, M. (eds.): Eective Computational Geometry for
Curves and Surfaces. Springer-Verlag, Mathematics and Visualization (2006)
5. Br onnimann, H., Burnikel, C., Pion, S.: Interval arithmetic yields ecient dynamic
lters for computational geometry. Discrete Appl. Math. 109, 25{47 (2001)
6. de Castro, P.M.M., Cazals, F., Loriot, S., Teillaud, M.: Design of the CGAL 3D
spherical kernel and application to arrangements of circles on a sphere. Comput.
Geom.-Theor. Appl. 42(6-7), 536{550 (2009)
7. de Castro, P.M.M., Pion, S., Teillaud, M.: Exact and ecient computations on
circles in CGAL. In: Proc. 23rd European Workshop on Computational Geometry.
pp. 219{222. Technische Universit at Graz, Austria (2007)
8. Cgal, Computational Geometry Algorithms Library, http://www.cgal.org
9. Core Number Library, http://cs.nyu.edu/exact/core_pages
10. Devillers, O., Teillaud, M.: Perturbations and vertex removal in a 3D Delau-
nay triangulation. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms
(SODA). pp. 313{319 (2003)
11. Emiris, I.Z., Karavelas, M.I.: The predicates of the Apollonius diagram: algorithmic
analysis and implementation. Comput. Geom.-Theor. Appl. 33(1-2), 18{57 (2006)
12. GMP, GNU Multiple Precision Arithmetic Library, http://www.swox.com/gmp/
13. Hanniel, I., Wein, R.: An exact, complete and ecient computation of arrange-
ments of B ezier curves. In: Proc. ACM Symposium on Solid and Physical Modeling.
pp. 253{263 (2007)
14. Hemmer, M.: Algebraic foundations. In: CGAL User and Reference Manual. CGAL
Editorial Board, 3.6 edn. (2010), http://www.cgal.org/Manual/3.6/doc_html/
cgal_manual/packages.html#Pkg:AlgebraicFoundations
15. Karavelas, M.I.: A robust and ecient implementation for the segment Voronoi
diagram. In: Proc. International Symposium on Voronoi Diagrams in Science and
Engineering (VD2004). pp. 51{62. Hongo, Tokyo, Japan (2004)
16. Kettner, L., Mehlhorn, K., Pion, S., Schirra, S., Yap, C.K.: Classroom examples
of robustness problems in geometric computations. Comput. Geom.-Theor. Appl.
40(1), 61{78 (2008)
17. Lazard, S., Pe~ naranda, L., Tsigaridas, E.P.: Univariate algebraic kernel and appli-
cation to arrangement. In: Proc. 8th International Symposium on Experimental
Algotirhms (SEA). LNCS, vol. 5526, pp. 209{220. Dortmund, Germany (2009)
18. LEDA: Library of ecient data-structures and algorithms, http://www.mpi-sb.
mpg.de/LEDA/leda.html
19. Li, C., Pion, S., Yap, C.K.: Recent progress in exact geometric computation. J.
Log. Algebr. Program. 64(1), 85{111 (2005)
20. Melquiond, G., Pion, S.: Formally certied oating-point lters for homogeneous
geometric predicates. Informatique Th eorique et Applications 41(1), 57{69 (2007)
21. The RS library, http://www-salsa.lip6.fr/~rouillie/Software.html
22. Russel, D., Karavelas, M.I., Guibas, L.J.: A package for exact kinetic data struc-
tures and sweepline algorithms. Comp. Geom.-Theor. Appl. 38(1-2), 111{127
(2007)
23. The CGAL Project: CGAL User and Reference Manual. CGAL Edito-
rial Board, 3.6 edn. (2010), http://www.cgal.org/Manual/3.6/doc_html/cgal_
manual/packages.html
24. Wein, R.: High-level ltering for arrangements of conic arcs. In: Proc. 10th Euro-
pean Symposium on Algorithms (ESA). LNCS, vol. 2461, pp. 884{895 (2002)
25. Wein, R., Fogel, E., Zukerman, B., Halperin, D.: Advanced programming tech-
niques applied to CGAL's arrangement package. In: Proc. Library-Centric Software
Design Workshop (LCSD'05). pp. 24{33 (2005)

Exact geometric and algebraic computations in CGAL

Katsoulakis, M. A.

Majda, A. J.

Sopasakis, A.

Hybrid deterministic stochastic systems with microscopic look-ahead dynamics

Dutykh, D.

Katsaounis, Th.

Mitsotakis, D.

ACMAC’s PrePrint Repository
Finite volume schemes for Boussinesq type equations
D. Dutykh and Th. Katsaounis and D. Mitsotakis
Original Citation:
Dutykh, D. and Katsaounis, Th. and Mitsotakis, D.
(2010)
Finite volume schemes for Boussinesq type equations.
Proceedings of Colloque EDP-Normandie. pp. 15-21.
This version is available at: http://preprints.acmac.uoc.gr/10/
Available in ACMAC’s PrePrint Repository: September 2011
ACMAC’s PrePrint Repository aim is to enable open access to the scholarly output of ACMAC.
http://preprints.acmac.uoc.gr/
FINITE VOLUME SCHEMES FOR BOUSSINESQ TYPE EQUATIONS
DENYS DUTYKH∗, THEODOROS KATSAOUNIS, AND DIMITRIOS MITSOTAKIS
Abstract. Finite volume schemes are commonly used to construct approximate solutions to
conservation laws. In this study we extend the framework of the finite volume methods to
dispersive water wave models, in particular to Boussinesq type systems. We focus mainly on
the application of the method to bidirectional nonlinear, dispersive wave propagation in one
space dimension. Special emphasis is given to important nonlinear phenomena such as solitary
waves interactions.
1. Introduction
The simulation of water waves in realistic and complex environments is a very challenging
problem. Most of the applications arise from the areas of coastal and naval engineering, but also
from natural hazards assessment. In this work we will study numerically bidirectional water wave
models. Specifically, we consider the following family of Boussinesq type systems of water wave
theory, introduced in [4], written in nondimensional, unscaled variables
ηt + ux + (ηu)x + a uxxx − b ηxxt = 0,
ut + ηx + uux + c ηxxx − d uxxt = 0, (1.1)
where a, b, c, d ∈ R, η = η(x, t), u = u(x, t) are real functions defined for x ∈ R and t ≥ 0.
a =
1
2
(θ2 − 1
3
)ν, b =
1
2
(θ2 − 1
3
)(1− ν), c = 1
2
(1 − θ2)µ, d = 1
2
(1 − θ2)(1 − µ),
where 0 ≤ θ ≤ 1 and µ, ν ∈ R.
Finite volume method is well known for its accuracy, efficiency and robustness for approximat-
ing solutions to conservation laws and in particular to nonlinear shallow water equations. The
aforementioned bidirectional models (1.1) are rewritten in a conservative form and discretization
by the finite volume method follows. Three different numerical fluxes are employed
• a simple average flux (m-scheme),
• a central flux, (KT-scheme) [16, 14], as a representative of central schemes,
• a characteristic flux (CF-scheme), as a representative of the linearized Riemann solvers,
[10].
along with TVD, UNO and WENO reconstruction techniques, [18, 12, 15]. Time discretization
is based on Runge-Kutta (RK) methods which preserve the total variation diminishing (TVD)
property of the finite volume scheme, [17]. We use explicit RK methods since we work with BBM
type systems (1.1) and not with KdV equation which is well known to be notoriously stiff.
The present text is organized as follows. In Section 1 we present the mathematical model
under consideration and the context of this study. Then, Section 2 contains a brief description
of various numerical schemes we implemented. Accuracy tests and several numerical results on
head-on collision of solitary waves are presented in Section 3. Finally, some conclusions of this
study are outlined in Section 4.
Key words and phrases. finite volume method; dispersive waves; solitary waves; runup; water waves.
∗ Corresponding author.
1
ha
l-0
05
53
75
4,
 ve
rs
ion
 1
 - 
9 
Ja
n 
20
11
2 D. DUTYKH, T. KATSAOUNIS, AND D. MITSOTAKIS
2. Numerical schemes
In the present section we generalize the finite volume method to systems (1.1) of dispersive
PDEs. Boussinesq system (1.1) can be rewritten in a conservative like form as follows:
(I−D)vt + [F(v)]x + [G(v)]x = 0, (2.1)
where v = (η, u)T , F(v) = ((1 + η)u, η + 12u
2)T , G(v) = (a uxx, c ηxx), and D = diag (b ∂2x, d ∂
2
x).
The simplest discretization is based on the average fluxes Fm for F and Gm for G. For the other
two choices of the numerical flux F the evaluation of Jacobian is needed. Let A denotes the
Jacobian of F, then
A =
(
u 1 + η
1 u
)
,
with eigenvalues λi = u ± √1 + η, i = 1, 2. It is readily seen, since F is a hyperbolic flux, that
A can be decomposed as A = LΛR thus for the characteristic flux FCF we have with µ = W+V2 ,
si = sign(λi), i = 1, 2
A(W,V ) =
( 1
2 (s1 + s2)
1
2
√
1 + µ1(s1 − s2)
s1−s2
2
√
1+µ1
1
2 (s1 + s2)
)
.
For evaluating the numerical fluxes F , G simple cell averages or higher order approximations such
as UNO2 or WENO can be used. For more details we refer to our original research article [9].
Remark 1. The discretization of the elliptic operator D is based on the standard centered dif-
ference. This is a second order accurate approximation and it is compatible with the TVD2 and
UNO2 reconstructions. For higher order interpolation we need to modify the elliptic and flux dis-
cretization to match the reconstruction’s order of approximation. Indeed, the finite volume scheme
is modified as
d
dt
[
Vi−1 + 10Vi +Vi+1
12
− (b, d)Vi+1 − 2Vi +Vi−1
∆x2
]
+
Hi−1 + 10Hi +Hi+1
12
= 0
where Hi = 1∆x(Fi+ 12 − Fi− 12 ) + 1∆x(Gi+ 12 − Gi− 12 ), is a fourth order accurate approximation.
Remark 2. In the sequel for the discretization of the dispersive term G we use mainly the average
numerical flux Gm defined as Gm
i+ 1
2
= (a, c)Yi+Yi+12 , where Yi =
Vi+1−2Vi+Vi−1
∆x2 . In case of higher
order WENO reconstructions we use the average numerical flux based on the reconstructed values
of Yi i.e. the flux Glmi+ 1
2
= (a, c)
Y
L
i+1
2
+YR
i+1
2
2 , where Y
L
i+ 1
2
and YR
i+ 1
2
are reconstructed values of
Yi.
2.0.1. Boundary conditions. In the case of Bona-Smith type systems with flat bottom we consider
herein only the initial-periodic boundary value problem which is known to be well-posed [1].
3. Numerical results
For the Boussinesq system (1.1) we present first results demonstrating the accuracy of the finite
volume scheme. Then, we study interaction of solitary waves.
3.1. Accuracy test, validation. We consider the initial value problem with periodic boundary
conditions for the Bona-Smith systems with known solitary wave solutions [7] to study the accuracy
of the finite volume method:
η(ξ) = η0 sech
2(λξ),
u(ξ) = B η(ξ),
with
η0 =
9
2 · θ
2−7/9
1−θ2 , cs =
4(θ2−2/3)√
2(1−θ2)(θ2−1/3)
,
λ = 12
√
3(θ2−7/9)
(θ2−1/3)(θ2−2/3) , B =
√
2(1−θ2)
θ2−1/3 .
ha
l-0
05
53
75
4,
 ve
rs
ion
 1
 - 
9 
Ja
n 
20
11
FINITE VOLUME SCHEMES FOR BOUSSINESQ TYPE EQUATIONS 3
(a) Average Flux
∆x Rate(E2h) Rate(E
∞
h )
0.5 1.910 1.978
0.25 1.910 1.954
0.125 1.923 1.937
0.0625 1.936 1.941
0.03125 1.946 1.948
(b) TVD2 MinMod
∆x Rate(E2h) Rate(E
∞
h )
0.5 2.042 2.032
0.25 2.033 2.029
0.125 2.026 2.023
0.0625 2.021 2.019
0.03125 2.017 2.016
Table 1. Rates of convergence.
0 20 40 60 80 100 120 140 160 180 2000.44
0.45
0.46
0.47
0.48
0.49
0.5
0.51
t
‖
U
‖
h
,∞
 
 
CF−UNO2
CF−TVD2
average
(a) Evolution of η amplitude
0 20 40 60 80 100 120 140 160 180 2001.15
1.2
1.25
1.3
1.35
1.4
1.45
1.5
t
I h1
 
 
CF−UNO2
CF−TVD2
average
(b) Evolution of Ih
1
Figure 1. Preservation of the solitary wave amplitude and conservation of the
invariant Ih1 : G
m flux with Minmod limiter
We fix θ2 = 8/10 in the system and an analytic solitary wave of amplitude η0 = 1/2 is used as
the exact solution in [−50, 50] computed up to T = 100. The error is measured with respect to
discrete L2 and L∞ norms, namely we use:
E2h(k) = ‖Uk‖h/‖U0‖h, ‖Uk‖h =
(∑
i
∆x|Uki |2
)1/2
,
E∞h (k) = ‖Uk‖h,∞/‖U0‖h,∞, ‖Uk‖h,∞ = max
i
|Uki |,
where Uk = {Uki }i denotes the solution of the fully-discrete scheme at the time tk = k∆t. The
expected theoretical order of convergence was confirmed for all finite volume methods we presented
above. Two indicative cases are reported in Table 1 for the average flux and TVD2 implementation
with MinMod limiter.
We also check the preservation of the invariant I1(t) =
∫
R
(η2(x, t) + (1 + η(x, t))u2(x, t) −
c η2x(x, t)− a u2x(x, t)) dx by computing its discrete counterpart:
Ih1 =
∑
i
∆x
(
η2i + [(1 + ηi)ui]
2 − c
[
ηi+1 − ηi
∆x
]2
− a
[
ui+1 − ui
∆x
]2)
, (3.1)
as well as the discrete mass Ih0 = ∆x
∑
i ηi. Figure 1 shows the evolution of the amplitude and the
invariant Ih1 of the solitary wave up to T = 200. The comparison of various methods is performed.
We observe that the UNO2 reconstruction is more accurate while KT and the CF schemes show
comparable performance. We note that the invariant Ih0 = 1.932183566158 conserved the digits
shown for all numerical schemes. In this experiment we took ∆x = 0.1, ∆t = ∆x/2.
ha
l-0
05
53
75
4,
 ve
rs
ion
 1
 - 
9 
Ja
n 
20
11
4 D. DUTYKH, T. KATSAOUNIS, AND D. MITSOTAKIS
(a) Bona-Smith
Ih1
m-flux 0.000944236
UNO2 0.00094423
TVD2 0.00094
WENO3 0.00094423
(b) BBM-BBM
Ih1
m-flux 0.00092793
UNO2 0.00092793
TVD2 0.00092
WENO3 0.00092793
Table 2. Preservation of the invariant Ih1 .
3.2. Head-on collisions. The head-on collision of two counter-propagating solitary waves is char-
acterized by the change of the shape along with a small phase-shift of the waves as a consequence
of the nonlinearity and dispersion. These effects have been studied extensively before by numer-
ical means using high order numerical methods such as finite differences, [3], spectral and finite
element methods [2] and experimentally in [8]. In Figure 2 we present the numerical solutions of
the BBM-BBM system and the Bona-Smith system with θ2 = 9/11 (in dimensional and unscaled
variables) along with the experimental data from [8]. The spatial variable is expressed in centime-
ters while the time in seconds. The solutions were obtained using the CF-scheme with UNO2 and
WENO3 reconstruction using ∆x = 0.05 cm and ∆t = 0.01 s. For this experiment we constructed
solitary waves for Boussinesq systems by solving the respective o.d.e’s system in the spirit of [5]
such that they fit to experimentally generated solitary waves before the collision. The speeds of
the right and left-traveling solitary waves are cr,s = 0.854 m/s and cl,s = 0.752 m/s respectively.
We observe that Boussinesq models converge to the same numerical solution with all numerical
schemes we tested. A very good agreement with the experimental data is observed. The discrete
mass for the Bona-Smith system is Ih0 = 0.0059904310418 and for the BBM-BMM system is
Ih0 = 0.0059199389479 for all fluxes and reconstructions used. The variances in I
h
1 are mainly due
to different types of reconstruction and not to the choice of numerical fluxes. In Table 2 these
values are reported.
4. Conclusions
Initially, the finite volume method was proposed by S. Godunov [11] to compute approximate
solutions to hyperbolic conservation laws. In the present study we made a further attempt to
generalize this method to the framework of dispersive PDEs. This type of equations arises naturally
in many physical problems. In the water wave theory dispersive equations have been well known
since the pioneering work of J. Boussinesq [6] and Korteweg-de Vries [13]. Currently, the so-
called Boussinesq-type models become more and more popular as an operational model for coastal
hydrodynamics and other fields of engineering.
We extend the finite volume framework to dispersive models. We tested several choices of nu-
merical fluxes (average, Kurganov-Tadmor, characteristic), various reconstruction methods rang-
ing from classical (TVD2, UNO2) to modern approaches (WENO3, WENO5). Various choices
of limiters have been also tested out. Advantages of specific methods are discussed and some
recommendations are outlined.
Acknowledgment
D. Dutykh acknowledges the support from French Agence Nationale de la Recherche, project
MathOcean (Grant ANR-08-BLAN-0301-01) and Ulysses Program of the French Ministry of For-
eign Affairs under the project 23725ZA. The work of Th. Katsaounis was partially supported by Eu-
ropean Union FP7 programCapacities (Regpot 2009-1), through ACMAC (http://acmac.tem.uoc.gr).
The work of D. Mitsotakis was supported by Marie Curie Fellowship No. PIEF-GA-2008-219399
of the European Commission. We would like to thank also Professors Diane Henderson and Costas
Synolakis for providing us their experimental data and Profs Jerry Bona and Vassilios Dougalis
for very helpful discussions.
ha
l-0
05
53
75
4,
 ve
rs
ion
 1
 - 
9 
Ja
n 
20
11
FINITE VOLUME SCHEMES FOR BOUSSINESQ TYPE EQUATIONS 5
−300 −200 −100 0 100 200 300−0.5
0
0.5
1
1.5
2
2.5
3
x
η
 
 
Bona−Smith θ2=9/11
BBM−BBM
Experimental data
(a) t = 18.29993s
−300 −200 −100 0 100 200 300−0.5
0
0.5
1
1.5
2
2.5
3
x
η
 
 
Bona−Smith θ2=9/11
BBM−BBM
Experimental data
(b) t = 18.80067s
−300 −200 −100 0 100 200 300−0.5
0
0.5
1
1.5
2
2.5
3
x
η
 
 
Bona−Smith θ2=9/11
BBM−BBM
Experimental data
(c) t = 19.00956s
−300 −200 −100 0 100 200 300−0.5
0
0.5
1
1.5
2
2.5
3
x
η
 
 
Bona−Smith θ2=9/11
BBM−BBM
Experimental data
(d) t = 19.15087s
−300 −200 −100 0 100 200 300−0.5
0
0.5
1
1.5
2
2.5
3
x
η
 
 
Bona−Smith θ2=9/11
BBM−BBM
Experimental data
(e) t = 19.19388s
−300 −200 −100 0 100 200 300−0.5
0
0.5
1
1.5
2
2.5
3
x
η
 
 
Bona−Smith θ2=9/11
BBM−BBM
Experimental data
(f) t = 19.32904s
Figure 2. Head-on collision of two solitary waves: —: BBM-BBM, −−: Bona-
Smith (θ2 = 9/11), •: experimental data of [8]
References
[1] D. C. Antonopoulos, V. A. Dougalis, and D. E. Mitsotakis. Initial-boundary-value problems for the Bona-Smith
family of Boussinesq systems. Advances in Differential Equations, 14:27–53, 2009. 2
[2] D. C. Antonopoulos, V. A. Dougalis, and D. E. Mitsotakis. Numerical solution of Boussinesq systems of the
Bona-Smith family. Appl. Numer. Math., 30:314–336, 2010. 4
[3] J. L. Bona and M. Chen. A Boussinesq system for two-way propagation of nonlinear dispersive waves. Physica
D, 116:191–224, 1998. 4
[4] J.L. Bona, M. Chen, and J.-C. Saut. Boussinesq equations and other systems for small-amplitude long waves
in nonlinear dispersive media. I: Derivation and linear theory. Journal of Nonlinear Science, 12:283–318, 2002.
1
ha
l-0
05
53
75
4,
 ve
rs
ion
 1
 - 
9 
Ja
n 
20
11
6 D. DUTYKH, T. KATSAOUNIS, AND D. MITSOTAKIS
−300 −200 −100 0 100 200 300−0.5
0
0.5
1
1.5
2
2.5
3
x
η
 
 
Bona−Smith θ2=9/11
BBM−BBM
Experimental data
(a) t = 19.84514s
−300 −200 −100 0 100 200 300−0.5
0
0.5
1
1.5
2
2.5
3
x
η
 
 
Bona−Smith θ2=9/11
BBM−BBM
Experimental data
(b) t = 20.49949s
Figure 2. (Cont’d) Head-on collision of two solitary waves. —: BBM-BBM,
−−: Bona-Smith (θ2 = 9/11), •: experimental data of [8]
[5] J.L. Bona, V.A. Dougalis, and D.E. Mitsotakis. Numerical solution of KdV-KdV systems of Boussinesq equa-
tions: I. The numerical scheme and generalized solitary waves. Mat. Comp. Simul., 74:214–228, 2007. 4
[6] J. Boussinesq. The´orie de l’intumescence liquide appele´e onde solitaire ou de translation se propageant dans
un canal rectangulaire. C.R. Acad. Sci. Paris Se´r. A-B, 72:755–759, 1871. 4
[7] M. Chen. Exact traveling-wave solutions to bidirectional wave equations. International Journal of Theoretical
Physics, 37:1547–1567, 1998. 2
[8] W. Craig, P. Guyenne, J. Hammack, D. Henderson, and C. Sulem. Solitary water wave interactions. Phys.
Fluids, 18:57–106, 2006. 4, 5, 6
[9] D. Dutykh, Th. Katsaounis, and D. Mitsotakis. Finite volume schemes for dispersive wave propagation and
runup. Submitted, http://hal.archives-ouvertes.fr/hal-00472431/, 2010. 2
[10] J.-M. Ghidaglia, A. Kumbaro, and G. Le Coq. Une me´thode volumes-finis a` flux caracte´ristiques pour la
re´solution nume´rique des syste`mes hyperboliques de lois de conservation. C. R. Acad. Sci. I, 322:981–988,
1996. 1
[11] S.K. Godunov. Reminiscences about difference schemes. J. Comput. Phys., 153:6–25, 1999. 4
[12] A. Harten and S. Osher. Uniformly high-order accurate nonscillatory schemes, I. SIAM J. Numer. Anal.,
24:279–309, 1987. 1
[13] D.J. Korteweg and G. de Vries. On the change of form of long waves advancing in a rectangular canal, and on
a new type of long stationary waves. Phil. Mag., 39(5):422–443, 1895. 4
[14] A Kurganov and E Tadmor. New high-resolution central schemes for nonlinear conservation laws and
convection-diffusion equations. J. Comput. Phys., 160(1):241–282, 2000. 1
[15] X.-D. Liu, S. Osher, and T. Chan. Weighted essentially non-oscillatory schemes. J. Comp. Phys., 115:200–212,
1994. 1
[16] H. Nessyahu and E. Tadmor. Nonoscillatory central differencing for hyperbolic conservation laws. J. Compu-
tational Physics, 87(2):408–463, 1990. 1
[17] R. J. Spiteri and S. J. Ruuth. A new class of optimal high-order strong-stability-preserving time discretization
methods. SIAM Journal on Numerical Analysis, 40:469–491, 2002. 1
[18] P.K. Sweby. High resolution schemes using flux limiters for hyperbolic conservation laws. SIAM J. Numer.
Anal., 21(5):995–1011, 1984. 1
LAMA UMR 5127, Universite´ de Savoie, CNRS, Campus Scientifique, 73376 Le Bourget-du-Lac France
E-mail address: Denys.Dutykh@univ-savoie.fr
URL: http://www.lama.univ-savoie.fr/~dutykh/
Department of Applied Mathematics, University of Crete, Heraklion, 71409 Greece
E-mail address: thodoros@tem.uoc.gr
URL: http://www.tem.uoc.gr/~thodoros/
UMR de Mathe´matiques, Universite´ de Paris-Sud, Baˆtiment 425, P.O. Box, 91405 Orsay, France
E-mail address: Dimitrios.Mitsotakis@math.u-psud.fr
URL: http://sites.google.com/site/dmitsot/
ha
l-0
05
53
75
4,
 ve
rs
ion
 1
 - 
9 
Ja
n 
20
11


Finite volume schemes for Boussinesq type equations

Antonopoulou, D. C.

Plexousakis, M.

Discontinuous Galerkin methods for the linear Schrödinger equation in non-cylindrical domains

del Pino, Manuel

Dolbeault, Jean

Filippas, Stathis

Tertikas, Achilles

A logarithmic Hardy inequality

Nupur, Gupta

Neela, Nataraj

Amiya K., Pani

On the optimal control problem of laser surface hardening

Efremidis, Nikolaos K.

Zhang, Peng

Chen, Zhigang

Christodoulides, Demetrios N.

Rüter, Christian E.

Kip, Detlef

Wave propagation in waveguide arrays with alternating positive and negative couplings

Abruptly autofocusing waves

University of Crete

Not a member yet