Numerical Analysis of Multiscale Computations

Multiscale differential equations arise in the modeling of many important problems in the science and engineering. Numerical solvers for such problems have been extensively studied in the deterministic case. Here, we discuss numerical methods for (mean-square stable) stiff stochastic differential equations. Standard explicit methods, as for example the Euler-Maruyama method, face severe stepsize restriction when applied to stiff problems. Fully implicit methods are usually not appropriate for stochastic problems and semi-implicit methods (implicit in the deterministic part) involve the solution of possibly large linear systems at each time-step. In this paper, we present a recent generalization of explicit stabilized methods, known as Chebyshev methods, to stochastic problems. These methods have much better (mean-square) stability properties than standard explicit methods. We discuss the construction of this new class of methods and illustrate their performance on various problems involving stochastic ordinary and partial differential equations.

We study a few interesting issues that occur in multiscale modeling and computation for oscillatory dynamical systems that involve three or more separated scales. A new type of slow variables which do not formally have bounded derivatives emerge from averaging in the fastest time scale. We present a few systems which have such new slow variables and discuss their characterization. The examples motivate a numerical multiscale algorithm that uses nested tiers of integrators which numerically solve the oscillatory system on different time scales. The communication between the scales follows the framework of the Heterogeneous Multiscale Method. The method’s accuracy and efficiency are evaluated and its applicability is demonstrated by examples.

This work is a follow up to previous articles of the same authors (Costaouec, Le Bris, and Legoll, Boletin Soc. Esp. Mat. Apl. 50:9–27, 2010; Blanc, Costaouec, Le Bris, and Legoll, Markov Processes and Related Fields, in press). It has been shown there, both numerically and theoretically, that the technique of antithetic variables successfully applies to stochastic homogenization of divergence-form linear elliptic problems and allows to reduce variance in computations. In (Costaouec, Le Bris, and Legoll, Boletin Soc. Esp. Mat. Apl. 50:9–27, 2010), variance reduction was assessed numerically for the diagonal terms of the homogenized matrix, in the case when the random field, that models uncertainty on some physical property at microscale, has a simple form. The numerical experiments have been complemented in Blanc, Costaouec, Le Bris, and Legoll (Markov Processes and Related Fields, in press) by a theoretical study. The main objective of this work is to proceed with some numerical experiments in a broader set of cases. We show the efficiency of the approach in each of the settings considered.

We suggest a method for the integration of highly oscillatory systems with a single high frequency. The new method may be seen as a purely numerical way of implementing the analytical technique of stroboscopic averaging. The technique may be easily implemented in combination with standard software and may be applied with variable step sizes. Numerical experiments show that the suggested algorithms may be substantially more efficient than standard numerical integrators.

The purpose of this paper is to provide a mathematical analysis of the Adler-Wiser formula relating the macroscopic relative permittivity tensor to the microscopic structure of the crystal at the atomic level. The technical level of the presentation is kept at its minimum to emphasize the mathematical structure of the results. We also briefly review some models describing the electronic structure of finite systems, focusing on density operator based formulations, as well as the Hartree model for perfect crystals or crystals with a defect.

The fast multipole method (FMM) is a technique allowing the fast calculation of long-range interactions between N points in O(N) or O(NlnN) steps with some prescribed error tolerance. The FMM has found many applications in the field of integral equations and boundary element methods, in particular by accelerating the solution of dense linear systems arising from such formulations. Standard FMMs are derived from analytic expansions of the kernel, for example using spherical harmonics or Taylor expansions. In recent years, the range of applicability and the ease of use of FMMs has been extended by the introduction of black box (Fong and Darve, Journal of Computational Physics 228:8712–8725, 2009) or kernel independent techniques (Ying, Biros and Zorin, Journal of Computational Physics 196:591–626, 2004). In these approaches, the user only provides a subroutine to numerically calculate the interaction kernel. This allows changing the definition of the kernel with minimal change to the computer program. This paper presents a novel kernel independent FMM, which leads to diagonal multipole-to-local operators. This results in a significant reduction in the computational cost (Fong and Darve, Journal of Computational Physics 228:8712–8725, 2009), in particular when high accuracy is needed. The approach is based on Cauchy’s integral formula and the Laplace transform. We will present a short numerical analysis of the convergence and some preliminary numerical results in the case of a single level one dimensional FMM.

