Sixth Mississippi State Conference on Differential Equations and Computational Simulations, Electronic Journal of Differential Equations, Conference 15 (2007), pp. 77–95. ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu ftp ejde.math.txstate.edu (login: ftp)

A FINITE DIFFERENCE SCHEME FOR A DEGENERATED DIFFUSION EQUATION ARISING IN MICROBIAL ECOLOGY

HERMANN J. EBERL, LAURENT DEMARET

Abstract. A finite difference scheme is presented for a density-dependent diffusion equation that arises in the mathematical modelling of bacterial biofilms. The peculiarity of the underlying model is that it shows degeneracy as the dependent variable vanishes, as well as a singularity as the dependent variable approaches its a priori known upper bound. The first property leads to a finite speed of interface propagation if the initial data have compact support, while the second one introduces counter-acting super diffusion. This squeezing property of this model leads to steep gradients at the interface. Moving interface problems of this kind are known to be problematic for classical numerical methods and introduce non-physical and non-mathematical solutions. The proposed method is developed to address this observation. The central idea is a non-local (in time) representation of the diffusion operator. It can be shown that the proposed method is free of oscillations at the interface, that the discrete interface satisfies a discrete version of the continuous interface condition and that the effect of interface smearing is quantitatively small.

1. Introduction

1.1. Biological background. The mathematical model in the focus of this study describes the formation and growth of bacterial biofilms. These are communities of migroorganisms that live embedded in a self-produced layer of extracellular polymeric substances (EPS). The EPS offers protection to the bacteria in the biofilm, which develop behavioral patterns that differ from those of planktonic bacteria [3], [11]. As a consequence, harmful biofilm bacteria are more difficult to remove, mechanically or by antimicrobial agents, than suspended bacteria [22], [24]. Biofilms occur naturally on surfaces and interfaces in aquatic systems wherever enough nutrients are available to sustain microbial growth [11]. Harmful occurrences of biofilms include bacterial infections, dental plaque and associated diseases, biocorrosion of drinking water pipes or industrial facilities, and food spoilage. On the other hand, the sorption properties and enhanced mechanical stability of biofilms are beneficially used by environmental engineers, e.g. in wastewater treatment, soil remediation, and groundwater protection [23].

2000 Mathematics Subject Classification. 35K65, 65M06, 92C17. Key words and phrases. Finite differences; nonlinear diffusion; non-local representation; non-standard discretisation; numerical simulation; biofilm. \begin{matrix}c \\ ◯ \end{matrix}2007 Texas State University - San Marcos. Published February 28, 2007.

While the term biofilm indicates a homogeneous film-like layer, biofilms on the meso-scale (10μm ∼ 1mm, the actual biofilm scale) in reality can develop in structurally highly complicated architectures. The morphology of a biofilm is triggered by environmental conditions, such as the availability of required substrates like nutrients and, in the case of aerobic biofilms, oxygen [15], [16], [23], [26]. Well-known are the so-called mushroom or pillar shaped biofilm morphologies. These are clusters of biofilm colonies, trenched by water-filled pores and channels, cf. the confocal laser scanning micrograph in Figure 1 and the schematic in Figure 2. Biofilm morphologies of this type are observed in nutrient limited regimes. Initially, at low population density, the bacterial population develops unhindered. As the population grows, demand of food increases and inner-species competition for food sets in when nutrients become depleted. Large colonies have an advantage allowing them to grow faster towards the nutrient source and thus out-compete smaller colonies that stay behind in their development. As these biofilms grow under nutrient limitation they typically develop slowly. On the other hand, biofilms developing in a nutrient rich, un-limited environment tend to grow quickly and form homogeneous, compact, flat yet thick structures. In order to capture these features, spatially resolving techniques are required for biofilm research. In addition to modern noninvasive microscopy methods in experimental studies, mathematical models and computer simulations for theoretical studies become more and more accepted [23], [25].

Figure 1. Microscopy snapshot of a very young spatially heterogeneous biofilm of Listeria monocytogenes and Pseudomonas putida developing in a cluster-and-channel morphology. The CLSM figure was made available by Heidi Schraft, Lakehead University, Thunder Bay, On, Canada. The original colors were modified for better greyscale printing.

1.2. Mathematical models and numerical simulation. Traditional biofilm models were formulated as one-dimensional free-boundary value problems, based on the assumption that newly produced biomass is converted into new biofilm volume. This leads to an increasing thickness of the biofilm and the speed of propagation of the biofilm/liquid interface normal to the substratum can be calculated from the production terms by integration over the biofilm thickness [23]. As this concept is inherently one-dimensional, it cannot predict spatially heterogeneous biofilm morphologies. To fill this gap, a variety of models for spatially heterogeneous biofilms has been proposed in recent years, ranging from stochastic individual based models to cellular automata models to deterministic continuum models [20]. The underlying mathematical principles of these models are quite different and, therefore, the mathematical and computational challenges vary from model to model. Nevertheless, they all show the same qualitative behavior in predicting the development of biofilm morphologies in response to substrate limitation, cf. [20] and the references therein for a selection and overview.

The model for biofilm formation that we consider was introduced originally in [5] and studied in a small series of papers analytically, numerically and in applications [4, 6, 7, 8, 9, 14]. It is a quasi-linear diffusion equation for the dependent variable biomass density u, with two interacting causes of degeneracy. One is degeneracy as in the porous medium equation, i.e. the density dependent diffusion coefficient D(u) vanishes as the dependent variable vanishes, D(0) = 0; the other one is a singularity in the density-dependent diffusion coefficient as the dependent variable approaches its a priori known maximum density, u → 1. In the current study we propose a numerical discretisation scheme that is able to handle these two simultaneously occurring effects and to render important qualitative features of the continuous model. The actual biofilm is the region in which the biomass density is positive. The transition from the surrounding aqueous phase to the biofilm is sharp, that is the biomass gradients are steep at the biofilm/liquid interface. Since the biofilm grows, this interface is not stationary but its location changes over time. The speed and direction of the interface propagation is not a priori known but an implicit consequence of the solution of the equation; furthermore, as two or more biofilm colonies merge into a bigger one the interfaces collide and become dissolved. Interface problems of this type are known to pose difficulties for many numerical methods, often leading to either un-physical and un-mathematical oscillations in the solution or smearing of the sharp interface. The underlying reason is that discretisation schemes often assume more regularity than the initial-boundary value problem offers. This effect can be observed already in very simple examples that possess classical smooth solutions, e.g. the heat equation with a discontinuous interface in the initial data [13].

