Mimetic Finite Difference Schemes with Conditional Maximum Principle for Diffusion Problems

Abstract

Numerical schemes that satisfy the maximum principle play important role in multiphysics codes. They reduce significantly various numerical artifacts. We describe a novel inexpensive practical algorithm for building mimetic finite difference schemes with conditional maximum principle on polygonal and polyhedral meshes for diffusion problems.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Numerical schemes that preserve important properties of underlying PDEs lead in general to more robust computer simulations. These schemes reduce significantly or eliminate totally various numerical artifacts. An important property of a diffusion problem is the existence of the maximum principle (MP). In its simplest form, it states that in absence of external sources, the continuum solution has no internal extrema. This implies that physical quantities, such as temperature or chemical concentration, are always bounded by the boundary data.

It is well known that the second-order linear schemes for the diffusion equation satisfy the MP only under some conditions on the mesh and diffusion tensor. Analysis of sufficient conditions for the MP on unstructured simplicial meshes started in 70th, see e.g. [2]. For the mimetic finite difference (MFD) method, sufficient conditions were formulated in [5]; however, algorithms for their verification were developed for a limited class of meshes. Here, we propose a practical algorithm for verifying the sufficient conditions and building mimetic schemes with the MP for meshes with arbitrarily-shaped cells. The algorithm satisfies a few requirements of emerging computer architectures: large flops per memory ratio and data locality.

A detailed description of the MFD method can be found in the recently published book [8] which focuses on numerical solution of elliptic PDEs. In general, the concept of mimetic (or compatible in general) schemes can be applied to a greater variety of PDEs (see [4] and references therein). The incomplete list of related compatible discretization methods includes discrete duality finite volume (FV), hybrid FV and mixed FV methods. For diffusion problems, the algebraic equivalence of the MFD, mixed FV, and hybrid FV methods has been shown in [3].

The paper outline is as follows. In Sect. 2, we describe briefly the MFD method. In Sect. 3, we formulate sufficient conditions for the MP and present a practical algorithm for verifying them and selecting an optimal scheme. In Sect. 4, we analyze numerically the complexity of the proposed algorithm.

2 A Family of Mimetic Finite Difference Schemes

Let $\varOmega \subset \mathfrak {R}^d$, $d=2$ or $3$, be a bounded domain with a Lipschitz boundary $\varGamma$. We consider the following mixed formulation of the elliptic equation:

$$\begin{aligned} {\mathbf u}= - {\mathbb K}\nabla p \quad \text {and}\quad \mathrm{div}\, {\mathbf u}= b, \end{aligned}$$

(1)

where $p$ is pressure, ${\mathbf u}$ is velocity, ${\mathbb K}$ is symmetric diffusion tensor, and $b$ is source term. To simplify the presentation, we assume that $p = 0$ on $\varGamma$.

Let $\varOmega _h$ be a conformal partition of $\varOmega$ into polyhedral ($d=3$) or polygonal ($d=2$) cells $\mathrm{c}$. We denote by $|\mathrm{c}|$ the volume (area in 2D) of cell $c$. For face $\mathrm{f}$ of cell $\mathrm{c}$, we denote by $|\mathrm{f}|$ its area (length in 2D) and by ${\mathbf n}_{\mathrm{f},\mathrm{c}}$ its exterior unit normal vector. We assume that the diffusion tensor has constant value ${\mathbb K}_\mathrm{c}$ in cell $\mathrm{c}$.

The discrete pressure space $Q_{h}$ consists of one degree of freedom per cell, $p_\mathrm{c}$, and one degree of freedom per face, $p_\mathrm{f}$, approximating the average pressure value in $\mathrm{c}$ and $\mathrm{f}$, respectively. Thus, the dimension of $Q_{h}$ equals to the number of mesh cells plus the number of mesh faces.

The discrete velocity space $X_{h}$ consists of one degree of freedom, $u_{\mathrm{f},\mathrm{c}}$, per face $\mathrm{f}$ of cell $\mathrm{c}$, which approximates the average flux ${\mathbf u}\cdot {\mathbf n}_{\mathrm{f},\mathrm{c}}$ across face $\mathrm{f}$. Thus, the dimension of $X_{h}$ equals to the number of boundary faces plus twice the number of interior faces. For each vector ${\mathbf u}_h\in X_h$, we denote by ${\mathbf u}_{h,\mathrm{c}}$ its restriction to cell $\mathrm{c}$, i.e. ${\mathbf u}_{h,\mathrm{c}} =\{u_{\mathrm{f},\mathrm{c}}\}_{\mathrm{f}\in \partial \mathrm{c}}$. The mass conservation law implies the following condition:

