Efficient sampling avoids the exponential wall in classical simulations of fidelity

We analyze the efficiency of available algorithms for the simulation of classical fidelity and show that their computational costs increase exponentially with the number of degrees of freedom. Then we present an algorithm for which the number of trajectories needed for convergence is independent of the system's dimensionality and show that, within a continuous family of algorithms, this algorithm is the only one with this property. Simultaneously we propose a general analytical approach to estimate efficiency of trajectory-based methods and suggest how to use it to accelerate calculations of other classical correlation functions. Converged numerical results are provided for systems with phase space volume 2(1700) times larger than the volume of the initial state.

Adaptive Finite Element Methods for Multiscale Partial Differential Equations

Achim Nonnenmacher

Engineers rely on efficient simulations that provide them with reliable data in order to make proper engineering design decisions. The purpose of this thesis is to design adaptive numerical methods for multiscale problems in this spirit. We consider elliptic homogenization problems discretized by the finite element heterogeneous multiscale method (FE-HMM). Unlike standard (single-scale) finite element methods, our multiscale discretization scheme relies on coupled macro and micro finite elements. The framework of the HMM allows to design an algorithm that follows the classical finite element structure on the macro level. The fine scales of the multiscale problems are taken into account by replacing the element-wise numerical integration over unknown macroscopic data by a numerical integration over suitably averaged micro solutions. These micro solutions are obtained from micro FE problems on sampling domains within the macro elements. This thesis is divided into two parts. In the first part, we discuss a short and versatile FE implementation of the multiscale algorithm. The implementation is flexible, easy to use and to modify and can handle simplicial or quadrilateral FE and various macro-micro coupling conditions for the constrained micro problems. The implementation of time-dependent problems is also discussed. Numerical examples including three dimensional problems are presented and demonstrate the efficiency and the versatility of the computational strategy. In the second part (the main part of this thesis), we present an a posteriori error analysis for the FE-HMM. The a posteriori analysis enables us to estimate the accuracy of a numerical solution (and therefore its reliability) and further it allows for the design of adaptive numerical methods, which are the most efficient. The crucial component for the design of an adaptive multiscale method is the introduction of appropriate error indicators. As the error indicators depend on macroscopic data (such as the macroscopic diffusion tensor) that are not readily available, we construct error indicators that only depend on the available macro and micro FE solutions, available from previous computations. We provide a posteriori estimates for the upper and lower bound in the energy norm. The corresponding macroscopic mesh refinement strategy is therefore both reliable and efficient. The microscopic mesh is refined simultaneously and – under appropriate assumptions – optimally with the macroscopic mesh. This means that the strategy reduces the macro and micro error at the same rate. In the case of a uniformly oscillating tensor and exact micro computations, the standard a posteriori error estimates for the FEM applied to the homogenized problem are recovered. Numerical experiments confirm the efficiency and reliability of the adaptive multiscale method and demonstrate the optimality of the chosen macro-micro coupling. We extend the adaptive FE-HMM to higher order FE. We further derive a posteriori estimates for the error in quantities of interest that are needed to make certain design decisions; the quantity of interest is represented by a linear functional. We derive and analyze a multiscale counterpart to the classical dual-weighted residual method and design a corresponding goal-oriented adaptive multiscale method. The efficiency of the method is shown in numerical experiments.

EPFL2011

On the Efficiency of Semiclassical and Classical Approximations of Quantum Fidelity in Many-Dimensional Systems

Cesare Mollica

This thesis is focused on classical and semiclassical approximations of a specific quantum time correlation function, the “quantum fidelity.” Namely, we rigorously study the efficiency of a continuous class of algorithms for the evaluation of its classical limit and both the cost and the error of a particular semiclassical approximation of it. In the physics domain, quantum fidelity can be used to study the cross section of inelastic neutron scattering and phenomena like decoherence and irreversibility in NMR experiments. In chemical physics, quantum fidelity can be employed to compute the spectrum of a quantum state, to evaluate the accuracy of quantum dynamics on an approximate potential energy surface, and to verify the importance of nonadiabatic electronic transitions in molecules. Unfortunately, as for any numerical simulation of a quantum dynamical object, many-dimensional calculations of quantum fidelity are extremely expensive computationally. Classical methods, not including any quantum effect, are generally believed to be efficient approximations for the numerical evaluation of large systems’ properties when quantum effects are not important. We prove that, previous to this research, the computational costs of available algorithms for the simulation of classical fidelity increased exponentially with the number of degrees of freedom and we single out, within a continuous family of algorithms, the only one for which the number of trajectories needed for convergence is independent of the system’s dimensionality. Recently a semiclassical method, called “dephasing representation” (DR), has been proposed to approximate quantum fidelity accurately and efficiently. Although semiclassical methods, approximately including all types of quantum effects, are generally more accurate but much less efficient than classical methods, we prove that for the semiclassical DR there exists at least one algorithm for which the number of trajectories needed for convergence is independent of dimensionality and also that this semiclassical algorithm is even faster than the most efficient classical fidelity algorithm previously singled out. Encouraged by the surprising efficiency of the specific semiclassical method, we investigate the error of the DR compared to the quantum benchmark.

EPFL2012

On the Efficiency of Semiclassical and Classical Approximations of Quantum Fidelity in Many-Dimensional Systems

Cesare Mollica

EPFL2012

Adaptive Finite Element Methods for Multiscale Partial Differential Equations

Achim Nonnenmacher

EPFL2011