A variety of numerical methods were used in previous studies of the biofilm model. In [5, 6, 7], based on a time-scale argument, the faster (in terms of characteristic time scales) substrate equations were solved implicitly while the slower biomass equation is solved with explicit schemes, e.g. the adaptive 4th/5th order Runge-Kutta-Fehlberg method, cf[10]. The maximum feasible time-step in this approach depends on the solution of the equation and becomes very small as the biofilm grows and maximum biomass density u → 1 is approached somewhere. A very different idea was followed in [4], where the degenerated equation was transformed into new dependent variables such that the spatial operator becomes the Laplacian and all non-linear effects appear in the time-derivative. A fully implicit method for this equation was devised that has only a very mild time-step constraint. This method handles the diffusion singularity effect very well, but it was found that in some cases it emphasises interface oscillations, i.e. is not able to correctly deal with the porous medium degeneracy. In [14] the model equation was re-formulated in a weak form in the moving frame and subsequently discretised by a moving grid finite element method that explicitly tracks the biofilm/liquid interface, following an idea that was originally developed in [2] for degenerate parabolic equations. This method describes the porous medium degeneracy very well.

It is fully adaptive in time and space (with explicit time integration) and builds its biofilm grid adaptively. However, re-meshing and grid-refinement is required as new biomass is produced and the biofilm structure grows, in order to avoid finite elements becoming too large. This requires interpolation and becomes inefficient in higher dimensions.

In this paper we will present a numerical method for the biofilm model that is based on a non-local (in time) representation of the nonlinear density dependent diffusive biomass flux. This leads to a semi-linear method that inherits the mild time-step constraint of the implicit method in [4] and the advantages of the explicit method. In every time step the solution of only one linear algebraic system is required. In particular the method deals well with the moving interface, preserves the positivity of the solutions and is free of oscillations.

2. The continuous model

Figure 2. The domain Ω ⊂ ℝ^{2} with liquid region Ω_{1}(t) = {x ∈ Ω : u(t, x) = 0} and biofilm region Ω_{2}(t) = {x ∈ Ω : u(t, x) > 0}. As u changes with time, the interface between Ω_{1} and Ω_{2} starts moving.

We consider the biofilm as a continuum and study a density-dependent diffusionreaction equation that describes the development of a spatially structured bacterial biofilm. The model is formulated as an evolution equation over the domain Ω ⊂ R^{d}, d = 1, 2, 3, in terms of the biomass density u, normalised with respect to the maximum biomass density. Under this ansatz, bacteria and EPS are considered together in one fraction. This is the classical approach in biofilm modelling [23].

The region Ω_{1}(t) := {x ∈ Ω : u(t, x) = 0} describes the surrounding aquatic environment (bulk liquid, channels and pores of a biofilm) without biomass, while Ω_{2}(t) = {x ∈ Ω : u(t, x) > 0} is the actual biofilm (cf. Figure 2). The model under consideration was introduced in [5]. In the notation used here it reads

u_{t} = ∇_{x}(D(u) · ∇_{x}u) + ku  (2.1)

where

D(u) = δ \frac{u^{b}}{(1 − u)^{a}} , a, b ≥ 1 ≫ δ > 0  (2.2)

together with Dirichlet, Neumann, or mixed boundary conditions. In (2.1) the quantity k describes the production rate. For our purpose it is sufficient to assume that it is bounded. If k is a positive constant (2.1) corresponds to a biofilm system in which nutrients are not limited. In this case we expect a homogeneous biofilm morphology for large t. In the case of nutrient limitations, k(t, x) is a non-constant function. We shall present simulations for both scenarios below.

Some analytical results about this model can be found in [4], [9]; biofilm applications of this type of equation and its generalisations were discussed in [5], [6], [7]. The long term behavior of the initial-boundary value problem associated with (2.1) was studied in [9]. It was shown that for initial data u_{0} with

u_{0} ∈ L^{∞}(Ω), F (u_{0}) ∈ H_{0}^{1}(Ω), u_{0} ≥ 0, ∥u_{0}∥_{L^{∞}}(Ω) < 1

where

F (u) = ∫_{0}^{u} \frac{v^{α}}{(1 − v)^{β}} dv, 0 ≤ u < 1

there exists a unique solution u of (2.1) in the class of functions