$$\begin{aligned} u_{\mathrm{f},\mathrm{c}_1} = -u_{\mathrm{f},\mathrm{c}_2}, \end{aligned}$$

(2)

for each face $\mathrm{f}$ shared by cells $\mathrm{c}_1$ and $\mathrm{c}_2$.

Integrating the second equation in (1) over cell $\mathrm{c}$, we obtain:

$$\begin{aligned} \mathrm{div}^h {\mathbf u}_{h,\mathrm{c}} = b_c,\quad \mathrm{div}^h {\mathbf u}_{h,\mathrm{c}} = \frac{1}{|\mathrm{c}|}\,\sum \limits _{\mathrm{f}\in \partial \mathrm{c}} |\mathrm{f}|\,u_{\mathrm{f},\mathrm{c}}, \quad b_c = \frac{1}{|\mathrm{c}|} \int _\mathrm{c}b \mathrm{d}V. \end{aligned}$$

(3)

What is left is to discretize the first equation in (1).

2.1 Consistency and Stability Conditions

The constitutive equation is discretized using the consistency and stability conditions. The consistency condition is the exactness property and can be formulated in a variety of ways. Here we use the FV viewpoint that is more appropriate for the practical implementation of the MFD method; however, it hides its theoretical roots.

Let us consider a cell $\mathrm{c}$ with $n_\mathrm{c}$ faces $\mathrm{f}_i$. We assume that there exists a linear relationship between the discrete unknowns,

$$\begin{aligned} \left( \begin{array}{c} u_{\mathrm{f}_1,\mathrm{c}}\\ u_{\mathrm{f}_2,\mathrm{c}} \\ \vdots \\ u_{\mathrm{f}_{n_\mathrm{c}},\mathrm{c}}\end{array}\right) = -{\mathbb W}_\mathrm{c}\left( \begin{array}{c} |\mathrm{f}_1|\,(p_{\mathrm{f}_1} - p_\mathrm{c}) \\ |\mathrm{f}_2|\,(p_{\mathrm{f}_2} - p_\mathrm{c}) \\ \vdots \\ |\mathrm{f}_{n_\mathrm{c}}|\,(p_{\mathrm{f}_{n_\mathrm{c}}} - p_\mathrm{c})\end{array}\right) , \end{aligned}$$

(4)

with a symmetric and positive definite matrix ${\mathbb W}_\mathrm{c}$. Then, the mimetic scheme is defined by collecting Eqs. (4), (2), (3) and imposing the homogeneous boundary conditions, i.e. $p_{\mathrm{f}} = 0$ for all $\mathrm{f}\in \varGamma$.

To define matrix ${\mathbb W}_\mathrm{c}$, we require that (4) is exact for any linear function $p$ and the corresponding constant vector function ${\mathbf u}$. It is sufficient to consider $d + 1$ linearly independent pressure functions: $p_0 = 1$, $p_1 = x$, $p_2 = y$ and $p_3 = z$ in 3D. Obviously, formula (4) is trivial for $p_0 = 1$ and ${\mathbf u}_0 = \mathbf{0}$. Taking pairs $p_i$ and ${\mathbf u}_i = -{\mathbb K}_\mathrm{c}\nabla p_i$, calculating vectors of degrees of freedom and inserting them in (4), we obtain $d$ matrix equations:

$$\begin{aligned} {\mathbb N}_{\mathrm{c},i} = {\mathbb W}_\mathrm{c}{\mathbb R}_{\mathrm{c},i}, \qquad 1 \le i \le d, \end{aligned}$$

(5)

where ${\mathbb N}_i$ and ${\mathbb R}_i$ are $n_\mathrm{c}\times 1$ vectors. These vectors can be calculated using only areas, centroids and normals to faces of $\mathrm{c}$ which results in relatively simple calculations for an arbitrary-shaped cell (see [8, Chap. 5] or [4] for more details).

Let us define $n_\mathrm{c}\times d$ matrices ${\mathbb N}_\mathrm{c}= [{\mathbb N}_{\mathrm{c},1}, \ldots , {\mathbb N}_{\mathrm{c},d}]$ and ${\mathbb R}_\mathrm{c}= [{\mathbb R}_{\mathrm{c},1}, \ldots , {\mathbb R}_{\mathrm{c},d}]$. It has been proved in [1] that a particular solution to matrix Eq. (5) is