This work presents a review of recent tools for multiscale simulations of liquids, ranging from simple Newtonian fluids to polymer melts. Particular attention is given to the problem of imposing the desired macro state into open microscopic systems, allowing for mass, momentum and energy exchanges with the environmental state, usually provided by a continuum fluid dynamics (CFD) solver. This review intends to highlight that most of the different methods developed so far in the literature can be joined together in a general tool, which I call OPEN MD. The development of OPEN MD should be seen as an ongoing research program. A link between the micro and macro methods is the imposition of the external conditions prescribed by the macro-solver at or across the boundaries of a microscopic domain. The common methodology is the use of external particle forces within the so called particle buffer. Under this frame, OPEN MD requires minor modifications to perform state-coupling (i.e. imposing velocity and/or temperature) or flux exchange, or even any clever combination of both. This tool can be used either in molecular or mesoscopic-based research or in CFD based problems, which focus on mean flow effects arising from the underlying molecular nature. In this latter case an important goal is to allow for a general description of Non-Newtonian liquids, involving not only transfer of momentum in incompressible situations, but also mass and energy transfers between the micro and macro models.

Multiscale wave propagation problems are computationally costly to solve by traditional techniques because the smallest scales must be represented over a domain determined by the largest scales of the problem. We have developed and analyzed new numerical methods for multiscale wave propagation in the framework of the heterogeneous multiscale method (HMM). The numerical methods couple simulations on macro- and microscales for problems with rapidly oscillating coefficients. The complexity of the new method is significantly lower than that of traditional techniques with a computational cost that is essentially independent of the smallest scale, when computing solutions at a fixed time and accuracy. We show numerical examples of the HMM applied to long time integration of wave propagation problems in both periodic and non-periodic medium. In both cases our HMM accurately captures the dispersive effects that occur. We also give a stability proof for the HMM, when it is applied to long time wave propagation problems.

The paper describes techniques for constructing simplified models for problems governed by elliptic partial differential equations involving heterogeneous media. Examples of problems under consideration include electro-statics and linear elasticity in composite materials, and flows in porous media. A common approach to such problems is to either up-scale the governing differential equation and then discretize the up-scaled equation, or to construct a discrete problem whose solution approximates the solution to the original problem under some constraints on the permissible loads. In contrast, the current paper suggests that it is in many situations advantageous to directly approximate the solution operatorto the original differential equation. Such an approach has become feasible due to recent advances in numerical analysis, and can in a natural way handle situations that are challenging to existing techniques, such as those involving, e.g.concentrated loads, boundary effects, and irregular micro-structures. The capabilities of the proposed methodology are illustrated by numerical examples involving domains that are loaded on the boundary only, in which case the solution operator is a boundary integral operator such as, e.g., a Neumann-to–Dirichlet operator.

This work generalizes a multilevel forward Euler Monte Carlo method introduced in Michael B. Giles. (Michael Giles. Oper. Res. 56(3):607–617, 2008.) for the approximation of expected values depending on the solution to an Itô stochastic differential equation. The work (Michael Giles. Oper. Res. 56(3):607– 617, 2008.) proposed and analyzed a forward Euler multilevelMonte Carlo method based on a hierarchy of uniform time discretizations and control variates to reduce the computational effort required by a standard, single level, Forward Euler Monte Carlo method. This work introduces an adaptive hierarchy of non uniform time discretizations, generated by an adaptive algorithmintroduced in (AnnaDzougoutov et al. Raùl Tempone. Adaptive Monte Carlo algorithms for stopped diffusion. In Multiscale methods in science and engineering, volume 44 of Lect. Notes Comput. Sci. Eng., pages 59–88. Springer, Berlin, 2005; Kyoung-Sook Moon et al. Stoch. Anal. Appl. 23(3):511–558, 2005; Kyoung-Sook Moon et al. An adaptive algorithm for ordinary, stochastic and partial differential equations. In Recent advances in adaptive computation, volume 383 of Contemp. Math., pages 325–343. Amer. Math. Soc., Providence, RI, 2005.). This form of the adaptive algorithm generates stochastic, path dependent, time steps and is based on a posteriori error expansions first developed in (Anders Szepessy et al. Comm. Pure Appl. Math. 54(10):1169– 1214, 2001). Our numerical results for a stopped diffusion problem, exhibit savings in the computational cost to achieve an accuracy of \( \vartheta{\rm(TOL),\, from\,(TOL^{-3})}\), from using a single level version of the adaptive algorithm to \( \vartheta\left( \begin{array}{lll}\left({(TOL^{-1})\,log(TOL)}\right)^2\end{array}\right).\)

