The ALPS project release 2.0: open source software for strongly correlated systems

We present release 2.0 of the ALPS (Algorithms and Libraries for Physics Simulations) project, an open source software project to develop libraries and application programs for the simulation of strongly correlated quantum lattice models such as quantum magnets, lattice bosons, and strongly correlated fermion systems. The code development is centered on common XML and HDF5 data formats, libraries to simplify and speed up code development, common evaluation and plotting tools, and simulation programs. The programs enable non-experts to start carrying out serial or parallel numerical simulations by providing basic implementations of the important algorithms for quantum lattice models: classical and quantum Monte Carlo (QMC) using non-local updates, extended ensemble simulations, exact and full diagonalization (ED), the density matrix renormalization group (DMRG) both in a static version and a dynamic time-evolving block decimation (TEBD) code, and quantum Monte Carlo solvers for dynamical mean field theory (DMFT). The ALPS libraries provide a powerful framework for programmers to develop their own applications, which, for instance, greatly simplify the steps of porting a serial code onto a parallel, distributed memory machine. Major changes in release 2.0 include the use of HDF5 for binary data, evaluation tools in Python, support for the Windows operating system, the use of CMake as build system and binary installation packages for Mac OS X and Windows, and integration with the VisTrails workflow provenance tool. The software is available from our web server at http://alps.comp-phys.org/.

New algorithmic methods for real-time transportation problems

Frank Crittin

Two of the most basic problems encountered in numerical optimization are least-squares problems and systems of nonlinear equations. The use of more and more complex simulation tools on high performance computers requires solving problems involving an increasingly large number of variables. The main thrust of this thesis the design of new algorithmic methods for solving large-scale instances of these two problems. Although they are relevant in many different applications, we concentrate specifically on real applications encountered in the context of Intelligent Transportation Systems to illustrate their performances. First we propose a new approach for the estimation and prediction of OriginDestination tables. This problem is usually solved using a Kalman filter approach, which refers to both formulation and resolution algorithm. We prefer to consider a explicit least-squares formulation. It offers convenient and flexible algorithms especially designed to solve largescale problems. Numerical results provide evidence that this approach requires significantly less computation effort than the Kalman filter algorithm. Moreover it allows to consider larger problems, likely to occur in real applications. Second a new class of quasi-Newton methods for solving systems of nonlinear equations is presented. The main idea is to generalize classical methods by building a model using more than two previous iterates. We use a least-squares approach to calibrate this model, as exact interpolation requires a fixed number of iterates, and may be numerically problematic. Based on classical assumptions we give a proof of local convergence of this class of methods. Computational comparisons with standard quasi-Newton methods highlight substantial improvements in terms of robustness and number of function evaluations. We derive from this class of methods a matrix-free algorithm designed to solve large-scale systems of nonlinear equations without assuming any particular structure on the problems. We have successfully tried out the method on problems with up to one million variables. Computational experiments on standard problems show that this algorithm outperforms classical large-scale quasi-Newton methods in terms of efficiency and robustness. Moreover, its numerical performances are similar to Newton-Krylov methods, currently considered as the best to solve large-scale systems of equations. In addition, we provide numerical evidence of the superiority of our method for solving noisy systems of nonlinear equations. This method is then applied to the consistent anticipatory route guidance generation. Route guidance refers to information provided to travelers in an attempt to facilitate their decisions relative to departure time, travel mode and route. We are specifically interested in consistent anticipatory route guidance, in which real-time traffic measurements are used to make short-term predictions, involving complex simulation tools, of future traffic conditions. These predictions are the basis of the guidance information that is provided to users. By consistent, we mean that the anticipated traffic conditions used to generate the guidance must be similar to the traffic conditions that the travelers are going to experience on the network. The problem is tricky because, contrarily to weather forecast where the real system under consideration is not affected by information provision, the very fact of providing travel information may modify the future traffic conditions and, therefore, invalidate the prediction that has been used to generate it. Bottom (2000) has proposed a general fixed point formulation of this problem with the following characteristics. First, as guidance generation involves considerable amounts of computation, this fixed point problem must be solved quickly and accurately enough for the results to be timely and of use to drivers. Secondly the unavailability of a closed-form objective function and the presence of noise due to the use of simulation tools prevent from using classical algorithms. A number of simulation experiments based on two system software including DynaMIT a state-of-the-art, real-time computer system for traffic estimation and prediction, developed at the Intelligent Transportation Systems Program of the Massachusetts Institute of Technology (MIT), have been run. These numerical results underline the good behavior of our large-scale method compared to classical fixed point methods for solving the consistent anticipatory route guidance problem. We close with some comments about future promising directions of research.

EPFL2004

Maximisation numérique et mesures acoustiques des précipitations

