A parametrization technique to improve the robustness of Newton's method, with application to Richards' equation

(1)

A parametrization technique to improve the

robustness of Newton’s method, with

application to Richards’ equation.

Master thesis

Politecnico di Milano

MsC Computational Science and Engineering Advisor: Professor Luca Formaggia

Tutor: Guillaume Ench´ery, PhD

Submitted by: Sabrina Bassetto Matr. 874972

(2)

4 Description of the code and preliminary validations 33 4.1 The prototype . . . 33 Mesh . . . 33 2D Mesh . . . 33 1D Mesh . . . 36 Numerics . . . 37 TPFAScheme . . . 37 NonLinearSystem . . . 37 NewtonSolver . . . 38 CancesBrooksCoreyParameterizedModel . . . 39 Physics . . . 40 Visualisation . . . 41 4.2 Preliminary validations . . . 42

Test for the Newton’s method on a linear Richards’ equation . . . 42

Test for Newton’s method on Richards’ equation . . . 46

Test for Newton’s method on Richards’ equation with parametrization . . . 51

Compilation . . . 57

Conclusions 58

Bibliography 59

(3)

Abstract

The simulation of the water flow in partially saturated porous media is significant in fields such as agriculture, hydrology, environment and waste management. The Richards’ equation is often use to model the movement of water in an unsaturated porous medium under the action of the gravity and capillarity, neglecting the air pressure. This equation is a nonlinear, degenerate elliptic-parabolic partial differential equation. Consequently, the resolution of the problem via analytical techniques becomes difficult, as well as the numerical resolution via Newton’s method. Over the years, several researchers have worked on this topic with the aim of increasing the robustness of the numerical resolution method. Generally, the solution is recovered using a switch of variable which consist in using as primary variable the saturation or the capillary pressure with respect to the physical conditions. More precisely, the problem is solved in saturation variable in the unsaturated region and in pressure variable elsewhere. In this work we investigate a method proposed in the literature to improve the performance of the switch of variable, which consists in the formulation of a parametrization allowing us to separate the dependence between the saturation and pressure variables, while keeping their derivatives bounded. We perform a numerical validation of this technique by presenting two test cases. Finally, we propose and validate with numerical experiments an alternative parametrization. The technique has been implemented in an original C++ prototype code. This prototype handles every step of the simulation like the management of the mesh, the set up of the physical laws, the numerical solution and, finally, the visualisation of the results.

(4)

Acknowledgments

Innanzitutto vorrei ringraziare il Professor Luca Formaggia per il suo aiuto, la sua disponibilit`a ed appoggio nei confronti dello stage effettuato presso IFPEN, Rueil-Mailmaison, dal quale nasce questo lavoro.

Je remercie mon encadrant Guillaume Enchéry pour sa patience, son aide et pour ses con-seils. Et merci aussi à Quang Huy Tran et à Clément Cancès pour leur soutien et aide.

Merci à les thésards Karine, Bastien, Julien et Thoi pour m’avoir bien accueilli, pour m’avoir soutenu et pour les soirées passées ensemble. J’ai trouvé l’IFPEN une ambiance de travail vrai-ment accueillantes. Merci à tous les collègues !

Grazie ai miei genitori per avermi dato la possibilità di intraprendere questo percorso ed ar-rivare fino a questo punto. Anche se a volte abbiamo divergenze di idee e non ci capiamo molto, siete importanti, vi voglio bene e spero di avervi reso orgogliosi. Grazie a mia sorella Chiara per aver sempre creduto e dimostrato tanta stima nei miei confronti. Grazie ai miei amici più cari Nicole, Peter, Matteo, Adrien ed ai miei compagni di università Valeria, Nicola, Elia, Carlo per i bei momenti passati insieme, per il sostegno e l’amicizia che mi avete dimostrato. E un ringraziamento anche alle due Silvia P. (purtroppo non avete solo lo stesso nome, ma anche la stessa iniziale del cognome!) per l’affetto, il sostegno e la stima conferitami.

Devo poi ringraziare la persona che mi ha fatto capire che l’economia non era la mia strada e che ha fatto nascere in me la passione per la matematica. Grazie professoressa Lucia per aver visto qualcosa di speciale in me, averci creduto ed avermi indirizzata a questa facolt`a.

Ed infine, grazie alla mia dolce met`a che mi ha accompagnata in questi anni, che mi ha sostenuta e che ha creduto in me quando io non ci credevo. Grazie Tommy per essermi rimasto accanto nonostante la distanza e le difficolt`a e per avermi aiutata ogni volta in cui ho avuto bisogno.

(5)

Introduction

A deep understanding of the water flow in partially saturated porous media is crucial in many fields of application, including agriculture, hydrology, environment and waste management. In the XIX-th century, the French engineer Henry Darcy pioneered the study of the fluid flow though this kind of medium, finding that the flow rate of a fluid in a porous medium is propor-tional to the hydraulic force applied to it. This idea then became what we know as the Darcy’s law. Actually, depending on the fact that the porous medium is saturated or not and if we are dealing with a slow or fast flow, there exist many different differential models for understanding and simulating such a system.

Let us consider, for example, a river flowing across the countryside, as depicted in Figure 1. The river saturates the soil with water in the riverbank, which contains a deep fracture. A

Figure 1: Cross-sectional view of a riverbank and the governing equations applied to each flow regime. Image taken from the website: https://cdn.comsol.com/wordpress/2017/02/cross-section-of-a-riverbank.png

water table divides the riverbank in two zones: a phreatic zone that is fully saturated and a vadose zone that is unsaturated. Richards’ Equation (1) was first set by Lorenzo A. Richards and it is used to model water flow in an unsaturated flow under the action of the gravitational force and capillarity effects. The equation is derived by substituting the Darcy equation into the mass conservation principle for the air and water-phase . Then the air-phase is neglected by assuming that it remains at athmospheric pressure. This approximation is reasonable in most cases because the mobility of air is much larger than that of water, due to the viscocity difference between the two fluids, when the air-phase pressure is assumed to be constant. Consequently, the air-phase mass balance equation can be eliminated and only the water-phase equation remains. The resulting equation reads

∂ts − ∇ · (λ(s)(∇p − g)) = 0, (1)

where we denote s the saturation variable, λ(s) the unsaturated hydraulic conductivity function, p = p(s) the capillary pressure and, finally, g is the gravity. This equation is a nonlinear,

(6)

CONTENTS 3

degenerate elliptic-parabolic partial differential equation. These two characteristics make it difficult to solve using traditional analytical techniques and impossible to solve in closed form, except for some particular cases. This difficulty is intesified by the range of initial and boundary conditions as well as by the soil water constitutive relations. Actually, the problem depends on two highly nonlinear relations: the unsaturated hydraulic conductivity function λ(s) and the capillary pressure p(s). These relations may not be smoothly differentiable at the extremes and, moreover, can present very high slopes. These nonlinearities and the elliptic degeneracy (which

Figure 2: Profile of the mobility function (left) and saturation (right), taken from [3]

arises whenever s = 0 implying λ(s) = 0) make the numerical resolution of Richards’ equation tough and computationally expensive. Over the years, existing schemes have been adapted in order to increase the robustness of the resolution method.

A brief state of the art

The main goal of the techniques proposed over the years was to improve the robustness of the Newton’s method, employed to attack the non-linearity of Equation (1). Applying a fully implicit temporal discretization, a Finite Volume scheme using TPFA (Two-Point Flux Approx-imation) for the diffusive term and an upwind discretization for the convective term to Equation (1), we obtain a discrete system for sn _{that we rewite in the form}

Fn(sn) = 0, (2)

n indexing time. The Newton’s method solves Equation (2) iteratively trough a series of linear problem:

sn,k+1= sn,k−hJFn(s

n,k₎i−1_F

n(sn,k), where JFn is the Jacobian matrix of Fn at s

n,k _{and k indicizes the iteration. In [10] we find a} classical convergence result for general Newton’s method showing that it converges quadratically towards the solution of Equation (2) under certain assumptions:

Theorem. Let xk

k∈N be the approximate solution of the abstract problem: Find x ∈ RN : F (x) = 0,

obtained starting from the initial guess x0∈ RN _{using the Newton iteration:}

xk+1 = xk− J(xk₎−1_{F (x}k_). ₍₃₎

If the following conditions are satisfied: • F (x) = 0 has a solution x∗, • J is Lipschitz continuous,

(7)

CONTENTS 4

• J(x∗_{) is nonsingular,}

then ∃δ > 0 such that if x0 ∈ B(x∗, δ) (the ball of radius δ centered at x∗), then xk _k∈N converges quadratically to x∗.

One of the important drawbacks of Newton’s method is that it is only locally convergent (convergence is achieved only if the initial guess is close enough to the actual solution) and involves the computation of the derivatives of the iteration function, which might be difficult to compute explicitely.

In 1995, Lehmann and Ackerer [11] proposed the use of Picard iterations and modified Picard iterations that can be considered as Newton’s method with an approximate Jacobian matrix. The aim is to accept a reduced rate of convergence in view of obtaining simplicity, efficiency and possibly robustness because, using classical or modified Picard, the need for an explicite knowledge of derivatives is eliminated or dramatically reduced.

Another approach to weaken the impact of non-linearities on the convergence of Newton’s method for this type of problem is to apply a switch of variable, consisting in using water saturation as primary variable in unsaturated zones and capillary pressure elsewhere (Forsyth at al. [7]). This strategy ensures to work with a non-singular Jacobian matrix and is designed in order to achieve rapid convergence in both the unsaturated and saturated regimes.

A possible alternative to the Newton’s and Picard’s methods is the so-called “relaxation scheme” used by Pop et al. in [14], which introduces a global regularizing term into the lin-earized problem related to Fn, namely Equation (3). It takes advantage of the monotonicity of the saturation-pressure relation to ensure a robust convergence behaviour with potentially less restrictive time-step constraints and better conditioned linear systems to solve.

Moreover we can find some works that propose globalization techniques like trust-region methods in Wang and Tchelepi [17]. Finally, several researchers have proposed a globalization approach that consists in combining Newton’s method with a slower converging technique, like Picard iteration or the scheme proposed by [14], in order to improve robustness for poor initial guesses while recovering quadratic convergence as intermediate iterates approach the actual solution of the problem (cf. [12] by List and Radu).

Meanwhile Williams et al. [1] introduced a Kirchhoff transform while working on homoge-neous media, defined as:

u(p) = Z p

−∞

λ(p)dp,

that has the effect of linearizing the gradient term using the chain rule ∇u = λ(p)∇p. This means that rather than evaluating ∇ · (λ(p)∇p), we deal with ∇ · (∇u) avoiding the nonlinear-ity. With this notion in mind, the paper by C. Canc`es and K. Brenner (see [3]) starts from the technique of the switch of variable between the saturation and the Kirchhoff transform and proposes a method to improve the robustness of the scheme. The contribution of this work constists in introducing a parametrization of the saturation graph in order to stabilize the New-ton’s algorithm, without implementing the switch of variable, which is automatically delegated to the parametrization.

It is worth observing that, concerning the non-linear solver, the choice of the time step clearly influences its performance. Richards’ equation solvers that use an implicit time discretization have to balance between the size of the time-step and the difficulty of resolution of the obtained system. As we can easily realize, if we use a very small time-step we will “help” Newton method in converging, since the initial guess at each iteration will be quite close to the actual solution, but we will increment the number of iterations and, consequently, the computational time needed to achieve a result.

(8)

CONTENTS 5

Content of the thesis

This work is focused on the study of the usage of a parametrization technique to the numerical solution of the Richards’ equation. We aim at highlighting its advantages and drawbacks and, possibly, formulating an alternative parametrization to the one from [3].

To this end, we go through the work of C. Canc`es and K. Brenner [3] by proposing a numer-ical validation of the approach through a test case, perfomed by ourselves, where the efficiency of the parametrization is highlighted. Then, the aim is to consider other parametrizations in order to find the one which makes the Newton’s method converging in a reduced number of iterations. In particular, we introduce a new parametrization taking inspiration from two-body mechanical problems, as fully developed in Section 1.3. Finally we evaluate its efficiency per-forming a numerical test.

All the simulations have been performed using a brand-new C++ prototype code for Finite Volume method, which does not lean on external libraries or tools, except for the library Eigen to implement linear algebra entities and operations in floating point arithmetics. The full description of the propotype is reported in the last chapter 4. It is divided in four main components:

• Mesh: which assembles and manages all the elements of the discrete mesh, previously generated by GMSH;

• Numerics: containing the numerical tools such as the Newton’s method solver, the evalu-ation of the transmissibilities for the TPFA scheme and so on;

• Physics: where we find the physical models used in the simulations, coded under the form of different classes;

• Visualisation: where we introduce a tool that creates a .vtk file to plot and post-process the solutions obtained by the simulations using ParaView.

Finally, a part of the Appendix is dedicated to test each implemented tool and, therefore, validate our whole code.

(9)

Chapter 1

The Richards equation

Let us denote by Ω a bounded open set of Rd(with d = 2, 3) representing a porous medium, by T > 0 a finite time horizon and by Q := Ω × (0, T ] the corresponding space-time cylinder. We want to find a saturation profile s : Q → [0, 1] and a water pressure p : Q → R such that, once setting porosity equal to one, is governed by the equation

∂ts − ∇ · (λ(s)(∇p − g)) = 0, (1.1)

where λ : [0, 1] → R+is the mobility function, a nondecreasing C2-function that satisfies λ(s) = 0 for s ≤ 0 and λ(s) > 0 for s > 0, and g ∈ Rd is the gravity vector. Pressure and saturation are supposed to be linked by some monotone relation, denoted by

s = S(p) in Q, (1.2)

where S is a non-decreasing function such that S : R → [0, 1]. We assume S(p) = 1 for all p ≥ 0, which corresponds to assume that water is the wetting phase. Moreover, we have that S ∈ L1_(R

−) implying that limp→−∞S(p) = 0. Figure 2 shows a plot of the typical saturation and mobility functions. Consequently, adding Dirichlet boundary conditions for the pressure and an initial condition for the saturation, our problem reads:

           ∂ts − ∇ · (λ(s)(∇p − g)) = 0 in Q, s = S(p), s|t=0= s0, p|_{∂Ω×(0,T )}= pD. (1.3)

Sometimes Equation (1.1) can be transformed by using the Kirchhoff transform: u(s) =

Z s

0

λ(ψ)∇p(ψ)dψ, (1.4)

also called generalized pressure, instead of p as primary variable and then s is deduced from the relation s = S(p) = ˜S(u). Therefore Equation (1.1) becomes

∂ts − ∇ · (λ(s)g − ∇u) = 0.

The problem is that this approach may lack of efficiency when one tries to solve the Richards’ equation numerically, in particular for dry media (saturation s close to 0) because, solving for u in this situation, the Newton’s methods faces difficulties in converging when solving the non-linear systems obtained from standard implicit numerical methods like the Finite Volume two-point flux approximation because the derivatives are extremely large.

Choosing the saturation s as primary variable yields the same difficulties highlighted above, for s in this case, in the saturated or almost saturated regions, i.e., where s ∼= 1. A classical approach to avoid these problems is to apply the so-called variable switch, which consists in changing the primary variable following the physical configuration.

(10)

CHAPTER 1. THE RICHARDS EQUATION 7

1.1 Use of a parametrization to solve an ordinary differential

equation

A technique to perform variable switch in an automatic way is to use a parametrization of the saturation graph. Let us explain, with a simple example, how the parametrization works.

Let’s consider the following problem:

u0(t) + um(t) = 0, (1.5)

where m > 1 and u(t0) = u0.

Denoting v = um, this problem can be, equivalently, rewritten in the form

vm1

0

(t) + v(t) = 0. (1.6)

Equations (1.5), (1.6) can be numerically solved by using an implicit Euler scheme, which gives φ(un+1, un) = u

n+1_{− u}n

∆t + u

n+1m = 0, using for the first one and

ψ(vn+1, vn) = v n+1_m1

− (vn₎m1

∆t + v

n+1_{= 0}

for the second one. These discrete non-linear equations are usually solved by means of Newton’s method which amounts solving at each iteration a linear equation that is

un+1,k+1− un+1,k= − ∂φ ∂un+1(u n+1,k_{, u}n₎ −1 φ(un+1,k, un) (1.7) for (1.5) and vn+1,k+1− vn+1,k = − ∂ψ ∂vn+1(v n+1,k_{, v}n₎ −1 ψ(vn+1,k, vn) (1.8)

for (1.6) . We can easily notice that for a large values of u, solving (1.7), the equation becomes problematic because φ0(u) is extremely large . Analogously for a small value of v, the resolution of 1.8 becomes problematic since ψ0(v) is unbounded.

Now let us introduce a parameter τ and make u, v depend on it. So we have v(τ ) = u(τ )m

Y (τ ) = u(τ ) + v(τ )

In terms of regularity, we require that v(τ ), u(τ ) are non-decreasing continuously differentiable functions and it has to be non-degenerate, namely 0 < α ≤ u0(τ ) + v0(τ ) ≤ β, with β ≥ α . Actually, the aim is to keep the derivatives of u and v under control. So we can impose, for example, knowing that u0(τ ) ≥ 0 and v0(τ ) ≥ 0, u0(τ )+v0(τ ) = Y0(τ ) = 1 or (u0(τ ))2_+(v0_{(τ ))}2₌ 1 and so on, by choosing the parametrization accordingly. Moreover, we may obtain a uniformly bounded derivative of the functions of interest and apply the Newton-Kantorovich theorem [10, pp.83] to claim convergence of Newton’s method.

Let us formulate a parametrization which satisfies the condition max(v0(τ ), u0(τ )) = 1.

(11)

Figure 1.1: Plot of the relation between u and v: v(τ ) = u(τ )m, where we have take m = 2 derivative of v is unitary, showed in Figure 1.1. Then we pass to v-variable. Indeed, thanks to this switch, we prevent the explosion of the derivatives. Actually, we will solve the problem for τ and hence, depending on its value, we evaluate u(τ ) and v(τ ). Let us denote τs the τ such that one has max(v0(τ ), u0(τ )) = 1. Clearly, imposing this condition, we ensure the control on the value of the derivatives, keeping them bounded.

Following the idea explained above, we want to work in u-variable for τ ∈ [0, τs], so here we have u(τ ) = τ and v is evaluated from u. Elsewhere we want to use v-variable and, consequently, here we have v(τ ) = τ and u is evaluated from v. Summarizing, we gain:

ˆ u(τ ) = ( τ if τ ∈ [0, τs], vm1(τ + τ_∗) if τ ≥ τ_s, and ˆ v(τ ) = ( um_{(τ )} _if _{τ ∈ [0, τ} s], τ + τ∗ if τ ≥ τs.

We can perform a translation, obtaining u(τ ) = ˆu(τ − τ∗) and v(τ ) = ˆv(τ − τ∗). Finally, the value of τ∗ is found enforcing continuity in the above formulation.

1.2 A monotone parametrization of the graph s = S(p)

Here we briefly describe the tecnique introduced in [3], which consists of parametrizing the graph S in order to stabilize Newton’s algorithm without implementing the variable switch procedure. Let us introduce two continuously differentiable non-decreasing functions

s : (τ∗, ∞) → [0, 1] and p : (τ∗, ∞) → (−∞, ∞), where τ∗ < 0 may be equal to −∞, such that p(0) = 0 and

s ∈ S(p) ⇔ there exists τ ≥ τ∗ s.t. s = s(τ ) and p = p(τ ). This implies that

s(0) = 1, lim τ →τ∗

s(τ ) = 0 and lim τ →τ∗

p(τ ) = p∗,

where p∗ is the minimal pressure value. The functions s, p are continuously extended by con-stants on (−∞, τ∗). Now let us define the Kirchhoff transform u : [τ∗, +∞) → R by

u(τ ) = Z τ

0

(12)

For technical reasons the function u is artificially extended into a continuous surjective function from R to R by setting

u(τ ) = τ − τ∗+ u∗ ∀τ < τ∗, (1.10) where u∗ = limτ &τ∗u(τ ) (finite), without influencing the result. We assume that the

parametriza-tion is not degenerated, this means that

s0(τ ) + p0(τ ) > 0 for almost every τ ≥ τ∗ or

s0(τ ) + u0(τ ) > 0 for almost every τ ∈ R

since λ(s(τ )) > 0 for all τ > τ∗. We can deduce from (1.9) and (1.10) that u0 > 0 almost everywhere in R and, because of this, the function ˜S = s ◦ u−1 is indeed well defined. It is important to highlight that the definition of ˜S is invariant with respect to the choice of parametrization of the graph s. Moreover, notice that a parametrization of the graph S always exists but it is not unique. A convenient parametrization should satisfy the following: there exist α∗ > 0 and α∗ ≥ α∗ such that

α∗≤ max(s0(τ ), u0(τ )) ≤ α∗.

We will understand the importance of this property when in Section 2.4. Let us choose τ as the primary variable, so Equation (1.1) now writes

∂ts(τ ) − ∇ · (λ(s(τ ))(∇p(τ ) − g)) = 0 in Q, and it turns to

∂ts(τ ) + ∇ · (λ(s(τ ))g − ∇u(τ )) = 0 in Q, (1.11) for τ ≥ τ∗. Now we impose the boundary condition

τ |∂Ω×(0,T )= p−1(pD) =: τD ≥ τ∗, (1.12)

and the initial condition

τ0 = s−1(s0).

To summarize, the problem now comes under the following form:      ∂ts(τ ) + ∇ · (λ(s(τ ))g − ∇u(τ )) = 0 in Q τ |t=0= τ0 τ |_{∂Ω×(0,T )}= τD, (1.13)

for which, existence and uniqueness of the solution of this scheme have been proven in [3]. Essentially, this parametrization has two drawbacks:

• We are considering the generalized pressure but, actally, it is not always easy to evaluate its analytical expression. It depends on the choosen physical model: if we consider the Brooks and Corey model [4], which reads

   λ(s) = s 2+3λ λ ef f pc(s) = pes −1 λ ef f with sef f = s − srw 1 − srn− srw ,

(peis the air-entry pressure and λ a parameter related to the pore-size distrubution)it can be easily computed. On the contrary, using Van Genuchten model [16],which reads

   λ(s) = s 1 2 ef f[1 − (1 − s 1 mg ef f ) mg_]2 pc(s) = pg[s − 1 mg ef f − 1]1/ng with sef f = s − srw 1 − srn− srw ,

(13)

(where pg is a pressure scaling parameter and mg,ng are parameters related to the pore size distribution) we are not able to find its analytical expression. This detail makes problematic the numerical implementation of the model proposed in [3].

• It does not take into account the fact that, in some physical model as the Van Genuchten one (see Figure 1.2), also the mobility function present problematic derivatives. It implies that we need to divide our domain in three regions and formulate a continuous differential parametrization with two switch of variable to manage the nonlinearities.

0 0.2 0.4 0.6 0.8 saturation -5 -4 -3 -2 -1 0 capillary pressure 1011 0 0.2 0.4 0.6 0.8 1 saturation 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 mobility function

Figure 1.2: Graphic of behaviour of the capillary pressure, on the left, and the mobility function, on the right, using Van Genuchten model.

1.3 An alternative parametrization

We have already pointed out that the viable parametrization is not unique and, depending of the properties we want it to satisfy, we can find different formulations. Now, let us present the different parametrization we have developed.

Consider the relation between u and s given by

u = sβ with β > 1. (1.14)

We look for a parametrization ensuring that |s0(τ )| and |u0(τ )| are bounded. When we introduced earlier the switch of variable for the resolution of the problem, we used the saturation variable in unsaturated zones as primary variable and the Kirchhoff transform elsewhere. Now we relax those requirements and we look for a parametrization that satisfies the conditions

• for τ → 0+ _{: s(τ ) ∼ τ and u(τ ) ∼ τ}β_, • for τ → +∞: s(τ ) ∼ τβ1 _{and u(τ ) ∼ τ}

The idea to “interpolate“ between these extreme behaviours in a continuous way. To achieve this purpose, we take inspiration from various classical mechanical problems, such as the two-body problem, where the reduced mass is obtained by evaluating the product of the mass over their sum, or the black-body radiation where a similar trick was applied by Plank to fit experimental data. Following this idea we propose the following parametrization:

u(τ ) = τ β_τ

τβ_{+ τ} =⇒ u(τ ) = τβ 1 + τβ−1,

(14)

from which we deduce that:

s(τ ) = τ (1 + τβ−1₎β1

.

Let us show that this formulation satisfy the required properties.

Proposition. Let u(τ ) : [0, +∞) → [0, 1], u(τ ) = _1+ττββ−1 and s(τ ) : [0, +∞) → [0, 1], s(τ ) =

τ (1+τβ−1₎β1

with β > 1, then the following properties are satisfied: • for τ → 0+ _{: s(τ ) ∼ τ and u(τ ) ∼ τ}β_,

• τ → +∞: s(τ ) ∼ τβ1 _{and u(τ ) ∼ τ ,}

• s(τ ), u(τ ) ∈ C1_{([0, +∞)),} • |s0(τ )| and |u0(τ )| are bounded.

Proof. Let us start proving the properties for u(τ ). Let τ → 0+_{, we have that 1 + τ}β−1_{∼ 1 and} so u(τ ) ∼ τβ .

Then let τ → +∞, we have that 1 + τβ−1∼ τβ−1_{, so u(τ ) ∼} τβ

1+τβ = τ .

Now we prove the continuity. We can rewrite u(τ ) as u(τ ) = f (τ )_{g(τ )} where f (τ ) = τβ and g(τ ) = 1 + τβ−1. We have that f, g ∈ C1(0, +∞) (precisely they are C∞(0, +∞)) and g(τ ) 6= 0 ∀ τ ∈ [0, +∞). So u(τ ) = f (τ )_{g(τ )} ∈ C1_{([0, +∞)). Being u(τ ) non-decreasing, if we show that,} for τ → 0 and for τ → +∞, u0(τ ) is finite, than we can conclude that |u0(τ )| is bounded. Having

u0(τ ) = βτβ−1(1 + τβ−1)−1− (β − 1)τβ(1 + τβ−1)τβ−2 we evaluate the limits

lim τ →0u 0 (τ ) = 0 lim τ →+∞u 0 (τ ) = 1. We can conclude that the derivative of u is bounded.

Now we pass to s(τ ). Let τ → 0+, we have that 1 + τβ−1∼ 1, so we have s(τ ) ∼ τ . Then let τ → +∞, we have that 1 + τβ−1 ∼ τβ−1_{, so we have s(τ ) =} τβ

1+τβ−1 _β1 ∼ τβ τβ−1 1_β

= τβ1_{. The proof for the continuity is analogue to the one performed for u(τ ), as well}

as for the proof of the boundedness of the derivative. Namely we obtain lim τ →0s 0 (τ ) = 1 lim τ →+∞s 0 (τ ) = 0 and so |s0(τ )| is bounded.

Physically the saturation is a quantity such that s ∈ [0, 1] so, when performing the simu-lations, after having solved the problem in τ -variable, we will take:

s(τ ) = min ( τ (1 + τβ−1₎β1 , 1 )

The advantage of this parametrization is that we do not have to look for the value of τs and the formulation is simpler than the one presented before. The evident drawback is that it is not able to manage the case in which the saturation is a graph. In the chapter dedicated to numerical simulations we will test its optimality.

(15)

Chapter 2

The Finite Volume scheme

For the space discretization of the equations, we have implemented a classical Two-Point Finite Volume scheme, which will be described in the present chapter.

2.1 Discretization of the domain

Let us define an admissible mesh of Ω (which is supposed to be polyhedral for meshing purpose, in order to simplify matter). An admissible mesh (T , E ) of Ω is given by a set T of disjointed open bounded convex subsets of Ω called control volumes, and a family E of subsets of Ω called edges contained in the hyperplanes of Rdwith strictly positive measure. Moreover, each control volume K ∈ T has center xK and

[

K∈T

K = Ω holds.

The boundary of a control volume is made up of edges: for each K ∈ T there exists a subset EK of E , where ∪K∈TEk= E , such that

∂K = [

σ∈EK

σ.

Let us make the distinction between inner edges and boundary ones. For any (K, L) ∈ T2 with K 6= L, either the (d − 1)-dimensional Lebesgue measure of K ∩ L is 0, or K ∩ L = σ for some σ ∈ E . In the last case we can say that σ = K|L and we denote by Eint = {σ ∈ E, ∃(K, L) ∈ T2 _{σ = K|L} the set of inner edges and by E}

ext= {σ ∈ E , σ ⊂ ∂Ω} the boundary edges.

Finally the family of cell centers (xK)K∈T is such that, if σ = K|L it is assumed that the straight line (xK, xL) is orthogonal to σ. This is an important property that we will use afterwards. Moreover for all σ ∈ Eext, there exists one unique cell K such that σ ∈ EK. Then we denote xσ the projection of xK over the hyperplane containing σ and xσ ∈ σ.

2.2 Space and time discretization

First let us introduce the space of degrees of freedom (including those at the boundary): XT = {v = (vK)K∈T} ' R]T,

where ' denotes the fact that the two spaces are linearly isomorphic one to the other. Now we will introduce a space-time discretization for our problem.

(16)

CHAPTER 2. THE FINITE VOLUME SCHEME 13

Figure 2.1: Example of admissible mesh and detail of two cells K, L sharing a face σ ∈ Eint.

Definition 1. A time discretization of (0, T ) is given by an integer value N and a sequence of real values 0 = t0 _{< t}1 _{< ... < t}N _{= T . For all n ∈ {1, . . . , N } the time step is defined by} ∆tn= tn− tn−1_.

Definition 2. A space-time discretization D of Q is a family D = T , E, (tn)n∈{0,...,N }

where (T , E ) is an admissible mesh of Ω, as defined in the previous section, and N, (tn)n∈{0,...,N } is a discretization of (0, T ).

The spaces of degrees of freedom are

XD= {v = (vKn)K∈T ,1≤n≤N} ' R]T ×N. Let v = (vn

K)K,n ∈ XD and we denote vn= (vnK)K ∈ XT for n ∈ {1, . . . , N }.

2.3 Implicit Finite Volume scheme

The numerical scheme we are going to apply in our work is a Finite Volume scheme approxi-mating the diffusive fluxes with the so-called Two-Points flux approximation(TPFA for short). We can use this approximation if the diffusion tensor is diagonal and if the mesh satisfies the orthogonality condition:

Definition 3. The mesh M satisfies the orthogonality condition if each control volume K ∈ M is assumed to contain a point xK such that, for each pair of neighboring control volumes K, L ∈ M, the line (xK, xL) is orthogonal to the common interface K|L.

Let us consider u ∈ XT. The finite volume method consist in first writing, using Stokes’ theore,: − Z K ∇ · (∇u)dx = Z ∂K −∇u · n_K,∂Kdσ = − X σ∈EK Z σ ∇u · n_K,σdσ Now we specify the approximation FK,σ of the flux −

R

σ∇u · nK,σds. The TP numerical flux FK,σ is defined by FK,σ = ( mσuK_d−u_σ L if σ = K|L ∈ Eint, mσ uK−uK,σ dK,σ if σ ∈ EK∩ Etext, (2.1)

where mσ is the (d − 1)-Lebesgue measure of the edge σ ∈ E , dK,σ = d(xK, xσ) and dσ = d(xK, xL), finally uK,σ correspond to the boundary value of u on σ when σ ∈ Eext. The

(17)

numerical flux is then consistent under orthogonality assumption on the mesh in the sense that, for any regular function φ ∈ C∞(Ω), we have

Z σ ∇φ · n_K,σdσ + FK,σ ≤ |σ|C_φh

for all K ∈ T , Cφ ∈ R+ depends on φ and h = max{diam(K), K ∈ T }. From Equation (2.1), the following local conservation property holds, when σ = K|L:

FK,σ+ FL,σ = 0

Again from Equation (2.1), we define the transmissibilities (Aσ)_σ∈E by

Aσ = (_m σ dσ if σ = K|L ∈ Eint, mσ dK,σ if σ ∈ E ∩ Eext. (2.2)

Now, we are able to discretize our problem (1.3). The initial data s0 is discretized by s0 = s0_K_K∈T ∈ XT ,int by setting s0_K = 1 mK Z K s0(x)dx, ∀K ∈ T . We can notice that 0 ≤ s0_K ≤ 1 since 0 ≤ s0 ≤ 1. So we have:

     ∂ts + ∇ · (λ(s)g − ∇u(s)) = 0 in Q s = sD on ∂Ω s|t=0= s0 in Ω. (2.3)

We integrate the first equation over K, discretize the temporal derivative with a first order Finite Difference. Applying the Stokes theorem:

Z K sn_K− sn−1_K ∆tn dx + X σ∈EK Z σ λ(sn_σ)g · nK,σdσ − Z σ ∇u(sn K) · nK,σdσ = 0.

Let us focus on the convective termR_σλ(sn_σ)g · nK,σdσ. We discretize this term using an upwind discretization:

• if g · n_K,σ ≥ 0 : this means that we see an outward flux. Hence we recover information by staying on cell K.

• if g · n_K,σ < 0 : this means that we see an inward flux. So we recover information by staying on cell L or, if σ ∈ Eext we stay on the face itself.

We can rewrite it in an easy way, denoting gK,σ= g · nK,σ, as X σ∈EK Z σ λ(sn_σ)g · nK,σdσ = X σ∈EK mσ λ(sn_K)g_K,σ+ − λ(sn K,σ)g−K,σ where gK,σ= g+K,σ− g − K,σ and g + K,σ= max(0, gK,σ), g−K,σ= − min(0, gK,σ). Finally, we end up with

sn_K− sn−1_K ∆tn mK+

X

σ∈EK

(18)

where mK is the d−dimensional Lebesgue measure of the control volume K ∈ T , FK,σn denotes the outward flux with respect to K across the edge σ at time step tn_{. Let us denote n}

K,σ the outward normal to σ w.r.t. K, gK,σ= g · nK,σ for all σ ∈ EK and all K ∈ T . Moreover,

sn_K,σ= (

sn_L if σ = K|L ∈ Eint sn_D if σ ∈ EK,ext. Then the fluxes F_K,σn are defined by

F_K,σn = mσ

λ(sn_K)g+_K,σ− λ(sn_K,σ)g_K,σ−

+ Aσ(unK− unK,σ). (2.5) Summarizing our system, made up by Equation (2.4) and Equation (2.5), reads

sn_K− sn−1_K ∆tn mK+ X σ∈EK F_K,σn = 0, (2.6) F_K,σn = mσ λ(sn_K)g_K,σ+ − λ(sn_K,σ)g_K,σ− + Aσ unK− unK,σ , (2.7) for all K ∈ T . We can rewrite this formulation in a different way noticing that, since g is divergence free, we have

X σ∈EK mσgK,σ = 0 ∀K ∈ T Hence, if we add −P σ∈EKmσgK,σλ(s n

K) to (2.5) and we exploit the decomposition gK,σ = g+_K,σ− g_K,σ− , the convective flux balance can be reformulated as

X σ∈EK F_K,σn = X σ∈EK mσg_K,σ− λ(snK) − λ(snK,σ) + X σ∈EK Aσ unK− unK,σ ∀K ∈ T

Let us now insert the parametrization into the above equations, so that our problem becomes (1.13). Its discretization reads

s(τ_Kn) − s(τ_Kn−1) ∆tn mK+ X σ∈EK F_K,σn = 0 (2.8) F_K,σn = mσ λ(s(τ_Kn))g+_K,σ− λ(s(τ_K,σn ))g_K,σ− + Aσ u(τKn) − u(τK,σn ) for all K ∈ T .

2.4 Solution of the non-linear problem by Newton method and

variable parametrization

The numerical scheme given by Equation (2.8), for all n ∈ {1, . . . , N }, leads us to the non-linear system

Fn(τn) = (fKn(τn))K∈T = 0 with Fn∈ C2(R]T; R]T) (2.9) where for all K ∈ T :

f_Kn(τn) = mK s(τ_Kn) − s(τ_Kn−1) ∆tn + X σ∈EK mσgK,σ+ λ(s(τKn)) − mσgK,σ− λ(s(τK,σn )) + Aσ u(τKn) − u(τK,σn ) . (2.10)

(19)

Solving (2.9) with the Newton method consists in constructing a sequence τn,k

k≥0 defined by ( τn,0 = τn−1 τn,k+1 = τn,k− JFn(τ n,k₎−1 Fn(τn,k) (2.11) where JFn is the Jacobian matrix of Fn at τ

n_{, assumed to be not singular. The stopping} criterion used is residual-based/

Stop iterative loop (2.11) if kFn(τn,k)k1 ≤ ∆t. (2.12) Coming back to the details of the system (2.11), the Jacobian matrix is a ]T × ]T matrix obtained computing the partial derivative with respect to τnof (2.9), i.e.,

JFn = ∂Fn(τn,k) ∂τn,k = ∂fn K(τn,k) ∂τ_Ln,k ! K∈T ,L∈T (2.13) Starting from equation (2.10) we can give a more detailed expression of (JFn)K

(JFn)K = mK ∆tn ∂s(τ_Kn,k) ∂τ_Kn,k + X σ∈EK Aσ ∂u(τ_Kn,k) ∂τ_Kn,k − ∂u(τ_K,σn,k) ∂τ_Kn,k !! + X σ∈EK mσ g_K,σ+ ∂λ(s(τ_Kn,k)) ∂s(τ_Kn,k) ∂s(τ_Kn,k) ∂τ_Kn,k − g − K,σ ∂λ(s(τ_K,σn,k)) ∂s(τ_K,σn,k) ∂s(τ_K,σn,k) ∂τ_K,σn,k !! . Therefore, [JFn]K,K = mK ∆tn ∂s(τ_Kn,k) ∂τ_Kn,k + X σ∈EK Aσ ∂u(τ_Kn,k) ∂τ_Kn,k + mσg + K,σ ∂λ(s(τ_Kn,k)) ∂s(τ_Kn,k) ∂s(τ_Kn,k) ∂τ_Kn,k ! [JFn]K,L= − Aσ ∂u(τ_Ln,k) ∂τ_Ln,k + mσg − K,σ ∂λ(s(τ_Ln,k)) ∂s(τ_Ln,k) ∂s(τ_Ln,k) ∂τ_Ln,k ! . Now, let us report a very important result from [3]:

Proposition. If τ 7→ s(τ ) and τ 7→ u(τ ) satisfy

0 < α∗≤ s0(τ ) + u0(τ ) ≤ α∗< ∞, then kJ(τ )k1 ≤ L and [J(τ )]−1 1 ≤ C, where • L > 0 depends on α∗, T , ∆t, λ and g, • C > 0 depends on α∗, α∗, T and ∆t.

Thanks to this Proposition, we can notice that Equation (2.12) provides the following error estimate

kτn− τnk1 ≤ ˜C∆t,

which also implies a similar estimate for ks(τn) − s(τn)k1 and ku(τn) − u(τn)k1.

Applying the parametrization, Newton’s method works on the variable τ and then, out of the iterative loop, the saturation and the generalized pressure are evaluated. This implies also that the derivatives in the Jacobian matrix are taken with respect to τ . On the contrary, without parametrization Newton’s method works directly on saturation or generalized pressure variables and the derivatives are computed with respect to them. Finally we can easily notice that Newton’s method is independent from the switch because it handles only τ .

(20)

Chapter 3

Numerical validation of the approach

Our two-dimensional test problem for the method presented in the previous sections is the following. We want to find s = s(x, y, t) defined over

Ω = (0, 1) × (0, 1), t ∈ [0.0, 0.7], as solution of the problem

           ∂ts + ∇ · (λ(s)g − ∇u(s)) = 0 in Ω, u = uD on ΓD, (−∇u(s) + λ(s)g) · n = 0 on ∂Ω\ΓD, s|t=0= s0 in Ω,

where we have set

mobility function: λ(s) = s3,

saturation function: S(u) = min˜ 1, u − u∗ ub

_β1!

, ∀ u ≥ u∗,

and β ≥ 1, u∗ < 0 and ub≤ −u∗ are some parameters. In Figure 3.1 we can see the behaviour of u(s). Thinking in terms of switch, we can easily realize that we want to work in s-variable in the initial plateau and then pass to u-variable. In this way we prevent the presence of large values for the derivatives.

3.1 Test for parametrization of the graph s = S(p)

Let us introduce the parametrization obtained by the equation max(s0(τ ), u0(τ )) = 1 and the condition u(0) = 0, following the theory presented in 1.2, which reads

ˆ u(τ ) = ( ubτβ+ u∗ if τ ∈ [0, τs] τ + τ∗ if τ ≥ τs, ˆ s(τ ) = ( τ if τ ∈ [0, τs] ˜ S(τ + τ∗) if τ ≥ τs,

where the τ -switch is τs= min 1 ubβ 1 β−1 , 1 and τ∗ = ubτsβ+ u∗− τs = us− τs. Indeed, us is the value for which we have s0 = ˜S0(us) = 1 and we obtain the value τs evaluating ˜S(us).

(21)

CHAPTER 3. NUMERICAL VALIDATION OF THE APPROACH 18 0 0.2 0.4 0.6 0.8 1 1.2

saturation

-2 -1 0 1 2 3 4 5

Kirchhoff transform

Figure 3.1: Plot of u(s)

So we can write the τ -formulation as

u(τ ) = ˆu(τ − τ∗) and s(τ ) = ˆs(τ − τ∗).

Using this formulation, while τ ∈ [τ∗, τs+ τ∗] we work in saturation variable, when τ ≥ τs+ τ∗ we pass to Kirchhoff variable. In our simulations we will also consider the limit case β = +∞, corresponding to the case where ˜S is a graph, that is

˜ S(u) =

(

[0, 1] if u = u∗, 1 if u > u∗. The parametrization in this case reads

u(τ ) = ( u∗ if τ ∈ [u∗− 1, u∗] τ if τ ≥ u∗, s(τ ) = ( τ − u∗+ 1 if τ ∈ [u∗− 1, u∗] 1 if τ ≥ u∗.

Actually we have tried to perform the simulation in s-variable to show the efficiency of the parametrization, but in this case where the Newton method does not converge, we are not able to show its result. The lack of convergence is related to the fact that, already from the first Newton’s iteration for the first time step, the cells on the Dirichlet boundary have saturation bigger than one. These values, beyond the fact that they are not physically acceptable, carry the method to the non-convergence. We have tried to use a one-step SOR method in order to fix the problem but it is not sufficient. Another possibility should be to test a time adaptation in order to “help” Newton at first times step reducing the time step.

We consider a bi-dimensional porous domain Ω which is initially very dry, namely we consider s0(x) = 10−6 in Ω. The water is injected with pressure uD = 0 through a portion of the upper boundary

(22)

CHAPTER 3. NUMERICAL VALIDATION OF THE APPROACH 19

and on Ω\ΓD a zero flux boundary is prescribed. The gravity vector is given by g = −∇x2. The final time is set to T = 0.7 and the time step is ∆t = 10−4. Finally we set ub = 10−1 and u∗ = −1.

Here we report the plot of the simulations obtained with β ∈ (4, 8, 16, 32, +∞) using τ -formulation in Figures 3.2, 3.3, 3.4, 3.5, 3.6, respectively. We can observe that as β increases, the saturation has a more and more abrupt profile.

Now for each value of β we compute, using τ -formulation and a tolerance ref = 10−12, the reference solution denoted by

τ_βn

n∈1,...,N ∈ XD. Then we perform the calculations measuring the maximum and average number of Newton iterations and the deviation of the variable s from the reference solution, for τ -formulation, for each value of β using

∈10−2_{, 10}−4_{, 10}−6_{, 10}−8_{, 10}−10_{, 10}−12_.

For a given β and tolerance , we denote by (τ_β,n )n∈(1,...,N ) ∈ XD the approximate solution of (2.9) obtained using τ -formulation. We measure the relative error

err_β,s = s(τ n β,) − s(τβn) _L∞_{(0,T ;L}1_(Ω)) s(τ n β) L∞_{(0,T ;L}1_(Ω))

The computations are performed on two quasi-uniform space discretizations of Ω composed by 870. Figure 3.7 shows, for both meshes, the behaviour of err_β,s , as the function of the average and maximum number of Newton iterations per time step required by method in order to converge up to the given tolerance . Moreover, in Figure 3.8, the evolution of the residual norm with respect to the number of iterations of a Newton’s cycle for β = 32 (the most challenging case, indeed) is reported. Performing a convergence analysis, we obtain a rate equal to two for the Newton’s method. Indeed we can easily notice that the residual norm decreases quickly with respect to the iteration number.

(23)

Figure 3.2: Saturation and generalized pressure profile, respectively on left and right column, for β = 4 and t ∈ {0.0, 0.1, 0.5, 0.7} using τ -formulation.

(24)

(25)

(26)

(27)

Figure 3.6: Saturation and generalized pressure profile, respectively on left and right column, for β = +∞ and t ∈ {0.0, 0.1, 0.5, 0.7} using τ -formulation.

(28)

CHAPTER 3. NUMERICAL VALIDATION OF THE APPROACH 25 14 15 16 17 18 19 −12 −10 −8 −6 −4

Number of maximum iterations

log 10 (err) β = 4 β = 8 β = 16 β = 32 β = ∞ 5 6 7 8 9 −12 −10 −8 −6 −4

Average number of iterations

log 10 (err) β = 4 β = 8 β = 16 β = 32 β = ∞

Figure 3.7: Behavior of the error with respect to the maximum and the average number of Newton iterations. 1 2 3 4 5 6 7 0 1 2 3 4 5 ·10−2 Iterations Fn (τ k +1 ,n ) 1 β = 32

(29)

3.2 Test for the proposed parametrization

Let us now, starting from the same test case, perform a numerical validation of the parametriza-tion we have proposed in Secparametriza-tion 1.3. From now we will denote ˜u = u−u∗

ub . Considering the

equation of ˜S(u), we have that u = sβ and so we can formulate the parametrizatio: ˜ u(τ ) = τ β 1 + τβ−1, s(τ ) = min τ (1 + τβ−1₎β, 1 .

We consider a two-dimensional porous domain Ω which, again, is initially very dry, having s0(x) = 10−6 in Ω. The water is injected with pressure uD = 0 through a portion of the upper boundary

ΓD = {(x1, x2) | x1 ∈ (0, 0.3), x2= 1},

and on Ω\ΓD a zero flux boundary is prescribed. The gravity vector is given by g = −∇x2. The final time is set to T = 0.7 and the time step is ∆t = 10−4. Finally we set ub = 10−1 and u∗ = −1.

In Figure 3.9 we report the plot of the simulations obtained with β = 4, using the previously shown parametrization.

We can observe that we obtain the same result of the test performed in Section 3.1. For β = 8, 16, 32, the Newton’s method encounters some difficulties and it actually does not converge. Looking for recovering convergence, we implement a one-step SOR-Newton method as done in [5]. In this way, in the Newton solver, we compute

˜

xk+1,n = θxk+1,n+ (1 − θ)xk,n,

the convex combination with coefficient θ ∈ [0, 1] of the solutions at two consecutive iterations. Now, we report the results obtained picking β ∈ {4, 8, 16, 32} using the relaxation parameter θ = 0.4 in Figure 3.10, 3.11, 3.12, 3.13, respectively. This coefficient has been choosen in order to carry convergence for every β, so actually it is not the optimal θ for each value of β. We can notice that, for β = 4 we obtain a result equal to the one evaluated without the relaxation. Considering now the simulations perfomed using relaxation, we can notice the same behavior that we have obtained in Section 3.1.

Then, for each value of β, we compute, using a tolerance ref = 10−12, the reference solution of Equation (2.9) denoted by (τ_βn)n∈1,...,N ∈ XD. Then we perform the calculations measuring average number of Newton iterations and the deviation of the variable s from the reference solution for each value of β using

∈10−2_{, 10}−4_{, 10}−6_{, 10}−8_{, 10}−10 We measure the relative error

err_β,s = s(τ n β,) − s(τβn) L∞_{(0,T ;L}1_(Ω)) s(τ n β) L∞_{(0,T ;L}1_(Ω))

The computations are performed on two quasi-uniform space discretizations of Ω composed by 870 cells. Figure 3.14 shows, for both mesh, the behaviour of errs_β,, as the function of the average number of Newton iterations per time step required by method in order to converge up to the given tolerance .

We can clearly notice that the error has almost the same behavior for all values of β. The evident difference of these results with respect to the ones obtained in Section 3.1 is that here we can observe a linear behavior of the error with respect to the average number of the iterations.

(30)

Figure 3.9: Saturation and generalized pressure profile, respectively on left and right column, for β = 4 and t ∈ {0.0, 0.1, 0.5, 0.7}.

(31)

Figure 3.10: Saturation and generalized pressure profile, respectively on left and right column, for β = 4 and t ∈ {0.0, 0.1, 0.5, 0.7} and θ = 0.4.

(32)

(33)

(34)

(35)

CHAPTER 3. NUMERICAL VALIDATION OF THE APPROACH 32 10 20 30 40 50 −10 −8 −6 −4 −2

Average number of iterations

log 10 (err) β = 4 β = 8 β = 16 β = 32

Figure 3.14: Behavior of the error with respect to the average number of Newton’s iterations.

Hence, we have to conclude that the parametrization we have proposed is not so good in terms of reliability because it needs a relaxation of the Newton method and, moreover, it requires a bigger number of iterations which means a longer computational time. In Figure 3.15 we can see the evolution of the residual norm during Newton’s iterations. At the first iterations it decreases quickily but than it takes a quite large number of iterations to reach convergence.

0 10 20 30 40 50 60 0 2 4 6 8 ·10−3 Iterations Fn (τ k +1 ,n ) 1 β = 32

(36)

Chapter 4

Description of the code and

preliminary validations

4.1 The prototype

Our prototype is basically made up by four components: Mesh, Numerics, Physics and Visual-isation. Let us analyze each of them.

Mesh

Our mesh structure is, potentially, adaptable to also handle a three-dimensional mesh. For the moment, we have only implemented constructors for 1D and 2D mesh but, when we will pass to 3D meshes, the only modification to the code will be the implementation of a specific constructor for the elements to menage this case. Now, let us detail the cases which have been implemented.

2D mesh

For the mesh generation, we use a Finite Elements mesh generator. Knowing that we use a Finite Volume scheme, we have created this support in order to store all the components of the mesh in an object and also evaluate some quantities of interest such as the volume of the cells, the center of the cells and so on. In Figure 4.1 we can see the structure of our code.

• The class Dof is a very simple class owning an integer which is the identifier characterizing an element of the mesh. This class has been created just to have other classes inheriting from it. For this reason the attribute m id is defined as protected. Let us analize the other classes. The class Node owns the attribute m point which is a vector of double of size 3 × 1 containing the coordinates of the node. Concerning the methods, this class has a getter method to return each coordinate of the node and an operator== in order to compare two node elements.

(37)

CHAPTER 4. DESCRIPTION OF THE CODE AND PRELIMINARY VALIDATIONS 34

(38)

• The class Cell describes our mesh components: the triangles. It is characterized by its center, its volume and the vector of the ids of the nodes which are the vertices of a triangle. Finally, we have a getter to return the center, the volume the number of nodes characterizing the cell and their ids, and an operator== to compare two cells.

• The class Face describes a line that is one edge of a cell. It is characterized by its center, its area, the normal vector, a boolean flag with value ”true” if it is a boundary face or ”false ”otherwise and, finally, the pointers to the cells sharing this face.

Clearly, if σ ∈ Eint we have that σ = K|L so it is shared by two cells called Cell0 and Cell1. Otherwise, if σ ∈ Eext, the face will be owned only by Cell0. In Figure 4.2 we have represented the two cases. The normal of the face is oriented, for σ ∈ K|L, from Cell0 (K) to Cell1 (L) and for σ ∈ Eextfrom Cell0 to the outside. For each of these parameters we have a getter method.

Figure 4.2: On the left we see the case σ = K|L, on the right the case σ ∈ Eext

• The class Mesh contains, stored in vectors, all the elements which form the mesh. The constructor of this class takes the name of the file .msh of our mesh and, reading it, stores all the needed information. Let us explain how, starting from a Gmsh file, we create an object Mesh.

Thanks to the fact that we know the structure of a .msh file, we read from the file and manipulate the data in order to store all we need to generate our mesh. In Figure 4.3 we can see and example of .msh file. We divide the reading procedure in seven intermediate steps:

1. It is the step working with the MeshFormat section, where we find the Gmsh version, the file-type and the data-size. We simply skip it because no information from this section is needed for our purpose.

2. Here, we enter in the section Nodes and we simply read and store the number of nodes we are going to read.

3. In this part, we have to process the node description: in each line we find the identifier of the node and its coordinates. For each node, we store the element in a vector of nodes, ordered with respect to the identifier number which starts from zero (so actually it will be the identifier read minus one). When the number of read nodes is equal to the number of nodes, we enter in the next part.

4. Here we enter in the section Elements where we will read data concerning the cells. Here we find elements of different types: type 1 is a line, type 2 is a triangle, type 4 is a quadrangle, type 15 is a point. In our work, we are only interested in type 2: triangles. Here we just read the total number of elements of different types.

5. Now, we skip all the elements which are not triangles, when we find the first one we pass to the next part calculating how many type 2 elements we have.

(39)

CHAPTER 4. DESCRIPTION OF THE CODE AND PRELIMINARY VALIDATIONS 36 $MeshFormat 2.2 0 8 $EndMeshFormat $Nodes 4 1 0 0 0 2 1 0 0 3 1.5 0.866025405 0 4 0.5 0.866025405 0 $EndNodes $Elements 10 1 15 2 0 1 1 2 15 2 0 2 2 3 15 2 0 3 3 4 15 2 0 4 4 5 1 2 0 1 1 2 6 1 2 0 2 2 3 7 1 2 0 3 3 4 8 1 2 0 4 1 4 9 2 2 0 6 2 4 1 10 2 2 0 6 2 3 4 $EndElements

Figure 4.3: Example of .msh file

6. For each line, we create a cell element starting from the id-nodes which characterizes it and its identifier number(which starts from zero) and we store it in a vector of cells. What we also create here is a set whose elements are pairs of identifier numbers characterizing a face. In this way, for each face, we will know which nodes compose it.

7. We skip the rest of the file.

After these parts we compute the orientation of the normal vectors, we assign the boundary flags and the pointer to Cell0 and Cell1 for each face.

1D mesh

For a one-dimensional mesh, the previous scheme does not change. We have created a Face, Cell and Mesh constructor to manage this case:

• Face constructor takes one node and the identifier number • Cell constructor takes two nodes and the identifier number

• Mesh constructor takes the starting point, the space step ∆x, the number of cells N we want to create and the height of our domain.

(40)

Numerics

In this folder, we can find the numerical tools we need, namely: the TPFAScheme class, the NonLinearSystem class and the NewtonSolver class. The skeleton of these classes is reported in Figure 4.5. Let us analyze them deeply.

Figure 4.5: Structure of classes contained in Numerics

TPFAScheme

The objective of this class is to calculate the transmissivities of the faces of our mesh. We have defined the transmissivity coefficient Aσ when we have set the flux discretization using the Two-Points Flux approximation scheme and we can find its definition in Equation (2.2). How does it work? We simply pass a reference to the mesh to the constructor which performs a loop on the inner and outer faces and evaluate the transmissivity coefficient for each face. This coefficient is stored in a vector in the position equal to the identifier of its corresponding face. Once the object TPFAScheme has been created, we can ask for the transmissivity coefficient of the i-th face using the getter method giving him the identifier numer i.

NonLinearSystem

NonLinearSystem is an abstract class whose children will describe the nonlinear system to solve. Basically this class is constructed in order to assemble the Jacobian matrix for the system, evaluate the residual vector, get the previous and current solution and the evaluated residual.

Moreover it saves and updates the time at which we are as long as the simulation advances. As we can clearly imagine, all this tools will be used in the Newton loop because we need to solve (2.11). The methods assemble() and updateResidual() are pure virtual functions because their implementation will change according the chosen system to solve. However the structure of these methods will not change: see Algorithm (1) and (2).

Functions increaseDeltaTime() and decreaseDeltaTime() are used at the end of the temporal loop to adapt the time-step ∆t. If the Newton method converges, we increase ∆t, otherwise we decrease it without updating the time of the simulation and we recall NewtonSolver using the previous solution for the loop.

(41)

Data: assemble()

We initialize the Jacobian matrix to the full-zero matrix;

We create a vector of triplets of double that we will use to create our sparse matrix; Each element of this vector takes the indices of the position of the matrix where we want

to store the value, and the value;

for each cell in the vector of cells of the mesh do

we push back the prescribed value at position (cell-id,cell-id); end

for each face in the vector of inner faces do

we push back the prescribed values of diffusion and convection in diagonal and off-diagonal position;

end

for each face in the vector of outer faces do

we push back the prescribed values of diffusion and convection in diagonal position; end

we create the matrix: m jacobian.setFromTriplets(tripletList.begin(), tripletList.end()) ; Algorithm 1: Algorithm for assembling Jacobian matrix.

Data: updateResidual() We initialize the vector to zero;

for each cell in the vector of cells of the mesh do m residual[id] += prescribed value;

end

for each face in the vector of inner faces do

we add the prescribed values of diffusion and convection; m residual[idCell0] += diffusionValue ;

m residual[idCell1] -= diffusionValue ; m residual[idCell0] ±= convectionValue ; m residual[idCell1] ∓= convtionValue ; end

for each face in the vector of outer faces do

we add the prescribed values of diffusion and convection; m residual[idCell0] += diffusionValue ;

m residual[idCell0] += convectionValue ; end

Algorithm 2: Algorithm to update residual vector. NewtonSolver

This class contains the solve method which performs Newton’s iterations. When we create an object of this class, we specify the maximum number of iterations to perform, the tolerance to use for the stopping criterion and a pointer, more precisely a shared pointer, to the NonLinearSystem to solve. Moreover, we also specify which norm we want to use for evaluate the residual norm (we pass 0 for L∞-norm, and 1 for L1-norm) and if we want to perform a Newton relaxation (passing 0 if not, 1 otherwise). Then, to apply the Newton method, we call the function solve(int& nIter). Let us analyze it: first, we can notice that the return type is a boolean. It returns true if the method converges and false otherwise. The reference to the integer passed as argument will be updated at the end of the iterations-loop with the number of iterations done. In the test we will use it to control the number of iterations performed by the Newton solver. We know that, at the very beginning, the previous solution and the current solution are the same and correspond to the initial one. Once entered in the solve method, we update

(42)

the residual vector and we evaluate its l∞-norm. Then, there is the loop to evaluate the new iterative solution. We stay in the the loop until the maximum number of iterations is reached or the norm of the residual vector becomes smaller than the desired tolerance. In the loop, we first assemble the Jacobian matrix and than we use the Stabilized BiConjugate Gradient method provided by the Eigen library to evaluate the increment solving JFn(x

n,k_{) incr = F}

n(xn,k). Then we update the new solution and the residual evaluating their norms. When we exit the loop, if the number of iterations we have performed is smaller than the maximum number of iterations expected, this means that the method is likely to have reached convergence and we return true. Otherwise we return false.

CancesBrooksCoreyParameterizedModel

We can define this class as a decoreator pattern of the object CancesBrooksCoreyModel (see Physics section): it has the same structure from the point of view of public methods but it menages them in a more complex way. When we introduce the parametrization we have to take the switch into accout and we want our Newton solver not to be affected by it. Hence, this is the moment when the utility of the CancesBrooksCoreyParameterizedModel emerges: it uses the laws implemented in the CancesBrooksCoreyModel and menage them with respect the choosen formulation, namely if we want to solve the problem in saturation variable, or in generlized pressure variable or using a parametrization. The formulations available are the following:

• formulation = 0 we solve the problem with respect to the Kirchhoff transform u, • formulation = 1 we solve using the automatic switch (τ ) using the parametrization

proposed by [3],

• formulation = 2 we solve the problem with respect to the saturation s

• formulation = 3 we solve the problem with respect to τ varibale using the alternative parametrization we have proposed.

Concerning the advanced C++ tools we have used, in this class, we make extensive use of lambda functions, in particular:

[captures](parameters) → ret{body} where

• captures : we pass &, simple by-reference capture of the object. Notice that [&] and [&, this] are equivalent.

• parameters: list of the parameters. • ret : is the return type.

(43)

Physics

In this folder, we can find classes corresponding to the physical models we are going to use in our simulations. Basically, for the moment, we are only using the Brooks-Corey model to describe the relation between the capillary pressure, the mobility and the saturation. The skeleton of the two implemented model is reported in Figure 4.6. Each class (hence, each law) has a getter

Figure 4.6: Skeleton of the models BrooksCorey and CancesBrooksCorey stored in Physics.

method: we pass the value at which we want to evaluate the law and the method returns the corresponding result. Let us just focus on the check() method of the class BrooksCoreyModel. The target of this method is to emulate, in the code, this relation:

Denoting sef f = s − srw 1 − srn− srw we have that: s =      srw if s < srw s if srw≤ s ≤ 1 − srn 1 − srn if s > −srn.

In CancesBrooksCoreyModel it is implemented for s (we no longer use sef f) in the getter methods using an if condition:

(44)

Visualisation

Once we have solved our problem, it would be interesting to plot and post-process the obtained solution. The aim of this folder is to provide a way to create a .vtk file which is used by the well-known post-processing software Parawiew. For this reason the class in object is named MakeVTK. The skeleton of this class is reported in Figure 4.7. Since we know the structure of

Figure 4.7: Skeleton of class MakeVTK.

a .vtk file (see Figure 4.8), we use the information we have about the mesh, its elements and the the values of the solution on each cell to write a .vtk file. This is, summing up, what the methods writeVTK and writeVTK1D do. They take the name of the file to write, a vector containing the solution we want to export and their labels, stored in the vector of string passed as last element. In the section POINTS the coordinates of the nodes are listed. Next to the

Figure 4.8: Example of file .vtk

word POINT we find how many numbers we are going to read and their type. Then in the section CELLS the identifier numbers of the nodes characterizing each cell are listed. Next to the word CELLS we find the number of the cells of our mesh and how many numbers we are going to read. Each line starts with the number of the identifiers to read and themselves.Then in the section CELL-TYPE we find, for each cell, the number corresponding to the type of the cell. Type 5 is for triangles and type 3 for lines.

Finally we have the solution values. SCALARS means that each value is a scalar value, then we find the label of the solution, the type of the value and how many values per line we will have. Then we have the list of the solution value associated to each cell. So the difference between the methods writeVTK and writeVTK1D is that the first, being for 2D meshes, will write three identifier numbers for each cell and cell type will be 5.*

The second method will write two identifier numbers for each cell and cell type will be 3. For the plot in time, we simply name the file with a number at the end: “myfile1.vtk”,

A parametrization technique to improve the robustness of Newton's method, with application to Richards' equation