u ∈ L^{∞}(R_{+} × Ω) ∩ C([0, ∞), L^{2}(Ω)))
F (u) ∈ L^{∞}(R_{+}, H^{1}(Ω) ∩ C([0, ∞), L^{2}(Ω))
0 ≤ u(t, x) ≤ 1 ∥u∥_{L^{∞}(R_{+}×Ω)} < 1

If the boundary conditions are homogeneous Neumann conditions everywhere, then the solution u reaches its maximum density 1 almost everywhere in finite time. Physically this corresponds to the situation where the biofilm growths unlimited in a closed vessel from where no biomass can escape. If Dirichlet conditions u = 0 are specified somewhere on the boundary of Ω, then the solution will remain below the maximum density for all t > 0 almost everywhere. Further results include the existence of a global attractor [9] and the construction of a Lyapunov functional [4]. An essential property of the solutions of (2.1) is that initial data with compact support imply solutions with compact support and that the solution is indeed bounded by the maximum biomass density. The first effect is due to the porous medium degeneracy u^{b} in (2.2), while the latter is due to the singularity (1−u)^{−a} in (2.2). It is the production term ku together with this second effect that drives the spatial spreading of Ω_{2}(t). This is counteracted by the degeneracy as u = 0 at the interface. As a consequence, u squeezes in Ω_{2}(t) and, in the absence of loss terms, approaches its maximum value 1. Hence, the interaction of both non-linear diffusion effects with the growth term in (2.1) is needed to describe spatial biomass spreading. It leads to very steep gradients of u at the moving interface between Ω_{1}(t) and Ω_{2}(t). If Ω_{2}(t) is initially not connected but consists of several “sub-domains” (each of which connected), these will eventually join if k is positive and large enough, due to the expansion of each individual sub-domain. In biofilm applications this describes the merging of two initially isolated bacterial colonies. Thus, if two Ω_{1}-Ω_{2} interfaces collide, they are dissolved and the sub-domains become connected.

In [4] a semi-discretisation in time was discussed that aimed at overcoming the obvious numerical difficulties arising when u → 1. After transformation of the dependent variable u ↦ v := F (u), the nonlinearities appear in the time-derivative, while the spatial spreading effect is described by the linear diffusion operator. Backward Euler discretisation leads to an elliptic boundary value problem in every timestep. Convergence results showed that the time-step restriction of this model is not critical, i.e. the maximum time-step size permitted for convergence is larger than the characteristic time-scale of the biofilm formation process, i.e. for given spatial discretisation it behaves like O(1/k). However, it was found that the numerical discretisation of the spatial terms with standard Finite Element or Finite Difference methods introduces oscillations with negative values at the biofilm/liquid interface. Local grid refinement can postpone and dampen this effect but not avoid it. In the current work we aim at a generally applicable numerical scheme for (2.1) and model extensions that is free of this non-physical effect.

3. Numerical Method

3.1. Finite Difference Scheme For The Continuous Problem. We introduce a finite difference scheme for (2.1) on a regular grid based on a first order difference approximation for the time derivative and the usual second order spatial difference for self-adjoint diffusion operators, cf [19].

The key idea of the method is to represent the nonlinear diffusive flux D(u)·∇_{x}u in (2.1) and the reaction term k · u non-local in time: The diffusion coefficient is evaluated in time level t while the gradient is evaluated at the new time level t+Δt, i.e. one has

D(u) · ∇_{x}u ≈ D(u(t, ·)) · ∇_{x}u(t + Δt, ·)

and similarly for the reaction term

k · u ≈ k(t, ·) · u(t + Δt, ·)

Finite difference methods for (ordinary or partial) differential equations utilising such a non-local representation of non-linear terms are called non-standard finite difference schemes [1]. Despite the low order convergence of the chosen derivative approximations, such a discretisation is known to be optimal among linear finite difference schemes for certain problems under the aspect of positivity and monotonicity (cf. [13] for details). In the context of non-standard finite difference schemes this strategy of low order discretisation of derivatives is routinely used for the construction of discretisation schemes and referred to as Rule 1 in [17].

In the sequel, we denote by u_{j}^{n} the numerical approximation of the exact solution u(t^{n}, x_{j}) in the grid points x_{j} ∈ R^{d}. Here j ∈ J can be a multi-index or a grid ordering in the multi-dimensional case d > 1; then J is an appropriate index set. The vector U^{n} = (u_{j}^{n})_{j∈J} ∈ R^{|J|} is the (ordered) vector, the coefficients of which are the numerical approximations of the solution at time level n. Employing a regular grid with spatial step size Δx one obtains for the discretised diffusion operator

∇_{x} (D(u)∇_{x}u) ˙=\frac{1}{2Δx^{2}} ∑_{k∈N_{j}}(D(u_{k}^{n}) + D(u_{j}^{n}))(u_{k}^{n+1} − u_{j}^{n+1})  (3.1)

where N_{j} ⊂ J is the index set pointing at the direct neighbors of x_{j} on the grid. For d = 1 it has two elements, for d = 2 there are four and for d = 3 there are six. The non-standard finite difference scheme that is derived under the above assumptions reads

U^{n+1} − U^{n} = ΔtD(U^{n}) · U^{n+1} + ΔtKU^{n+1}  (3.2)

where K = diag(k_{j}^{n}) is the diagonal matrix the coefficients of which are the net growth rates k(t^{n}, x_{j}). The matrix D(U^{n}) is the banded matrix obtained by second order standard finite difference discretisation of the diffusion operator evaluated at the previous time-step t^{n}, according to (3.1).

System (3.2) can be re-written in matrix-vector form as

U^{n+1} = [I − ΔtD(U^{n}) − ΔtK]^{−1} U^{n}  (3.3)

if the inverse matrix exists. This is the case if the time-step Δt is chosen such that 1/Δt is not an eigenvalue of the matrix D(U^{n}) + K. Then, the numerical solution U^{n+1} is unique. Hence, a sufficient condition for the existence of a unique solutions is the restriction of the time-step size t^{n} → t^{n} + Δt =: t^{n+1} by

Δt · max_{i} k_{i}^{n} < 1  (3.4)

This ensures that I − ΔtK is diagonal with strictly positive entries. Then in (3.3) the matrix I − ΔtD(U^{n}) − ΔtK is diagonally dominant. Inequality (3.4) poses a time-step restriction for the numerical method. From the application point of view this is a weak restriction, as 1/k is the characteristic time scale of biomass production. Accordingly, time-steps larger than 1/k would be at the expense of inaccurate description of the growth process. The same time stepping condition (3.4) was obtained for the transformation method in [4]. If k is not a constant, (3.4) leads to a variable time-stepping strategy.

For a given U^{n} with 0 ≤ U^{n} < 1 (where all vector inequalities are understood coefficient-wise), U^{n+1} according to (3.3) is a continuous function of Δt. Hence, for Δt small enough U^{n} < 1 implies U^{n+1} < 1. A more quantitative statement will be presented in the next section.

The non-standard finite difference scheme (3.3) is a system of explicit non-linear difference equations, i.e. it can be understood as a discrete dynamic system. In the numerical simulation the solution of one coupled linear system is required in every time-step. The matrix is sparse, banded and diagonally dominant. In twoand three-dimensional simulations, the system can be solved iteratively, e.g. by the stabilised bi-conjugate gradient method, which is described in [21]; due to diagonal dominance, pre-conditioning is not required for convergence. In the one-dimensional case the system is tridiagonal and the Thomas algorithm (e.g. [10]) can be used. These are the methods that we employ in the simulations below.

In the next section we will show that the numerical solution according to (3.3) inherits the following important qualitative properties of the continuous model:

• positivity

• boundedness U^{n} < 1 of the solution

• finite speed of propagation of the discrete liquid/biofilm interface

• the solution of (3.3) satisfies a discrete interface condition that corresponds to the interface condition for the continuous model (2.1).

• the numerical interface is sharp, i.e. only weak interface smearing takes place

• the solution is monotonous at the interface and merging of two colonies is well-posed

3.2. Properties Of The Scheme.

Lemma 3.1 (Positivity). Let (3.4) be always satisfied. If 0 ≤ U^{0} < 1 then U^{n} ≥ 0

Proof. We use an argument from the theory of M-matrices (cf. [12]) and mathematical induction: If Δt is chosen according to (3.4) then the matrix in (3.3) is diagonally dominant with positive diagonal elements and non-positive off-diagonals.

Hence, its inverse is positive and, thus, positivity of U^{n} implies positivity of U^{n+1} according to iteration (3.3). □

Remark 3.2. An alternate proof can be derived based on the following observation: In the time step t^{n} → t^{n+1} method (3.2) can be understood as an implicit Euler method for the linear system of ordinary differential equations

v̇ = (D(U^{n}) + K) v, v(t^{n}) = U^{n}, t ∈ [t^{n}, t^{n+1}]  (3.5)

where v is a time-continuous vector valued function. Thus, method (3.2) is a piecewise linear problem and in every time-step linear theory applies, which can be found e.g. in [13]. Thus in every time-step positivity is ensured if the matrix in (3.5) has only non-negative off-diagonal entries and if the diagonal is bounded from below, i.e. if there is an α_{n} > 0 such that (D(U^{n}) + K)_{jj} > −α_{n}. That this is the case follows from a recursive argument: It is easily verified that these conditions are satisfied for n = 0. If they hold for one n then it follows from a simple calculation that it also holds for n+1, due to the assumption that Δt is small enough to warrant U^{n} < 1 and the definition of D(U). Note that both methods of proof for Lemma 3.1 use the same property of the system matrix in (3.3), and thus are essentially equivalent.

The M-matrix property is also used to derive the following sufficient (but not necessary) time-step condition for boundedness of the solution.

Lemma 3.3 (Boundedness). The choice of a time-step Δt such that (3.4) holds and

Δt < min_{i} \frac{1 − u_{i}^{n}}{∑_{j}[D(U^{n}) + K]_{ij}}

guarantees that the numerical solution obeys the upper bound, i.e. U^{n+1} ≤ 1 if U^{n} < 1.

Proof. We introduce W^{n} := e − U^{n} where e := (1, …, 1)^{T}. Hence, U^{n} ≤ 1 is equivalent to W^{n} ≥ 0. Then (3.3) gives

[I − ΔtD(U^{n}) − ΔtK] (e − W^{n+1}) = (e − W^{n})  (3.6)

and, therefore,

[I − ΔtD(U^{n}) − ΔtK] W^{n+1} = W^{n} − Δt [D(U^{n}) + K] e  (3.7)

If W^{n} > 0, positivity of W^{n+1} is ensured if Δt is chosen such that the right hand side of (3.6) is non-negative. This is certainly the case if

Δt < min_{i} \frac{1 − u_{i}^{n}}{∑_{j}[D(U^{n}) + K]_{ij}}  (3.8)
□

It is easy to verify that criterion (3.8) can be more strict than (3.4). It can be relaxed by the observation that it is sufficient but not necessary. Indeed, in the numerical simulations conducted below, this time-step criterion was implemented as an emergency strategy to guarantee the upper bound if other time-step control mechanisms fail, but never activated. Note that if in one coefficient U^{n} reaches 1, (3.4) implies the termination of the simulation. This is in accordance with the continuous problem (2.1), since it was shown in [9] that the solution of (2.1) can reach 1 in finite time in dependence of boundary conditions and reaction rates.

To formulate the next result we introduce the following concept. Definition. We denote by Ω_{1}^{n} a discrete grid analogy of Ω_{1}(t^{n}) as

Ω_{1}^{n} = {x_{j} : u_{j}^{n} = 0}

An interior point of Ω_{1}^{n} is a point in Ω_{1}^{n} whose direct neighbors are in Ω_{1}^{n} as well, i.e. a point x_{j} ∈ Ω_{1}^{n} such that x_{i} ∈ Ω_{1}^{n} for all i ∈ N_{j}. Similar definitions can be made for the biofilm region Ω_{2}

Note that this definition is based on the numerical solution u_{j}^{n}. Thus it does not imply that Ω_{1}^{n} is contained in Ω_{1}(t^{n}) or vice versa. For now, the discrete interface at time level t^{n} is defined by grid points of Ω_{1}^{n} with a direct neighbor in Ω_{2}^{n}. The following result states that the discrete interface travels at most with finite speed. In particular it states that in one time-step it moves across at most one grid cell.

Lemma 3.4 (Finite speed of propagation). Let (3.4) hold. If x_{j} is an interior point of Ω_{1}^{n} then x_{j} ∈ Ω_{1}^{n+1}.

Proof. If x_{j} ∈ Ω_{1}^{n} is interior then the corresponding jth row of the matrix D(U^{n}) contains only zeros. Thus one has from (3.3)

(1 − Δtk_{j}^{n})u_{j}^{n+1} = u_{j}^{n} = 0

with (3.4) it follows that u_{j}^{n+1} = 0 and thus x_{j} ∈ Ω_{1}^{n+1}. □

In the one-dimensional case d = 1 an explicit expression can be derived for the speed of interface propagation in the continuous model (2.1). An interface between Ω_{1}(t) and Ω_{2}(t) can be parameterised locally by a curve x^{∗}(t). The speed of the interface is ẋ^{∗}(t). Due to continuity and u(x^{∗}(t), t) = 0 we obtain from (2.1)

ẋ^{∗}(t) = −[u_{t}/u_{x}]_{x^{∗}(t)}  (3.9)

where the right hand side is to be understood in the sense of a limit of the quotient of the one-sided derivatives as one approaches the interface. The theory developed in [9] implies that this is finite. We show that the numerical solution satisfies a corresponding discrete interface condition if the derivatives in (3.9) are replaced by the usual difference quotients. Without loss of generality, we restrict ourselves to the case of an expanding biofilm (i.e. Ω_{2} increases) with an interface with positive speed. We define the location x_{j^{∗,n}} of a discrete interface at time t^{n} as follows: x_{j^{∗,n}−1} ∈ Ω_{2}^{n}, x_{j^{∗,n}} ∈ Ω_{2}^{n}, x_{j^{∗,n}+1} ∈ Ω_{1}^{n} and x_{j^{∗,n}+2} an interior point of Ω_{1}^{n}. That is, j^{∗,n} is the index of the last biofilm point before the liquid/biofilm interface at time t^{n}.

Lemma 3.5 (Moving interface condition). The following discrete interface condition holds

\frac{x_{j^{∗,n+1}} − x_{j^{∗,n}}}{Δx} = −\frac{u_{j^{∗,n+1}}^{n+1} − u_{j^{∗,n+1}}^{n}}{u_{j^{∗,n+1}+1}^{n+1} − u_{j^{∗,n+1}}^{n+1}}  (3.10)

Proof. For brevity of the notation let i := j^{∗,n}. We obtain from the (i + 1)th coefficient of (3.3) and the hypothesis on the position of the interface

−\frac{Δt}{2}D(u_{i}^{n})u_{i}^{n+1} + (1 + \frac{Δt}{2}D(u_{i}^{n}) − Δtk_{i+1}^{n})u_{i+1}^{n+1} = 0  (3.11)

and thus u_{i+1}^{n+1} > 0. With the previous Lemma we have that j^{∗,n+1} = i+1 = j^{∗,n}+1. Thus u_{j^{∗,n+1}}^{n} = 0. Furthermore we have by hypothesis u_{j^{∗,n+1}+1}^{n+1} = 0. The assertion follows by substituting these observations into (3.10). □

Note that (3.10) is a discrete version of (3.9) after multiplying with Δx/Δt. The proof showed that it could have been formulated in a stronger version that essentially states that the speed of propagation of the discrete interface is Δx/Δt. This is a consequence of the smearing around the interface that is introduced by the spatial discretisation of the diffusion operator. However, from (3.11) it follows

\frac{Δt}{2}D(u_{i}^{n}) [u_{i+1}^{n+1} − u_{i}^{n+1}] + [1 − Δtk_{i+1}^{n}] u_{i+1}^{n+1} = 0

and thus with (3.4) and the positivity of (3.3) we obtain 0 < u_{i+1}^{n+1} < u_{i}^{n+1}. Moreover, after re-arranging terms we have

u_{i+1}^{n+1} = O ((u_{i}^{n})^{b}u_{i}^{n+1})

with the definition (2.2), since u_{i}^{n} small at the interface implies (1 − u_{i}^{n}) ≫ 0. In biofilm applications one has b in the range 2 through 6. Thus we may expect the interface smearing effect to be quantitatively small. This will be demonstrated in the numerical simulations in the next section.

The last theoretical result in this section shows that the numerical solution at time t^{n+1} in a grid point in Ω_{1}^{n} is bounded from above by the values of the solution in neighboring grid points. This is of particular interest in the case where the grid point changes its membership from Ω_{1}^{n} to Ω_{2}^{n+1} as t^{n} → t^{n+1}, i.e. is passed by a biofilm/water interface.

Lemma 3.6 (Merging of two colonies). Let x_{i} ∈ Ω_{1}^{n} and assume that (3.4) holds. Then u_{i}^{n+1} is bounded by the values of u in the neighboring nodes, i.e.

0 ≤ u_{i}^{n+1} ≤ max_{j∈N_{i}}{u_{j}^{n+1}}

Proof. We have x_{i}^{n} ∈ Ω_{1}^{n} ⟹ u_{i}^{n} = 0 ⟹ D(u_{i}^{n}) = 0. Thus (3.2) and (3.1) imply

u_{i}^{n+1} = \frac{Δt}{Δx^{2}} ∑_{j∈N_{i}} D(u_{j}^{n})(u_{j}^{n+1} − u_{i}^{n+1}) + Δtk_{i}^{n}u_{i}^{n+1}

and, hence,

u_{i}^{n+1} = \frac{\frac{Δt}{Δx^{2}} ∑_{j∈N_{i}} D(u_{j}^{n})u_{j}^{n+1}}{1 + \frac{Δt}{Δx^{2}} ∑_{j∈N_{i}} D(u_{j}^{n}) − Δtk_{i}^{n}}

≤ \frac{\frac{Δt}{Δx^{2}} ∑_{j∈N_{i}} D(u_{j}^{n}) · max_{j∈N_{i}} u_{j}^{n+1}}{1 + \frac{Δt}{Δx^{2}} ∑_{j∈N_{i}} D(u_{j}^{n}) − Δtk_{i}^{n}}

≤ max_{j∈N_{i}} u_{j}^{n+1}

The last inequality follows from (3.4) with 1 − Δtk_{j}^{n} > 0. From Lemma 3.1, we have 0 ≤ u_{i}^{n+1}. □

Thus, if x_{i} ∈ Ω_{1}^{n} separates two approaching interfaces then Lemma 3.6 implies that the colonies merge smoothly without forming bulges or inducing oscillations. In the case of a single moving interface, Lemma 3.6 implies monotonicity, i.e. the absence of non physical oscillations. Note that Lemma 3.6 includes the previous Lemma 3.4 for the trivial case where x_{i} is interior to Ω_{1}^{n}.

Figure 3. Simulation of biofilm formation in time: the inoculum at t = 0 consist of (right) three sinusoidal colonies of different height and (left) two colonies with constant densities of different height.

4. Numerical Simulations

We present three sets of simulations of (2.1) with the nonstandard finite difference scheme (3.3). The first one is one-dimensional in space. While this does not fully capture the features of biofilm formation and growth it allows to investigate the behavior of the numerical scheme. In the second part of this section we carry out some two-dimensional numerical illustrations of biofilm growth for constant net growth rate k. In both cases we had for the parameters of the dimensionless equation a = b = 4, k = 0.1, δ = 10^{−8}. In the third simulation study we apply the discretisation scheme to a more complicated system, where biofilm formation is controlled by two dissolved substrates. All simulations were carried out using double accuracy arithmetics. Codes were implemented in Fortran 95 on Linux based personal computers. In all simulations the time-step was variable, as

Δt = min \{1/k, min_{j} \frac{MΔx^{2}}{D(u_{j}^{n})} , 0.1\}  (4.1)

The first condition is according to (3.4), the last one to keep the time-step bounded for the sake of accuracy. This was also the reason to introduce the second condition, where M is a user-defined constant. It renders the typical Δt/Δx^{2} dependency for parabolic problems and allows comparability of results for different choices of Δx. In our simulations, we use M = 40; this choice of time-step is well above the limitations of the explicit method. That said, this time-step constraint was introduced as a trade-off between between fast and accurate computation. The condition (3.8) was implemented as an emergency brake, such that it becomes active only if (4.1) would lead to max U^{n+1} > 1. It never became activated.

4.1. One-dimensional simulations. The results of two numerical simulations of (2.1) with the finite difference method presented here are shown in Figure 3. In case the (I), the initial data were specified by the function

u(x, 0) = max(0, −0.8 sin(7πx)(1 − x^{4})).

Figure 4. left: Location of the left interface between liquid and biofilm in the third scenario for different choices of Δx = 1/N, N = 50, 100, 200, 400, 800; right: solution of scenario 3 for various choices of N.

In the case (II), the initial data were specified by

u(x, 0) = \begin{cases}0.8, & 0.3 ≤ x ≤ 0.4 \\ 0.9, & 0.5 ≤ x ≤ 0.6, \\ 0, & elsewhere. \end{cases}

In the case (III), finally one sinusoidal colony was placed around the centre of the interval (0, 1). This scenario is included to study the dependence of the interface on the spatial resolution.

That is, in the first and third case the initial data are continuous but not differentiable at the interface, while in the second case they are only piecewise continuous. Both scenarios are known to be problematic if treated with standard techniques. It is easily verified that in the first case the biomass is organised in three colonies originally. Figure 3 shows the simulations of cases I and II. They were carried out with a spatial step-size Δx = 1/200.

In the third scenario the dependency of the simulation results on the spatial resolution was tested. To this end, the location of the actual interface between Ω_{1}(t) and Ω_{2}(t) for different step-sizes Δx = 1/N, N = 50, 100, 200, 400, 800 is plotted in the x-t plane. The second panel in Fig. 4 shows the solution surface for various Δx. In Figures 3 and 4 (right panel), the solution surfaces u(t, x) are plotted where |u| > 10^{−16} for the sake of readability, assuming that 10^{−16} is a reasonably good approximation of 0 for our purpose.

As predicted by the theory outlined above, the new numerical method gives non-negative and oscillation-free solutions. The simulations also confirm the above statement that the diffusive smearing around the interface is quantitatively small, i.e. negligible. In both first scenarios the colonies of the inoculum compress initially, that is the biomass density u increases while only very little spatial expansion is observed. As u approaches 1, Ω_{2} expands exponentially due to the first order growth term in (2.1) and the squeezing property. In both cases the colonies eventually merge. In the first scenario, the first initial colony is bigger than the second one, which is bigger than the third one. Accordingly the first and second colony merge first. The actual interface was defined somewhat arbitrary as the location at which u becomes bigger than 10^{−5} (as an approximation of 0). Both figures show a very good agreement. It can be seen that the computed interface converges as Δx becomes smaller. Even for the coarsest discretisation the deviations are accurate within Δx. This again confirms the above comment that the smearing effect at the interface is small.

Figure 5. Formation of a homogeneous, thick biofilm from originally heterogeneously distributed biomass. The substratum y = 0 is at the top of each picture. Shown are snap shots at t = 0.01, 1.22, 2.1, 2.98, 3.85, 4.45, 5.06, 6.16 (top left to bottom right). Biomass density u is coded in a linear greyscale: black corresponds to u = 0, white to u = 1.

4.2. A two-dimensional illustration: Formation of a homogeneous biofilm. The simplified biofilm model (2.1) with positive k = const describes biofilm formation under non-limiting conditions. This can be the case for nutrient rich environments, e.g. bacterial growth in foods or relatively thin biofilms (in the initial stages) in wastewater treatment plants. For many other biofilms this is not a realistic assumption because often either nutrients or oxygen or ph-value or other controlling substances are not constant inside the biofilm. Typically, the thicker a biofilm is, the more limited become nutrients in the deeper layers. Often, decay due to lysis will even become dominant, leading to negative local net growth rates. This spatially heterogeneous situation will be addressed in the next section. Since we want to focus on the spatial discretisation of models of this kind first, we nevertheless accept the case k = const for an illustrative example. Under such non-limiting conditions it is expected (cf. [5], [23]) that even starting from a heterogeneous initial distribution of biomass, a homogeneous biofilm will form eventually and that the biomass distribution within Ω_{2} will be more or less homogeneous. This will be verified in the following simulations.

Initially biomass is randomly distributed in 15 different locations across the substratum, i.e. the surface on which the biofilm forms. That is, the biomass is placed initially in the first layer of grid cells. The biomass density in each of these locations is chosen randomly between 0 and 1. The computational domain is the interval [0, 1]×[0, 0.3]. We specify Neumann boundary conditions at the substratum y = 0.3 and on the boundaries x = 0, x = 1. The first assumptions ensures that no biomass leaves the system across the solid surface, while the second assumption allows us to consider the computational domain as part of a larger system (periodic conditions would do this as well). At y = 0 we specify homogeneous Dirichlet conditions. The results of a simulation are shown in Figure 5. The rate at which the biofilm colonies grow depends initially on the biomass density at t = 0. Colonies with larger u(x, 0) grow faster and merge earlier with their neighbors. Eventually all colonies merge and form a compact film as expected. As it was already observed in the one-dimensional simulations, the biomass density inside the biofilm approaches the maximum density rapidly everywhere, due the homogeneous growth rate.

4.3. A two-dimensional illustration: Formation of a cluster-and-channel biofilm. We investigate now the more general case where the local growth of biomass is controlled by the availability of required substances. As an example we choose a heterotrophic biofilm that is limited by two dissolved substrates, nutrients and oxygen. This is a standard example of biofilm systems in wastewater engineering and was defined by the International Water Association’s taskgroup on biofilm modeling as a first benchmark system (BM1) for biofilm models, cf. [18], [23]. The local net growth rate k(t, x) in this example is given by

k(t, x) = k_{1} \frac{c_{1}(t, x)}{k_{s,1} + c_{1}(t, x)} \frac{c_{2}(t, x)}{k_{s,2} + c_{2}(t, x)} − k_{3}  (4.2)

where the positive constant k_{1} is the maximum specific growth rate and the positive constant k_{3} is the lysis rate describing biomass deactivation. The positive parameters k_{s,1} and k_{s,2} are the Monod half saturation constants. By c_{1} and c_{2} we denote the concentrations of the dissolved substrates. They are governed by the semi-linear diffusion-reaction equations

c_{1,t} = D_{1}Δ_{x}c_{1} − k_{4}u\frac{c_{1}}{k_{s,1} + c_{1}} \frac{c_{2}}{k_{s,2} + c_{2}}  (4.3)

and

c_{2,t} = D_{2}Δ_{x}c_{2} − k_{5}u\frac{c_{1}}{k_{s,1} + c_{1}} \frac{c_{2}}{k_{s,2} + c_{2}}  (4.4)

where the consumption rates k_{4} and k_{5} are essentially the maximum specific growth rate divided by the respective yield factors, which quantify how much substrate is needed to produce one unit mass of microbial biomass. The positive parameters D_{1} and D_{2} are the diffusion coefficients of both substrates. For small molecules these are constants, attaining the same values in the biofilm and in the surrounding bulk phase. For our simulation we choose the same reaction and diffusion parameters as in the benchmark problem specification in [18].

The model is completed by initial and boundary conditions for c_{1} and c_{2}. We choose the computational domain to be rectangular of size L_{1} × L_{2} and specify the mixed boundary conditions for j = 1, 2

c_{j} = c_{∞,j} for x_{2} = L_{2}

and

\frac{∂c_{j}}{∂n} = 0 elsewhere on ∂Ω

The initial conditions for c_{1,2} are

c_{j}(x, 0) = c_{∞,j}

For the biomass density u we specify the same initial and boundary conditions as in the previous example.

The purpose of this example is to show that the numerical scheme is able to simulate the formation of spatially heterogeneous of mushroom-shaped cluster-and-channel biofilm architectures. It is well understood in the biofilm literature, cf [23], that a good predictor for the surface heterogeneity of a biofilm is how biomass growth terms relate to substrate availability. If substrate does not become limited, a flat, spatially homogeneous biofilm is eventually obtained, as in the previous example. If substrate in the biofilm becomes limited, growth of biomass slows down. Microbial inner-species competition for nutrients leads to irregular biofilm morphologies. Eventually larger biofilm colonies closer to the food source become dominating and smaller colonies stay back in their development. With our choice of parameters from [18], the growth terms are fixed. Hence, we use substrate availability to control the biofilm structure. It is quantified in terms of the diffusion coefficients (also fixed from [18]) and the environmental conditions, in particular the Dirichlet values c_{∞,j} and the diffusion length L_{2}. We choose the bulk concentrations in the same range as the Monod half saturation concentrations, c_{∞,1} = k_{s,1} and c_{∞,2} = 2k_{s,2}. The maximum principle for parabolic equations implies that these values are upper estimates for the concentrations c_{1} and c_{2} and that inside the domain and, hence, in the biofilm lower concentration values will be obtained. Thus, our choice of environmental concentrations ensures that substrates are not available in abundance. The system height L_{2} is the distance over which substrates need to be transported by diffusion to reach the bacteria at the substratum. The smaller this value is, the more compact a biofilm develops [23]. We choose L_{2} = L_{1} = 500μm, i.e. carry out our simulations in a square domain.

For the numerical solution of (4.3) and (4.4) we use a standard finite volume scheme on the same grid on which (2.1) is discretised, 2nd order in space and 1st order in time. The simulation results of this example are shown in Figure 6; plotted are the biofilm/liquid interface and the concentration field of oxygen, c_{2}. The nutrient concentration field c_{1} is qualitative similar, albeit on a higher quantitative level. Initially the substratum is inoculated by few small bacterial colonies. As time increases, first a smooth, almost homogeneous, smooth biofilm layer develops which than changes in a cluster-and-channel morphology as substrates become limited. It should be noted that due to the lysis term in (4.2) and due to substrate limitations the active biomass density remains distinctively separated from the maximum biomass density, i.e. u < 1 clearly. Thus, the simulation results agree with our a priori expectations on model behavior.

5. Conclusion

A finite difference scheme was developed for a parabolic evolution equation with two distinct nonlinear effects in the density-dependent diffusion coefficient. One is degeneracy as in the porous medium equation, while the other one is a singularity as the dependent variable approaches its a priori known maximum value. In the numerical method, the nonlinearity of the diffusion operator was handled in a nonlocal representation in time. It was shown that the numerical method renders the essential qualitative features of the solution of the continuous problem. In particular it is free of non physical oscillations that often are observed in problems of this kind, it shows the finite speed of propagation of interfaces between the regions Ω_{1}(t) where u = 0 and Ω_{2}(t) where u > 0, and it guarantees that the upper bound of the solution.

The nonstandard finite difference scheme for the proto-type biofilm model (2.1) is based on a non-local in time representation of the nonlinear diffusive flux. The method was constructed in a manner that allows a straightforward application to more complicated biofilm systems with several particulate substances as in section 44.3 and dissolved substrates, i.e. for models as studied in e.g. [6], [7]. Although only one- and two-dimensional simulations have been carried out here for the illustration of the new method, an application to more realistic three-dimensional biofilm descriptions is possible. In fact, the method (3.3) itself is formulated in the general setup and the analytical results were derived for the three-dimensional case. This makes the new method attractive for further studies in mathematical modeling of biofilms.

Acknowledgments. This study was supported by the Volkswagen Stiftung, Hannover, Germany with a grant in Interdisciplinary Environmental Research, by the NSERC Canada with a Discovery Grant and by the Advanced Foods and Materials Network of Centres of Excellence (AFMnet) with a project grant. The original draft version of this manuscript was written while the first author visited the GSF Research Centre in Neuherberg, Germany. The authors also wish to thank Messoud Efendiev for many stimulating discussions. The CLSM micrograph was made available by Heidi Schraft, Dept. Biology, Lakehead University, Thunder Bay, ON.

References

[1] Anguelov R, Lubuma J. M. S. Contributions to the mathematics of the nonstandard finite difference method and its applications, Num. Meth. PDE 17:518-543, 2001

[2] Baines M. J., Hubbard M. E., Jimack P. K., A moving mesh finite element algorithm for the adaptive solution of time dependent PDEs with moving boundaries, Appl. Num. Math., 54:450-469, 2005

[3] Costerton JW, Lewandowsky Z, Caldwell DE, Korber DR, Lappin-Scott HM, Microbial Biofilms, Annu. Rev. Microbiol. 49:711-745, 1995

[4] Duvnjak A, Eberl H. J. Time-discretisation of a degenerate reaction-diffusion equation arising in biofilm modeling, El. Trans Num. Analysis, 23:15-38, 2006 [5] Eberl H. J., Parker D. F., van Loosdrecht M. C. M. A new Deterministic Spatio-Temporal

Continuum Model For Biofilm Development, J. Theor. Medicine, 3(3), 2001

[6] Eberl H. J., Efendiev M. A. A Transient Density Dependent Diffusion-Reaction Model for the Limitation of Antibiotic Penetration in Biofilms. El. J. Diff Eq. CS10:123-142, 2003

[7] Eberl H. J., A deterministic continuum model for the formation of EPS in heterogeneous biofilm architectures, Proc. Biofilms 2004, Las Vegas, 2004

[8] Eberl H. J., Schraft H., A diffusion-reaction model of a mixed culture biofilm arising in food safety studies, accepted

[9] Efendiev M. A., Eberl H. J., Zelik S. V., Existence and longtime behavior of solutions of a nonlinear reaction-diffusion system arising in the modeling of biofilms. RIMS Kyoto, 1258:49-71, 2002

[10] Epperson J. F., An Introduction to Numerical Methods and Analysis, Wiley & Sons, 2002 [11] Flemming H. C., Biofilme – das Leben am Rande der Wasserphase, Nachr. Chemie, 48:442-

447, 2000

[12] Hackbusch W., Theorie und Numerik elliptischer Differentialgleichungen, Teubner, Stuttgart, 1986

[13] Hundsdorfer W., Verweer J. G., Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations, Springer, 2003

[14] Khassekhan H., Eberl H. J., Interface tracking for a non-linear degenerated diffusion-reaction equation describing biofilm formation, accepted

[15] Van Loosdrecht M. C. M., Eikelboom D., Gjaltema A., Mulder A., Tijhuis L., Heijnen J. J., Biofilm Structures, Wat. Sci. Tech. 32(8):35-43, 1995

[16] Van Loosdrecht M. C. M. , Picioreanu C., Heijnen J. J., A more unifying hypothesis for the structure of microbial biofilms, FEMS Microb. Ecol., 24:181183, 1997

[17] Mickens R. E. Nonstandard finite difference schemes, in Mickens R. E. (ed), Applications of nonstandard finite difference schemes, World Scientific, Singapore, 2000

[18] Morgenroth E., Eberl H. J., Van Loosdrecht M.C. M., Noguera D. R., Picioreanu C, Rittmann BE, Schwarz AO, Wanner O. Results from the single species benchmark problem (BM1), Wat. Sci. Tech., 49(11/12):145-154, 2004

[19] Morton K. W., Mayers D. F., Numerical solution of partial differential equations, Cambridge Univ. Press, 1994

[20] Picioreanu C., Van Loosdrecht M. C. M., Use of mathematical modelling to study biofilm development and morphology. In: Lens P et al (eds). Biofilms in Medicine, Industry and Environmental Biotechnology Characteristics, Analysis and Control, IWA Publishing. pp 413-437, 2003

[21] Saad Y., Iterative Methods for Sparse Linear Systems, 2nd edition, 2000

[22] Stewart P. S., Multicellular nature of biofilm protection from antimicrobial agents, in: McBain A et al (eds), Biofilm Communities: Order from Chaos, BioLine, 2003

[23] Wanner O., Eberl H. J., Van Loosdrecht M. C. M., Morgenroth E., Noguera D. R., Picioreanu C, Rittmann BE. Mathematical Modeling of Biofilms, IWA Publishing, 2006

[24] Watnick P., Kolter R., Biofilm – City of Microbes (Minireview), J. Bacteriol., 182(10):2675-2679, 2000

[25] Wilderer P. A., Bungartz H. J., Lemmer H., Wagner M., Keller J., Wuertz S., Modern Scientific Methods and their Potential in Wastewater Science and Technology, Water Res. 36:370-393, 2002

[26] Xu K. D., Stewart P. S., Xia F., Huang C.-T., McFeters G. A., Spatial physiological heterogeneity in Pseudomonas aeruginosa biofilm is determined by oxygen availability, Appl. and Env. Microbiol., 64(10):4035-4039, 1998

Hermann J. Eberl Dept. Mathematics and Statistics, University of Guelph, Guelph, On, Canada

E-mail address: heberl@uoguelph.ca

Laurent Demaret Inst. Biomathematics and Biometry, GSF - National Research Centre for Environment and Health, Neuherberg, Germany

E-mail address: laurent.demaret@gsf.de

Figure 6. Formation of a cluster-and-channel biofilm morphology (top left to bottom right): Shown are the biofilm/liquid interface and the limiting oxygen concentration c_{2}(t, x) in time t = 0.02, 4.03, 6.05, 9.08, 19.12, 39.13d. The food source is located at the right boundary x_{2} = L_{2}.

Figure 7. Figure 6 continued for t = 79.13, 119.13, 159.13, 199.13, 229.20, 249.35d