$$ {\mathbb W}_{\mathrm{c}}^{(0)} = \frac{1}{|\mathrm{c}|} {\mathbb N}_\mathrm{c}\, {\mathbb K}_\mathrm{c}^{-1}\, {\mathbb N}_\mathrm{c}^T. $$

The rank of this matrix is $d$ which is strictly less than $n_\mathrm{c}$. Thus, to build a positive definite $n_\mathrm{c}\times n_\mathrm{c}$ matrix ${\mathbb W}_\mathrm{c}$, we have to add a stabilization term ${\mathbb W}_{\mathrm{c}}^{(1)}$ such that ${\mathbb W}_{\mathrm{c}}^{(1)} {\mathbb R}_\mathrm{c}= 0$. The stability condition imposes lower and upper bounds on this term. More precisely, it requires the matrix ${\mathbb W}_\mathrm{c}= {\mathbb W}_{\mathrm{c}}^{(0)} + {\mathbb W}_{\mathrm{c}}^{(1)}$ to be spectrally equivalent to a scalar matrix:

$$\begin{aligned} a_\star \frac{1}{|\mathrm{c}|} \Vert {\mathbf u}_{h,\mathrm{c}} \Vert ^2 \le {\mathbf u}_{h,\mathrm{c}}^T {\mathbb W}_\mathrm{c}{\mathbf u}_{h,\mathrm{c}} \le a^\star \frac{1}{|\mathrm{c}|} \Vert {\mathbf u}_{h,\mathrm{c}} \Vert ^2 \qquad \forall {\mathbf u}_{h,\mathrm{c}}, \end{aligned}$$

(6)

where $a_\star$ and $a^\star$ are mesh independent positive constants, and $\Vert \cdot \Vert$ denotes the Eucleadian norm.

2.2 A Family of Stable Mimetic Schemes

Let us introduce a full rank matrix ${\mathbb D}_\mathrm{c}$ such that its columns span the null space of matrix ${\mathbb R}_\mathrm{c}^T$, i.e. ${\mathbb R}_\mathrm{c}^T\,\ {\mathbb D}_\mathrm{c}= {\mathbb O}$, where ${\mathbb O}$ denotes a generic zero matrix. We assume that the columns of ${\mathbb D}_\mathrm{c}$ are orthonormal vectors. Then,

$$ {\mathbb W}_\mathrm{c}^{(1)} = {\mathbb D}_\mathrm{c}\, {\mathbb P}_\mathrm{c}\, {\mathbb D}_\mathrm{c}^T, $$

where ${\mathbb P}_\mathrm{c}$ is a symmetric positive definite matrix of parameters. The stability condition does not allow ${\mathbb P}_\mathrm{c}$ to have arbitrarily small or large eigenvalues. In practice, a good choice for ${\mathbb P}_\mathrm{c}$ is the scalar matrix $\alpha _\mathrm{c}{\mathbb I}$ where $\alpha _\mathrm{c}= \frac{1}{n_\mathrm{c}} \mathrm{trace}({\mathbb W}_\mathrm{c}^{(0)})$. In this case, the condition number of ${\mathbb W}_\mathrm{c}$ depends only on the anisotropy of tensor ${\mathbb K}_\mathrm{c}$ and the shape-regularity constants of cell $\mathrm{c}$.

3 Mimetic Schemes with the Maximum Principle

For a polyhedral mesh, a family of admissible mimetic schemes is quite large. Indeed for each polyhedral cell with $n_\mathrm{c}$ faces, we have $(n_\mathrm{c}-d+1) \times (n_\mathrm{c}-d)/2$ parameters forming the symmetric matrix ${\mathbb P}_\mathrm{c}$. Ideally, these parameters have to be selected to enforce the MP.

3.1 Sufficient Conditions

We recall sufficient conditions for the MP proposed in [5]. Inserting (4) into (2) and (3), we obtain a system of algebraic equations for the pressure unknown ${\mathbf p}_h \in Q_h$:

$$ {\mathbb A}{\mathbf p}_h = {\mathbf b}_h, \quad {\mathbb A}= \sum \limits _{\mathrm{c}\in \varOmega _h} \mathcal{N}_\mathrm{c}\, {\mathbb A}_\mathrm{c}\, \mathcal{N}_\mathrm{c}^T, $$

