Déterminisme | EPFL Graph Search

Le déterminisme est une théorie philosophique selon laquelle chaque événement, en vertu du principe de causalité, est déterminé par les événements passés conformément aux lois de la nature. En physique, cette idée se traduit par la notion de système déterministe, c'est-à-dire un système soumis à une dynamique qui associe à chaque condition initiale un et un seul état final. On parle également de système déterministe en automatique pour désigner un système pour lequel les mêmes entrées produisent toujours exactement les mêmes sorties, par opposition à un système stochastique pour lequel les mêmes entrées peuvent produire différentes sorties. vignette|William Blake, Newton (1795). Le mathématicien, astronome et physicien français Pierre-Simon de Laplace a formulé l'hypothèse d'un déterminisme universel en vertu duquel les lois de la physique faisaient que, pour un état donné de l'univers, une seule évolution de celui-ci était possible et que celle-ci était, du moins en théorie, prédi

Probabilistic and Bayesian methods for uncertainty quantification of deterministic and stochastic differential equations

Giacomo Garegnani

In this thesis we explore uncertainty quantification of forward and inverse problems involving differential equations. Differential equations are widely employed for modeling natural and social phenomena, with applications in engineering, chemistry, meteorology, and economics. Mathematical models of complex systems in these fields require numerical methods, which introduce uncertainties in the outcome. Moreover, there has recently been a steep rise in the availability of data, which also come with an uncertainty. Therefore, blending mathematical models, data, and their respective uncertainties is nowadays of the utmost importance. The first part of this thesis is dedicated to two novel methods for multiscale inverse problems. We first consider an elliptic partial differential equation (PDE), with a diffusion tensor oscillating at a small scale. Given noisy observations of the solution, we consider the problem of inferring a slow-scale parametrization of the multiscale tensor. For this purpose, we combine numerical homogenization, which yields a single-scale surrogate of the full model, and the ensemble Kalman filter. The scheme we propose is accurate in the homogenized limit, and outperforms existing methods in terms of computational cost. We then study the error due to the mismatch between the full and the homogenized models, and show how to combine statistical techniques for model misspecification and our scheme. We then move to multiscale diffusion processes, and consider the problem of inferring effective dynamics from multiscale observations. A homogenized single-scale equation reproducing the full model exists also in this case. The effective model, though, is the subject of the inference procedure, and not only a computational tool. The resulting issue of model misspecification is usually bypassed by subsampling at an appropriate rate, which is non-trivial to choose, and which may give misleading results. We avoid subsampling by designing a novel technique based on filtered data, and show how to modify classical estimators and obtain an effective equation consistently with homogenization. Our technique is robust and can be employed as a black-box tool for inferring effective surrogates of complex stochastic models.In the second part we present two novel schemes belonging to the field of probabilistic numerics, whose purpose is to provide a statistical description of the uncertainty due to numerical discretization. We first consider ordinary differential equations (ODEs), and introduce a probabilistic integrator based on random time steps and Runge-Kutta methods (RTS-RK). Tuning the distribution of the time steps, we generate a probability measure on the solution which allows for a consistent uncertainty quantification of numerical errors. Unlike previous probabilistic methods in literature, our scheme inherits the geometric properties of the underlying deterministic integrators. In particular, we show long-time energy conservation when the RTS-RK is applied to Hamiltonian ODEs. We employ the idea of randomizing the discretization to propose a random mesh finite element method (RM-FEM) for elliptic PDEs. We prove that the measure induced by the RM-FEM on the solution can be employed to derive a posteriori error estimators. Hence, the RM-FEM provides a consistent statistical characterization of numerical errors. For both our novel schemes, we demonstrate the usefulness of the probabilistic approach in Bayesian inverse problems.

EPFL2021

Performance prediction and race detection in message-passing parallel applications

Basile Schäli

