MATHICSE Technical Report : Fast solvers for 2D fractional differential equations using rank structured matrices

We consider the discretization of time-space diffusion equations with fractional derivatives in space and either 1D or 2D spatial domains. The use of implicit Euler scheme in time and finite differences or finite elements in space, leads to a sequence of dense large scale linear systems describing the behavior of the solution over a time interval. We prove that the coefficient matrices arising in the 1D context are rank structured and can be efficiently represented using hierarchical formats (H-matrices, HODLR). Quantitative estimates for the rank of the off-diagonal blocks of these matrices are presented. We analyze the use of HODLR arithmetic for solving the 1D case and we compare this strategy with existing methods that exploit the Toeplitz-like structure to precondition the GMRES iteration. The numerical tests demonstrate the convenience of the HODLR format when at least a reasonably low number of time steps is needed. Finally, we explain how these properties can be leveraged to design fast solvers for problems with 2D spatial domains that can be reformulated as matrix equations. The experiments show that the approach based on the

Finite elements in space and time for the analysis of generalised visco-elastic materials

Cyrille Dunant, Alain Benjamin Giorla, Karen Scrivener

Numerical analysis of linear visco-elastic materials requires robust and stable methods to integrate partial differential equations in both space and time. In this paper, symmetric space-time finite element operators are derived for the first time for elementary linear elastic spring and linear viscous dashpot. These can thereafter be assembled in parallel and in series to simulate an arbitrarily complex linear visco-elastic behaviour. The flexibility of the proposed method allows the formulation of the behaviour, which closely reflects physical processes. An efficient algorithm is proposed to use the generated elementary matrices in a way that is comparable with finite difference schemes, in terms of both processor and memory costs. This unconditionally stable and convergent procedure is equally valid for space domains in which geometry or material properties evolve with time. Copyright (c) 2013 John Wiley & Sons, Ltd.

Wiley-Blackwell2014

Numerical homogenization methods for advection-diffusion and nonlinear monotone problems with multiple scales

Martin Ernst Huber

Many applied problems, like transport processes in porous media or ferromagnetism in composite materials, can be modeled by partial differential equations (PDEs) with heterogeneous coefficients that rapidly vary at small scales. To capture the effective behavior at a scale of interest, standard numerical methods like the finite element method (FEM) however need to resolve the finest scale of the problem (scale resolution) and thus are prohibitively costly. Numerical homogenization methods based on effective models are an efficient alternative as they require scale resolution only in a small portion of the computational domain. In this thesis, we introduce numerical homogenization methods developed in the framework of heterogeneous multiscale methods (HMM) for two different classes of multiscale PDEs. In the first part, we consider linear parabolic advection-diffusion problems with highly oscillating data, large Péclet number and compressible velocity fields. We use a discontinuous Galerkin finite element method (DG-FEM) for the spatial discretization of an effective equation whose data is estimated from finite element simulations in microscopic domains. The numerical upscaling strategy appropriately models the effects of the highly oscillating velocity field on the effective diffusion (enhanced or depleted diffusion). Thanks to the favorable stability properties of DG-FEM, robust a priori error estimates with explicit convergence rates for the macro and micro spatial discretization errors can be shown. In the second part, we propose numerical homogenization methods for nonlinear monotone multiscale problems. For parabolic problems, we first combine the backward Euler method in time with a finite element heterogeneous multiscale method (FE-HMM) in space, which couples macro and micro FEMs. We prove convergence of the method in the general

L^p(W^{1,p})

setting and provide fully discrete space-time a priori error estimates for

p=2

. The upscaling procedure however is based on nonlinear micro sampling problems, which can be computationally expensive. As a remedy, we propose a linearized method, which is only based on linear micro problems and is much more efficient as it avoids Newton iterations. We prove stability and optimal convergence rates of the linearized scheme in the classical

L^2(H^1)

setting. Further, for elliptic problems, we extend the FE-HMM (based on nonlinear micro problems) to high order macro and micro FEMs and present fully discrete a priori error estimates.

EPFL2015

A posteriori error estimation for partial differential equations with random input data

Diane Sylvie Guignard

This thesis is devoted to the derivation of error estimates for partial differential equations with random input data, with a focus on a posteriori error estimates which are the basis for adaptive strategies. Such procedures aim at obtaining an approximation of the solution with a given precision while minimizing the computational costs. If several sources of error come into play, it is then necessary to balance them to avoid unnecessary work. We are first interested in problems that contain small uncertainties approximated by finite elements. The use of perturbation techniques is appropriate in this setting since only few terms in the power series expansion of the exact random solution with respect to a parameter characterizing the amount of randomness in the problem are required to obtain an accurate approximation. The goal is then to perform an error analysis for the finite element approximation of the expansion up to a certain order. First, an elliptic model problem with random diffusion coefficient with affine dependence on a vector of independent random variables is studied. We give both a priori and a posteriori error estimates for the first term in the expansion for various norms of the error. The results are then extended to higher order approximations and to other sources of uncertainty, such as boundary conditions or forcing term. Next, the analysis of nonlinear problems in random domains is proposed, considering the one-dimensional viscous Burgers' equation and the more involved incompressible steady-state Navier-Stokes equations. The domain mapping method is used to transform the equations in random domains into equations in a fixed reference domain with random coefficients. We give conditions on the mapping and the input data under which we can prove the well-posedness of the problems and give a posteriori error estimates for the finite element approximation of the first term in the expansion. Finally, we consider the heat equation with random Robin boundary conditions. For this parabolic problem, the time discretization brings an additional source of error that is accounted for in the error analysis. The second part of this work consists in the analysis of a random elliptic diffusion problem that is approximated in the physical space by the finite element method and in the stochastic space by the stochastic collocation method on a sparse grid. Considering a random diffusion coefficient with affine dependence on a vector of independent random variables, we derive a residual-based a posteriori error estimate that controls the two sources of error. The stochastic error estimator is then used to drive an adaptive sparse grid algorithm which aims at alleviating the so-called curse of dimensionality inherent to tensor grids. Several numerical examples are given to illustrate the performance of the adaptive procedure.

EPFL2016