Reduced basis method and domain decomposition for elliptic problems in networks and complex parametrized geometries

The aim of this work is to solve parametrized partial differential equations in computational domains represented by networks of repetitive geometries by combining reduced basis and domain decomposition techniques. The main idea behind this approach is to compute once, locally and for few reference shapes, some representative finite element solutions for different values of the parameters and with a set of different suitable boundary conditions on the boundaries: these "functions will represent the basis of a reduced space where the global solution is sought for. The continuity of the latter is assured by a classical domain decomposition approach. Test results on Poisson problem show the flexibility of the proposed method in which accuracy and computational time may be tuned by varying the number of reduced basis functions employed, or the set of boundary conditions used for defining locally the basis functions. The proposed approach simplifies the pre-computation of the reduced basis space by splitting the global problem into smaller local subproblems. Thanks to this feature, it allows dealing with arbitrarily complex network and features more flexibility than a classical global reduced basis approximation where the topology of the geometry is fixed. (C) 2015 Elsevier Ltd. All rights reserved.

MATHICSE Technical Report: Reduced basis method and domain decomposition for elliptic problems in networks and complex parametrized geometries

Laura Iapichino, Alfio Quarteroni, Gianluigi Rozza

The aim of this work is to solve parametrized partial differential equations in computational domains represented by networks of repetitive geometries by combining reduced basis and domain decomposition techniques. The main idea behind this approach is to compute once, locally and for few reference shapes, some representative finite element solutions for different values of the parameters and with a set of different suitable boundary conditions on the boundaries: these functions will represent the basis of a reduced space where the global solution is sought for. The continuity of the latter is assured by a classical domain decomposition approach. Test results on Poisson problem show the flexibility of the proposed method in which accuracy and computational time may be tuned by varying the number of reduced basis functions employed, or the set of boundary conditions used for defining locally the basis functions. The proposed approach simplifies the pre-computation of the reduced basis space by splitting the global problem into smaller local subproblems.Thanks to this feature, it allows dealing with arbitrarily complex network and features more flexibility than a classical global reduced basis approximation where the topology of the geometry is fixed.

MATHICSE2015

Hardness of Computing Individual Bits for One-way Functions on Elliptic Curves

Alexandre Raphaël Duc, Dimitar Petkov Jetchev

We prove that if one can predict any of the bits of the input to an elliptic curve based one-way function over a finite field, then we can invert the function. In particular, our result implies that if one can predict any of the bits of the input to a classical pairing-based one-way function with non-negligible advantage over a random guess then one can efficiently invert this function and thus, solve the Fixed Argument Pairing Inversion problem (FAPI-1/FAPI-2). The latter has implications on the security of various pairing-based schemes such as the identity-based encryption scheme of Boneh–Franklin, Hess’ identity-based signature scheme, as well as Joux’s three-party one-round key agreement protocol. Moreover, if one can solve FAPI-1 and FAPI-2 in polynomial time then one can solve the Computational Diffie--Hellman problem (CDH) in polynomial time. Our result implies that all the bits of the functions defined above are hard-to-compute assuming these functions are one-way. The argument is based on a list-decoding technique via discrete Fourier transforms due to Akavia--Goldwasser–Safra as well as an idea due to Boneh–Shparlinski.

Springer2012

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

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

Diane Sylvie Guignard

EPFL2016