The combination of low cost clusters and multicore processors lowers the barrier for accessing massive amounts of computing power. As computational sciences advance, the use of in silico simulations to complement in vivo experiments promises parallel programming a bright future in multiple scientific fields. It is therefore increasingly important to develop tools helping developers to write efficient and bug-free parallel applications. This thesis focuses on performance prediction and advanced testing tools for distributed memory message-passing parallel applications. The tools have been implemented within the Dynamic Parallel Schedules (DPS) parallelization framework. They have also been partly adapted to applications written using the Message Passing Interface (MPI) standard. The first part presents a parallel application simulator which has been integrated into the DPS framework. We identified a small set of processing and networking parameters that characterize the hardware platform on which the application is running. After parameterizing the hardware platform, the running time of parallel applications can be predicted using direct execution without requiring any change to the application source code. We propose a partial direct execution technique that reduces the execution time and memory consumption of the simulation. Using partial direct execution, the simulation is no longer tied to the platform to be simulated. Simulations may thus run on a desktop computer rather than on the target parallel machine. The proposed parameterization of the application and of the hardware properties enable using the simulator to study the sensitivity of a parallel application to various operating conditions such as the data subdivision granularity, the adopted parallelization strategy and the underlying hardware platform properties. The proposed simulator helps developers identifying the factors having the largest impact on their application's performance, and determining the most suitable cluster hardware configuration. Speed should not come at the expense of correctness. Since improving parallelization efficiency often requires loosening synchronizations or implementing more complex communication patterns, developers need to ensure that their changes do not introduce potential message races or deadlocks. Deadlocks and message races are common sources of problems in parallel applications and stem from the fact that the delivery of messages from different sources is not deterministically ordered. This non-determinism makes such synchronization errors hard to reproduce and debug. The second part of the thesis presents methods for uncovering potential deadlocks and message races by taking advantage of the flow graph structures and checkpointing capabilities of DPS. We developed a debugger for DPS applications that displays an instantaneous graphical view of the global computation state and is able to control the ordering of message delivery in order to explicitly test specific orderings. The number of possible orderings explodes when the number of messages sent by the application increases. Manual testing can only cover a tiny fraction of possible executions. Therefore, we use the simulator's ability to control the execution of a parallel application, in order to automatically detect deadlocks and message races. A first method for reducing the number of orderings to be tested relies on a partial-order reduction of the search space and on the decomposition of the application execution into independently testable subparts. This method relies on a static analysis of an execution trace of the application, and can therefore only be applied to parallel applications that produce a fixed set of messages, i.e. applications producing the same messages for all delivery orderings. In order to overcome this limitation, we propose an approach relying on the dynamic construction of a state graph expressing possible executions. Both methods reduce the testing costs by several orders of magnitude, and can be combined to further improve the results. Nevertheless, testing durations may remain prohibitive for longer running applications. We therefore also define algorithms generating subsets of possible orderings that are likely to reveal erroneous executions. In the recent years, the MPI standard has emerged as the de facto standard for writing message-passing parallel applications. The final part of this thesis therefore focuses on adapting the aforementioned parallel application testing concepts to MPI applications. We first describe the extension of our work on visualizing the execution of parallel applications. We then discuss the limits and the benefits of using partial-order execution graphs to describe MPI application executions, and show that our dynamic message-passing state graph construction approach can be successfully applied.

EPFL2009

GAPPARD: a computationally efficient method of approximating gap-scale disturbance in vegetation models

Jed Oliver Kaplan

Models of vegetation dynamics that are designed for application at spatial scales larger than individual forest gaps suffer from several limitations. Typically, either a population average approximation is used that results in unrealistic tree allometry and forest stand structure, or models have a high computational demand because they need to simulate both a series of age-based cohorts and a number of replicate patches to account for stochastic gap-scale disturbances. The detail required by the latter method increases the number of calculations by two to three orders of magnitude compared to the less realistic population average approach. In an effort to increase the efficiency of dynamic vegetation models without sacrificing realism, we developed a new method for simulating stand-replacing disturbances that is both accurate and faster than approaches that use replicate patches. The GAPPARD (approximating GAP model results with a Probabilistic Approach to account for stand Replacing Disturbances) method works by postprocessing the output of deterministic, undisturbed simulations of a cohort-based vegetation model by deriving the distribution of patch ages at any point in time on the basis of a disturbance probability. With this distribution, the expected value of any output variable can be calculated from the output values of the deterministic undisturbed run at the time corresponding to the patch age. To account for temporal changes in model forcing (e. g., as a result of climate change), GAPPARD performs a series of deterministic simulations and interpolates between the results in the postprocessing step. We integrated the GAPPARD method in the vegetation model LPJ-GUESS, and evaluated it in a series of simulations along an altitudinal transect of an inner-Alpine valley. We obtained results very similar to the output of the original LPJ-GUESS model that uses 100 replicate patches, but simulation time was reduced by approximately the factor 10. Our new method is therefore highly suited for rapidly approximating LPJ-GUESS results, and provides the opportunity for future studies over large spatial domains, allows easier parameterization of tree species, faster identification of areas of interesting simulation results, and comparisons with large-scale datasets and results of other forest models.

Copernicus Gesellschaft Mbh2013