where $\mathcal{N}_\mathrm{c}$ is an assembling matrix with $0$ and $1$ entries. The sufficient conditions for the MP are such that each cell matrix ${\mathbb A}_\mathrm{c}$ is a singular M-matrix. If so, the global matrix ${\mathbb A}$ is a singular M-matrix. Eliminating equations corresponding to the Dirichlet boundary conditions, $p_\mathrm{f}= 0$ for $\mathrm{f}\in \varGamma$, we obtain an M-matrix [5]. Hence, solution ${\mathbf p}_h$ satisfies the MP.

Let us rewrite the mass balance equation (3) in the algebraic form ${\mathbb B}_\mathrm{c}^T {\mathbf u}_{h,\mathrm{c}} = |\mathrm{c}|\,b_\mathrm{c}$ where ${\mathbb B}_\mathrm{c}$ is the column matrix, ${\mathbb B}_\mathrm{c}= (|\mathrm{f}_1|,\ldots ,|\mathrm{f}_{n_\mathrm{c}}|)^T$. We define a square diagonal matrix ${\mathbb C}_\mathrm{c}$ such that ${\mathbb C}_\mathrm{c}\mathbf{1} = {\mathbb B}_\mathrm{c}$, where $\mathbf{1}$ is a generic vector with all entries equal to $1$. According to [5], the cell-based matrix has the following structure:

$$ {\mathbb A}_\mathrm{c}= \left( \begin{array}{rr} {\mathbb C}_\mathrm{c}^T\, {\mathbb W}_\mathrm{c}\, {\mathbb C}_\mathrm{c}&{} -{\mathbb C}_\mathrm{c}^T\, {\mathbb W}_\mathrm{c}\, {\mathbb B}_\mathrm{c}\\ -{\mathbb B}_\mathrm{c}^T\, {\mathbb W}_\mathrm{c}\, {\mathbb C}_\mathrm{c}&{} {\mathbb B}_\mathrm{c}^T\, {\mathbb W}_\mathrm{c}\, {\mathbb B}_\mathrm{c}\end{array}\right) . $$

Lemma 1

([5]). The matrix ${\mathbb A}_\mathrm{c}$ is a singular M-matrix if ${\mathbb W}_\mathrm{c}$ is an M-matrix and the vector ${\mathbb W}_\mathrm{c}\, {\mathbb B}_\mathrm{c}$ has non-negative entries.

3.2 Simplex Method for Matrix ${\mathbb W}_\mathrm{c}$

The simplex method is used twice in the construction of matrix ${\mathbb W}_\mathrm{c}$ that satisfies the conditions of Lemma 1. First, it answers the question of the existence of at least one such matrix. Second, it finds an optimal (in some sense) matrix when a few matrices satisfy Lemma 1. In this section, we drop out subscript ‘$\mathrm{c}$’ from all matrices.

We illustrate this method for the quadrilateral cell, i.e. $n_\mathrm{c}= 4$, $d=2$. Despite its simple shape, the direct construction of an M-matrix ${\mathbb W}$ was an open problem until now. The matrix of parameters is a $2 \times 2$ matrix characterized typically by three parameters. However, since the simplex method requires all parameters to be non-negative, we need four parameters to describe negative off-diagonal entries:

$$ {\mathbb P}= \left( \begin{array}{cc} a_1 &{} ~a_3 - a_4 \\ a_2 - a_4~ &{} a_2 \end{array}\right) , \quad a_i \ge 0. $$

Unless we enforce somehow the positive definiteness of matrix ${\mathbb P}$, we can only guarantee the symmetry of ${\mathbb W}$. Direct control of the properties of ${\mathbb P}$ is undesirable, since it leads to a nonlinear optimization problem. Fortunately, the properties of a M-matrix allow us to circumvent this problem. The first set of linear inequalities enforces the Z-matrix property for ${\mathbb W}= {\mathbb W}^{(0)} + {\mathbb W}^{(1)}$:

$$ a_1 {\mathbb D}_{1i} {\mathbb D}_{1j} + a_2 {\mathbb D}_{2i} {\mathbb D}_{2j} + (a_3 - a_4) \big ({\mathbb D}_{1i} {\mathbb D}_{2j} + {\mathbb D}_{2i} {\mathbb D}_{1j}\big ) \le -{\mathbb W}_{ij}^{(0)} \quad \forall i<j. $$

