Ordinal number | EPFL Graph Search

In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, nth, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the least natural number that has not been previously used. To extend this process to various infinite sets, ordinal numbers are defined more generally as linearly ordered labels that include the natural numbers and have the property that every set of ordinals has a least element (this is needed for giving a meaning to "the least unused element"). This more general definition allows us to define an ordinal number \omega (omega) that is greater than every natural number, along with ordinal numbers \omega + 1, \omega + 2, etc., which are even greater than \omega. A linear order such that every non-empty subset has a least element is called a well-order. The axiom of choice implies that every

Numerical Approximation of Flows in Random Porous Media

Francesco Tesei

The objective of this thesis is to develop efficient numerical schemes to successfully tackle problems arising from the study of groundwater flows in a porous saturated medium; we deal therefore with partial differential equations(PDE) having random coefficients and we are interested in computing statistics related to specific quantities of interest (QoI), e.g. a linear functional of the solution of the PDE or the solution itself. We mainly consider the approximation of the pressure in the medium through a stochastic Darcy problem with random lognormally distributed permeability relying on Matérn-type covariance functions to take into account a wide range of possible smoothness of the permeability field. Once the problem has been reformulated in terms of a countable number of random variables, we analyze sparse grid polynomial approximations of the QoI. We propose different strategies to exploit the anisotropicity of the QoI with respect to the different random entries; to this end we consider a priori'' and a posteriori'' strategies to drive the exploration of the multi-index set that defines the sparse grid, associating a profit to each multi-index either by using explicit theoretical estimates or by actually solving the PDE and computing on the fly the corresponding sparse grid interpolant. We show on several numerical examples the effectiveness of this strategy in treating the case of smooth permeability fields. In order to cover also the case of rough input permeabilities we consider, instead, Multi Level Monte Carlo techniques based on the use of a suitable control variate. Such a control variate is obtained from the solution of an auxiliary Darcy problem with a regularized input permeability which leads to pressure distributions that are smoother and less oscillatory than the original ones, but still highly correlated with them. We use then a sparse grid approximation to compute effectively the mean of the control variate and provide explicit bounds for the corresponding estimator as well as a complexity result. We also consider groundwater transport problems and focus, in particular, on arrival times properly defined starting from particle trajectories driven by the stochastic Darcy velocity and subject to molecular diffusion taking place at porous level. In this case, by using suitable PDEs whose solution can be linked to specific expectations (with respect to all Brownian motions) thanks to the famous Feynman-Kac formula, we compute statistics of such arrival times, e.g. their expected value or the probability of exiting the physical domain in a given time horizon. We discuss several scenarios and readapt the methodologies previously developed involving adaptive sparse grid stochastic collocation and Monte Carlo type schemes to this case.

EPFL2016

Error-correcting multi-stage code generator and decoder for communication systems having single transmitters or multiple transmitters

Mohammad Amin Shokrollahi

A communications system includes an encoder that produces a plurality of redundant symbols. For a given key, an output symbol is generated from a combined set of symbols including the input symbols and the redundant symbols. The output symbols are generally independent of each other, and an effectively unbounded number of output symbols can be generated, if needed. Received output symbols can provide probabilistic information for error correction. A decoder calculates check symbols from the output symbols received. For each received output symbol, the decoder updates a running total of estimated information content and, in one or more rounds, generates a probability distribution for each input symbol over all or some of possible values. This process may be repeated until, for all of the input symbols, one of the many possible values is much more probable than others, or the process may be repeated a predetermined number of rounds, or other criteria is met.

2014

Numerical Approximation of Flows in Random Porous Media

Francesco Tesei

EPFL2016