Knowledge of extreme precipitation phenomena is of crucial importance to the safety of civil engineering works and for electricity production management in a country of lakes and mountains like Switzerland. In order to study the distribution in space and the evolution of strong rain episodes, the work presented here relies on the complementary approaches of field observation and numerical simulation. The experimental portion of this project relies on a novel, acousticbased, rain metrology instrument. Based on the results, a methodology for the determination of raindrop size distribution (disdrometer facility) and rainfall rate (rain gauge facility) has been developed and is described in the present dissertation. In addition, numerical modelling and simulation methods were developed with the aim of calculating — for a given watershed topography — the Probable Maximum Precipitation (PMP). The method relies on the separation of the different phenomenological contributions and on the climatic characterization of atmospheric situations leading to extreme rain events. Boundary and initial conditions are represented by theoretical profiles of the wind speed, wind direction, temperature, and water contents, turbulent energy and dissipation rate variables. The numerical model calculates the consequent wind and rain fields within the simulation domain for the desired atmospheric situation. The hydrodynamic code (CFX4) is based on the finite volume approach and is particularly adapted to complex geometries, allowing an excellent representation of the topography. The code is partially open and several specific atmospheric models were implemented. Microphysics schemes considered are Kessler's warm classic scheme (1969) and the Caniaux detailed scheme (1993). The latter includes solid ice particles, aggregates and graupel and allows the simulation of convective as well as orographic cloud system precipitation cycles. Sensitivity studies of the results with respect to the dominant parameters of each situation, lead to a maximisation procedure successfully applied to convective as well as frontal precipitation. The work shows that the maximisation method consisting of maximising severe events into critical events can be more effective than using statistical approaches. Use of this method compensates for the relative lack of measurement facilities in many regions.

EPFL2004

Object-oriented approach for dynamic system modelling and simulation

Adel Besrour

Software engineering always cares to provide solutions for building applications as close as possible to what they should be, according to the requirements and the final users needs. Systems behavior simulation is a very common application to virtually reproduce and often predict the real-world behavior. Simulation is one of the most operational research tool in a large variety of engineering and scientific domains: Transport, telecommunication, medicine, chemical processes, physics, etc. The complexity of such application is relative to the increasing complexity of the systems. In this context, it is relevant to bring together different tools and formalisms such as markovian chain, Petri nets, etc., to improve the existent approaches and so to answer the simulations performances needs. The principle objective of this thesis is to bring together techniques from software engineering and safety engineering in order to improve the state of the art of modeling and simulation of dynamic systems in the industrial context. In addressing this objective, this work initially involves defining the essential limitations of the used formalisms, methods and tools regarding from one hand the software engineering modeling and simulation techniques and from the other hand the existent risk analysis methodologies. This work is conducted with respect to the problem of danger identification, considering the context of the complex systems behavior and their interaction with the human operator. In software engineering, it is well known that Petri/high-level nets have attractive characteristics to be used in systems simulation and behavior prediction such as the natural graphical representation, and their well-defined semantic. They are well-suited for the description of complex situations with concurrency (interleaving and true concurrency depending on the underlying semantics), conflict and confusion. However, the absence of structuring capabilities has been one of the main criticisms raised against Petri nets/high-level nets. Thus, there have been many attempts to introduce structuring principles in nets of this kind [BCM88] [Kie89] [JR91]. The attractive characteristics of Petri/high-level nets have prompted researchers to enrich these formalisms with object-oriented features. CO-OPN (Concurrent Object-Oriented Petri Net) approach, brings together the power of both Petri/high-level nets and object-orientation techniques, it has been devised so as to offer an adequate framework for the specification and design of large scale concurrent system [BG91]. CO-OPN, as a powerful modeling tool, has been used in a limited way to simulate systems. This work aims to provide a CO-OPN extension to allow a more realistic systems' simulation. Actually, its simulator semantic uses to be a suitable approach for modeling near closed systems and software components, because they need to loose coupling with external world. But, when we model more realistic problems like industrial processes, where human interaction is a relevant event, this approach is not sufficient to catch all system activity attributes. Moreover, the CO-OPN interpretation process does not allow interaction with the object internal states. This work provides a new solution to overcome CO-OPN simulation limitations and a set of prototypes to assist dynamic systems simulations. Furthermore, this work has been conducted in a Risk Analysis (RA) context, a domain where computer-based simulations research are of utmost interest. Actually, classical approaches used to address complex workplace hazard in a limited way, using checklists or sequence models. Moreover, the use of single oriented methods, such as AEA (man-oriented), FMEA (machine oriented) or HAZOP (process oriented), is not satisfactory to overcome the increasing sophistication of industrial processes. The automation of a part of the analysis process as well as the multiple-oriented approach allowed by dynamic modeling may indeed enhance significantly the analysis completeness and reduce the time analyzing time. This work, based on Object Oriented Petri net formalism (CO-OPN), propose an alternative multi-oriented approach where existent methods limitations have been criticized to develop a dynamic model, MORM (Man-machine Occupational Risk Modeling). A real industrial system (metal wire making process) has been specified to implement the different approach steps (system identification, model application, system simulation, system analysis).

EPFL2005

Maximisation numérique et mesures acoustiques des précipitations

EPFL2004

Object-oriented approach for dynamic system modelling and simulation

Adel Besrour

EPFL2005

New algorithmic methods for real-time transportation problems

Frank Crittin

EPFL2004