Recall that a Z-matrix ${\mathbb W}$ is an M-matrix if there exists a vector ${\mathbf v}$ with non-negative entries such that ${\mathbb W}{\mathbf v}\ge \varepsilon > 0$, i.e. all entries of this matrix-vector product are strictly positive. We take ${\mathbf v}= {\mathbb B}$, so that the later property implies the second condition of Lemma 1. Since ${\mathbb W}^{(0)}{\mathbf v}= 0$, the resulting set of inequalities reads:

$$ \sum \limits _{j = 1}^{n_\mathrm{c}} |\mathrm{f}_j|\Big ( a_1 {\mathbb D}_{1i} {\mathbb D}_{1j} + a_2 {\mathbb D}_{2i} {\mathbb D}_{2j} + (a_3 - a_4) \big ({\mathbb D}_{1i} {\mathbb D}_{2j} + {\mathbb D}_{2i} {\mathbb D}_{1j}\big )\Big ) \ge \varepsilon _i \quad \forall i, $$

where $\varepsilon _i > 0$. In practice, we take $\varepsilon _i = \lambda _{\min }({\mathbb K}_\mathrm{c}) / (10 |\mathrm{c}|)$. This choice leads to mesh-independent coefficients $a_\star$ and $a^\star$ in the stability condition (6).

The objective functional that the simplex method maximizes is the sum of all entries in ${\mathbb W}$ (this maximizes the diagonal dominance of ${\mathbb W}$):

$$\begin{aligned} \max \limits _{a_i \ge 0} \varPhi (\{a_i\}), \qquad \varPhi (\{a_i\}) = \sum \limits _{i,j=1}^{n_\mathrm{c}} {\mathbb W}_{ij}. \end{aligned}$$

(7)

Note that other linear objective functionals can be also admissible. The simplex method requires to convert the inequality constraints to equality constraints. We introduce the slack (or surplus, or logical) non-negative variables $s_{ij}$ and $s_i$:

$$\begin{aligned} a_1 {\mathbb D}_{1i} {\mathbb D}_{1j} + a_2 {\mathbb D}_{2i} {\mathbb D}_{2j} + (a_3 - a_4) \big ({\mathbb D}_{1i} {\mathbb D}_{2j} + {\mathbb D}_{2i} {\mathbb D}_{1j}\big ) + s_{ij} = -{\mathbb W}^{(0)}_{ij} \end{aligned}$$

(8)

and

$$\begin{aligned} \sum \limits _{j = 1}^{n_\mathrm{c}} |\mathrm{f}_j|\Big ( a_1 {\mathbb D}_{1i} {\mathbb D}_{1j} + a_2 {\mathbb D}_{2i} {\mathbb D}_{2j} + (a_3 - a_4) \big ({\mathbb D}_{1i} {\mathbb D}_{2j} + {\mathbb D}_{2i} {\mathbb D}_{1j}\big )\!\Big ) + s_i = \varepsilon _i. \end{aligned}$$

(9)

The total number of slack variables is $n_\mathrm{c}(n_\mathrm{c}+ 1) / 2$. The slack variables are treated like the original parameters $a_i$ until the last moment when they are just ignored. Each slack variable is the amount by which the original inequality is satisfied. The optimization problem is now to find the maximum of functional $\varPhi$ subject to the equality constraints (8), (9) and the inequality constraints $a_i \ge 0$, $s_{ij} \ge 0$, $s_i \ge 0$.

To launch the simplex method, we need to prescribe valid (i.e. non-negative) initial values for the variables $a_i$, $s_{ij}$ and $s_i$ so that the above equalities are satisfied. In general, finding such a guess is equally as difficult as finding an optimal solution. Fortunately, computation of valid initial values can be done by the simplex itself.

Let us assume that the right-hand sides in (8) are non-negative which can be easily achieved by multiplying the corresponding equations by $-1$. Then, we introduce $n_\mathrm{c}(n_\mathrm{c}- 1) / 2$ additional artificial (or logical) variables $y_{ij}$ such that

$$\begin{aligned} a_1 {\mathbb D}_{1i} {\mathbb D}_{1j} + a_2 {\mathbb D}_{2i} {\mathbb D}_{2j} + (a_3 - a_4) \big ({\mathbb D}_{1i} {\mathbb D}_{2j} + {\mathbb D}_{2i} {\mathbb D}_{1j}\big ) + s_{ij} + y_{ij} = -{\mathbb W}_{ij}^{(0)}. \end{aligned}$$