We propose an efficient Markov Chain Monte Carlo method for sampling equilibrium distributions for stochastic lattice models. The method is capable of handling correctly and efficiently long and short-range particle interactions. The proposed method is a Metropolis-type algorithm with the proposal probability transition matrix based on the coarse-grained approximating measures introduced in (Katsoulakis et al. Proc. Natl. Acad. Sci. 100(3):782–787, 2003; Katsoulakis et al. ESAIM-Math. Model. Numer. Anal. 41(3):627–660, 2007). The proposed algorithm reduces the computational cost due to energy differences and has comparable mixing properties with the classical microscopic Metropolis algorithm, controlled by the level of coarsening and reconstruction procedure. The properties and effectiveness of the algorithm are demonstrated with an exactly solvable example of a one dimensional Ising-type model, comparing efficiency of the single spin-flip Metropolis dynamics and the proposed coupled Metropolis algorithm.

A method for calibrating a jump-diffusion model to observed option prices is presented. The calibration problem is formulated as an optimal control problem, with the model parameters as the control variable. It is well known that such problems are ill-posed and need to be regularized. A Hamiltonian system, with non-differentiable Hamiltonian, is obtained from the characteristics of the corresponding Hamilton-Jacobi-Bellman equation. An explicit regularization of the Hamiltonian is suggested, and the regularized Hamiltonian system is solved with a symplectic Euler method. The paper is concluded with some numerical experiments on real and artificial data.

We present recent results on coarse-graining techniques for thermodynamic quantities (canonical averages) and dynamical quantities (averages of path functionals over solutions of overdamped Langevin equations). The question is how to obtain reduced models to compute such quantities, in the specific case when the functional to be averaged only depends on a few degrees of freedom. We mainly review, numerically illustrate and extend results from (Blanc et al. Journal of Nonlinear Science 20(2):241–275, 2010; Legoll and Lelièvre Nonlinearity 23(9):2131–2163, 2010.), concerning the computation of the stress-strain relation for one-dimensional chains of atoms, and the construction of an effective dynamics for a scalar coarse-grained variable when the complete system evolves according to the overdamped Langevin equation.

Force-based multiphysics coupling methods have become popular since they provide a simple and efficient coupling mechanism, avoiding the difficulties in formulating and implementing a consistent coupling energy. They are also the only known pointwise consistent methods for coupling a general atomistic model to a finite element continuum model. However, the development of efficient and reliable iterative solution methods for the force-based approximation presents a challenge due to the non-symmetric and indefinite structure of the linearized force-based quasicontinuum approximation, as well as to its unusual stability properties. In this paper, we present rigorous numerical analysis and computational experiments to systematically study the stability and convergence rate for a variety of linear stationary iterative methods.

A new coupling term for blending particle and continuum models with the Arlequin framework is investigated in this work. The coupling term is based on an integral operator defined on the overlap region that matches the continuum and particle solutions in an average sense. The present exposition is essentially the continuation of a previous work (Bauman et al., On the application of the Arlequin method to the coupling of particle and continuum models, Computational Mechanics, 42, 511–530, 2008) in which coupling was performed in terms of an H ¹-type norm. In that case, it was shown that the solution of the coupled problem was mesh-dependent or, said in another way, that the solution of the continuous coupled problem was not the intended solution. This new formulation is now consistent with the problem of interest and is virtually mesh-independent when considering a particle model consisting of a distribution of heterogeneous bonds. The mathematical properties of the formulation are studied for a one-dimensional model of harmonic springs, with varying stiffness parameters, coupled with a linear elastic bar, whose modulus is determined by classical homogenization. Numerical examples are presented for one-dimensional and two-dimensional model problems that illustrate the approximation properties of the new coupling term and the effect of mesh size.

Approximations of geometric optics type are commonly used in simulations of high frequency wave propagation. This form of technique fails when there is strong local variation in the wave speed on the scale of the wavelength or smaller. We propose a domain decomposition approach, coupling Gaussian beam methods where the wave speed is smooth with finite difference methods for the wave equations in domains with strong wave speed variation. In contrast to the standard domain decomposition algorithms, our finite difference domains follow the energy of the wave and change in time. A typical application in seismology presents a great simulation challenge involving the presence of irregularly located sharp inclusions on top of a smoothly varying background wave speed. These sharp inclusions are small compared to the domain size. Due to the scattering nature of the problem, these small inclusions will have a significant effect on the wave field. We present examples in two dimensions, but extensions to higher dimensions are straightforward.