(10)

This transformation gives equivalent equations only if $y_{ij} = 0$. To find such non-negative solution, we consider an auxiliary optimization problem:

$$ \max \limits _{a_i,\, s_{ij},\, s_i,\, y_{ij} \ge 0} \varPsi , \;\; \varPsi = -\sum \limits _{i < j} y_{ij} $$

subject to constraints (9) and (10). The maximum of this functional on a set of non-negative solutions is obviously zero. For this auxiliary functional it is easy to find a valid initial guess by setting $a_i = s_{ij} = 0$ and calculating $y_{ij}$, $s_i$ from (9) and (10). If the auxiliary problem does not have a solution, the original problem has no valid initial guess and an M-matrix ${\mathbb W}$ does not exist.

Remark 1

In a computer program, the artificial variables $y_{ij}$ have to be introduced only when ${\mathbb W}^{(0)}_{ij} > 0$.

The simplex method performs linear operations on the set of linear constraints (9), (10) plus the linear objective functional (first $\varPsi$, then $\varPhi$) using certain rules [6]. Each transformation does not decrease the value of the objective functional.

Various generalizations. The simplex method can be also applied to the nodal mimetic schemes [8, Chap. 6], In the case of parabolic equations, positive terms from a time discretization relax the positive definiteness conditions of type (9) which leads to a larger feasible set. Additional computational efficiency can be achieved by combining the simplex method with the primal-dual interior point method [6].

4 Numerical Analysis

In the numerical experiments we used the algorithm simplx from [7] with a few modifications that happened to be critical for meshes with flat cells typically used in porous media applications. Specifically, we changed the pivot rule and enforced stability with respect to round-off errors. We verified that the proposed algorithm returns diagonal mass matrix ${\mathbb W}_\mathrm{c}$ for a Voronoi cell and a scalar diffusion tensor.

For time-dependent simulations that require to generate matrices ${\mathbb W}_\mathrm{c}$ on each time step, complexity of the numerical scheme cannot be ignored. In our experiments with large physics codes, the simplex method has been reaching an optimal solution in something between $n_\mathrm{c}^2 / 2$ and $n_\mathrm{c}^2$ pivot steps. We have not yet met the worst-case scenario shown in Fig. 1.

We illustrate complexity of the simplex method with two experiments. In the first experiment, we take the unit square and the shape-regular pentagon with diameter $2.51$ shown in Fig. 2 and change randomly positions of their vertices. This simulates a mechanical deformation of porous media, e.g. due to a land subsidence. The perturbation changes each vertex coordinate by $0.2\xi$ where $-1 \le \xi \le 1$ is a random function. In the second experiment, we fix the shape of cells shown in Fig. 2, plus the unit square, and rotate gradually the anisotropic diffusion tensor ${\mathbb K}_\mathrm{c}= \mathrm{diag}\{1,3\}$ in 2D and ${\mathbb K}_\mathrm{c}= \mathrm{diag}\{1,2,3\}$ in 3D about the z-axis. This simulates a change of dispersion tensor, e.g. due to pumping in or out of a subsurface reservoir.

In both experiments, the CPU times are averaged over 1000 different realizations. The results presented in Table 1 show that the calculation of an M-matrix ${\mathbb W}_\mathrm{c}$ is 3–6 times more expensive than the calculation based on the original formula ${\mathbb W}_\mathrm{c}^{(1)} = \alpha _\mathrm{c}{\mathbb D}_\mathrm{c}{\mathbb D}_\mathrm{c}^T$. On the other hand, the optimal M-matrix contains on average 40 % zero entries which has a few interesting implications for multigrid solvers. The performance of the multigrid solvers is near-optimal for M-matrices and our preliminary experiments indicate reduction of the cost of one V-cycle which offsets a bit the higher complexity of the proposed mimetic scheme.

Due to page limitation, experiments showing advantage of the simplex method in modeling dispersive transport in porous media will be presented at the conference.

Table 1 Complexity of a single matrix generation in microseconds for random perturbation (columns 2 and 3) and tensor rotation (columns 4 and 5)

Fig. 1

The worst-case scenario. The set of feasible solutions forms a Klee Minty cube. The Dantzig’s simplex method initialized at a vertex of this cube passes through all its vertices making exponentially many pivot steps

Fig. 2

The cells used in the numerical experiments: pentagon and hexahedron with planar faces