An efficient epistemic uncertainty quantification algorithm for a class of stochastic models: A post-processing and domain decomposition framework | 2020

Mahadevan GaneshStuart C HawkinsAlexandre TartakovskyRamakrishna Tipireddy

Partial differential equations (PDEs) are fundamental for theoretically describing numerous physical processes that are based on some input fields in spatial configurations. Understanding the physical process, in general, requires computational modeling of the PDE. Uncertainty in the computational model manifests through lack of precise knowledge of the input field or configuration. Uncertainty quantification (UQ) in the output physical process is typically carried out by modeling the uncertainty using a random field, governed by an appropriate covariance function. This leads to solving high-dimensional stochastic counterparts of the PDE computational models. Such UQ-PDE models require a large number of simulations of the PDE in conjunction with samples in the high-dimensional probability space, with probability distribution associated with the covariance function. Those UQ computational models having explicit knowledge of the covariance function are known as aleatoric UQ (AUQ) models. The lack of such explicit knowledge leads to epistemic UQ (EUQ) models, which typically require solution of a large number of AUQ models. In this article, using a surrogate, post-processing, and domain decomposition framework with coarse stochastic solution adaptation, we develop an offline/online algorithm for efficiently simulating a class of EUQ-PDE models.

Robust linear domain decomposition schemes for reduced non-linear fracture flow models | 2020

Elyes AhmedAlessio FumagalliAna BudišaEirik KeilegavlenJan Martin NordbottenFlorin Adrian Radu

In this work, we consider compressible single-phase flow problems in a porous media containing a fracture. In the latter, a non-linear pressure-velocity relation is prescribed. Using a non-overlapping domain decomposition procedure, we reformulate the global problem into a non-linear interface problem. We then introduce two new algorithms that are able to efficiently handle the non-linearity and the coupling between the fracture and the matrix, both based on linearization by the so-called L-scheme. The first algorithm, named MoLDD, uses the L-scheme to resolve the non-linearity, requiring at each iteration to solve the dimensional coupling via a domain decomposition approach. The second algorithm, called ItLDD, uses a sequential approach in which the dimensional coupling is part of the linearization iterations. For both algorithms, the computations are reduced only to the fracture by pre-computing, in an offline phase, a multiscale flux basis (the linear Robin-to-Neumann co-dimensional map), that represent the flux exchange between the fracture and the matrix. We present extensive theoretical findings and in particular, the stability and the convergence of both schemes are obtained, where user given parameters are optimized to minimise the number of iterations. Examples on two important fracture models are computed with the library PorePy and agree with the developed theory.

Adaptive greedy algorithms based on parameter-domain decomposition and reconstruction for the reduced basis method | 2020

Jiahua JiangYanlai Chen

The reduced basis method (RBM) empowers repeated and rapid evaluation of parametrized partial differential equations through an offline-online decomposition, a.k.a. a learning-execution process. A key feature of the method is a greedy algorithm repeatedly scanning the training set, a fine discretization of the parameter domain, to identify the next dimension of the parameter-induced solution manifold along which we expand the surrogate solution space. Although successfully applied to problems with fairly high parametric dimensions, the challenge is that this scanning cost dominates the offline cost due to it being proportional to the cardinality of the training set which is exponential with respect to the parameter dimension. In this work, we review three recent attempts in effectively delaying this curse of dimensionality, and propose two new hybrid strategies through successive refinement and multilevel maximization of the error estimate over the training set. All five offline-enhanced methods and the original greedy algorithm are tested and compared on {two types of problems: the thermal block problem and the geometrically parameterized Helmholtz problem.

A diagonal sweeping domain decomposition method with source transfer for the Helmholtz equation | 2020

Wei LengLili Ju

In this paper, we propose and test a novel diagonal sweeping domain decomposition method (DDM) with source transfer for solving the high-frequency Helmholtz equation in $\mathbb{R}^n$. In the method the computational domain is partitioned into overlapping checkerboard subdomains for source transfer with the perfectly matched layer (PML) technique, then a set of diagonal sweeps over the subdomains are specially designed to solve the system efficiently. The method improves the additive overlapping DDM (W. Leng and L. Ju, 2019) and the L-sweeps method (M. Taus, et al., 2019) by employing a more efficient subdomain solving order. We show that the method achieves the exact solution of the global PML problem with $2^n$ sweeps in the constant medium case. Although the sweeping usually implies sequential subdomain solves, the number of sequential steps required for each sweep in the method is only proportional to the $n$-th root of the number of subdomains when the domain decomposition is quasi-uniform with respect to all directions, thus it is very suitable for parallel computing of the Helmholtz problem with multiple right-hand sides through the pipeline processing. Extensive numerical experiments in two and three dimensions are presented to demonstrate the effectiveness and efficiency of the proposed method.

A general framework for substructuring-based domain decomposition methods for models having nonlocal interactions | 2020

Giacomo CapodaglioMarta D'EliaMax GunzburgerPavel BochevManuel KlarChristian Vollmann

A rigorous mathematical framework is provided for a substructuring-based domain-decomposition approach for nonlocal problems that feature interactions between points separated by a finite distance. Here, by substructuring it is meant that a traditional geometric configuration for local partial differential equation problems is used in which a computational domain is subdivided into non-overlapping subdomains. In the nonlocal setting, this approach is substructuring-based in the sense that those subdomains interact with neighboring domains over interface regions having finite volume, in contrast to the local PDE setting in which interfaces are lower dimensional manifolds separating abutting subdomains. Key results include the equivalence between the global, single-domain nonlocal problem and its multi-domain reformulation, both at the continuous and discrete levels. These results provide the rigorous foundation necessary for the development of efficient solution strategies for nonlocal domain-decomposition methods.

A global-in-time domain decomposition method for the coupled nonlinear Stokes and Darcy flows | 2020

Thi-Thao-Phuong HoangHyesuk Lee

We study a decoupling iterative algorithm based on domain decomposition for the time-dependent nonlinear Stokes-Darcy model, in which different time steps can be used in the flow region and in the porous medium. The coupled system is formulated as a space-time interface problem based on the interface condition for mass conservation. The nonlinear interface problem is then solved by a nested iteration approach which involves, at each Newton iteration, the solution of a linearized interface problem and, at each Krylov iteration, parallel solution of time-dependent linearized Stokes and Darcy problems. Consequently, local discretizations in time (and in space) can be used to efficiently handle multiphysics systems of coupled equations evolving at different temporal scales. Numerical results with nonconforming time grids are presented to illustrate the performance of the proposed method.

A non-iterative domain decomposition method for the interaction between a fluid and a thick structure | 2020

Anyastassia SeboldtMartina Bukač

This work focuses on the development and analysis of a partitioned numerical method for moving domain, fluid-structure interaction problems. We model the fluid using incompressible Navier-Stokes equations, and the structure using linear elasticity equations. We assume that the structure is thick, i.e., described in the same dimension as the fluid. We propose a non-iterative, domain decomposition method where the fluid and the structure sub-problems are solved separately. The method is based on generalized Robin boundary conditions, which are used in both fluid and structure sub-problems. Using energy estimates, we show that the proposed method applied to a moving domain problem is unconditionally stable. We also analyze the convergence of the method and show $\mathcal{O}(\Delta t^\frac12)$ convergence in time and optimal convergence in space. Numerical examples are used to demonstrate the performance of the method. In particular, we explore the relation between the combination parameter used in the derivation of the generalized Robin boundary conditions and the accuracy of the scheme. We also compare the performance of the method to a monolithic solver.

On condition numbers of symmetric and nonsymmetric domain decomposition methods | 2020

Juan Galvis

Using oblique projections and angles between subspaces we write condition number estimates for abstract nonsymmetric domain decomposition methods. In particular, we consider a restricted additive method for the Poisson equation and write a bound for the condition number of the preconditioned operator. We also obtain the non-negativity of the preconditioned operator. Condition number estimates are not enough for the convergence of iterative methods such as GMRES but these bounds may lead to further understanding of nonsymmetric domain decomposition methods.

Analysis of the Schwarz domain decomposition method for the conductor-like screening continuum model | 2020

Arnold ReuskenBenjamin Stamm

We study the Schwarz overlapping domain decomposition method applied to the Poisson problem on a special family of domains, which by construction consist of a union of a large number of fixed-size subdomains. These domains are motivated by applications in computational chemistry where the subdomains consist of van der Waals balls. As is usual in the theory of domain decomposition methods, the rate of convergence of the Schwarz method is related to a stable subspace decomposition. We derive such a stable decomposition for this family of domains and analyze how the stability "constant" depends on relevant geometric properties of the domain. For this, we introduce new descriptors that are used to formalize the geometry for the family of domains. We show how, for an increasing number of subdomains, the rate of convergence of the Schwarz method depends on specific local geometry descriptors and on one global geometry descriptor. The analysis also naturally provides lower bounds in terms of the descriptors for the smallest eigenvalue of the Laplace eigenvalue problem for this family of domains.

Analysis of the SORAS domain decomposition preconditioner for non-self-adjoint or indefinite problems | 2020

Marcella BonazzoliXavier ClaeysFrédéric NatafPierre-Henri Tournier

We analyze the convergence of the one-level overlapping domain decomposition preconditioner SORAS (Symmetrized Optimized Restricted Additive Schwarz) applied to a general linear system whose matrix is not necessarily symmetric/self-adjoint nor positive definite. By generalizing the theory for the Helmholtz equation developed in [I.G. Graham, E.A. Spence, and J. Zou, preprint arXiv:1806.03731, 2019], we identify a list of assumptions and estimates that are sufficient to obtain an upper bound on the norm of the preconditioned matrix, and a lower bound on the distance of its field of values from the origin. As an illustration of this framework, we prove new estimates for overlapping domain decomposition methods with Robin-type transmission conditions for the heterogeneous reaction-convection-diffusion equation.

A diagonal sweeping domain decomposition method with trace transfer for the Helmholtz equation | 2020

Wei LengLili Ju

In this paper, the diagonal sweeping domain decomposition method (DDM) for solving the high-frequency Helmholtz equation in $\mathbb{R}^n$ is re-proposed with the trace transfer method, where $n$ is the dimension. The diagonal sweeping DDM uses $2^n$ sweeps of diagonal directions on the checkerboard domain decomposition based on the source transfer method, it is sequential in nature yet suitable for parallel computing, since the number of sequential steps is quite small compared to the number of subdomains. The advantages of changing the basic transfer method from source transfer to trace transfer are as follows: first, no overlapping region is required in the domain decomposition; second, the sweeping algorithm becomes simpler since the transferred traces have only $n$ cardinal directions, whereas the transferred sources have all $3^n-1$ directions. We proved that the exact solution is obtained with the proposed method in the constant medium case, and also in the two-layered medium case provided the source is on the same side with the first swept subdomain. The efficiency of the proposed method is demonstrated using numerical experiments in two and three dimensions, and it is found that numerical differences of the diagonal sweeping DDM with the two transfer methods are very small using second-order finite difference discretization.

A domain decomposition method for Isogeometric multi-patch problems with inexact local solvers | 2020

Michal BosyMonica MontardiniGiancarlo SangalliMattia Tani

In Isogeometric Analysis, the computational domain is often described as multi-patch, where each patch is given by a tensor product spline/NURBS parametrization. In this work we propose a FETI-like solver where local inexact solvers exploit the tensor product structure at the patch level. To this purpose, we extend to the isogeometric framework the so-called All-Floating variant of FETI, that allows us to use the Fast Diagonalization method at the patch level. We construct then a preconditioner for the whole system and prove its robustness with respect to the local mesh-size $h$ and patch-size $H$ (i.e., we have scalability). Our numerical tests confirm the theory and also show a favourable dependence of the computational cost of the method from the spline degree $p$.

Balancing domain decomposition by constraints associated with subobjects | 2020

Santiago BadiaAlberto F. MartínHieu Nguyen

A simple variant of the BDDC preconditioner in which constraints are imposed on a selected set of subobjects (subdomain subedges, subfaces and vertices between pairs of subedges) is presented. We are able to show that the condition number of the preconditioner is bounded by $C \big(1+\log (L/h)\big)^2$, where $C$ is a constant, and $h$ and $L$ are the characteristic sizes of the mesh and the subobjects, respectively. As $L$ can be chosen almost freely, the condition number can theoretically be as small as $O(1)$. We will discuss the pros and cons of the preconditioner and its application to heterogeneous problems. Numerical results on supercomputers are provided.

Analysis of a Sinclair-type domain decomposition solver for atomistic/continuum coupling | 2019

M. Hodapp

The "flexible boundary condition method", introduced by Sinclair and coworkers in the 1970s, remains among the most popular methods for simulating isolated two-dimensional crystalline defects, embedded in an effectively infinite atomistic domain. In essence, the method can be characterized as a domain decomposition method which iterates between a local anharmonic and a global harmonic problem, where the latter is solved by means of the lattice Green function of the ideal crystal. This local/global splitting gives rise to tremendously improved convergence rates over related alternating Schwarz methods. In a previous publication (Hodapp et al., 2019, Comput. Methods in Appl. Mech. Eng. 348), we have shown that this method also applies to large-scale three-dimensional problems, possibly involving hundreds of thousands of atoms, using fast summation techniques exploiting the low-rank nature of the asymptotic lattice Green function. Here, we generalize the Sinclair method to bounded domains using a discrete boundary element method to correct the infinite solution with respect to a prescribed far-field condition, thus preserving the advantage of the original method of not requiring a global spatial discretization. Moreover, we present a detailed convergence analysis and show for a one-dimensional problem that the method is unconditionally stable under physically motivated assumptions. To further improve the convergence behavior, we develop an acceleration technique based on a relaxation of the transmission conditions between the two subproblems. Numerical examples for linear and nonlinear problems are presented to validate the proposed methodology.

On the Dirichlet-to-Neumann coarse space for solving the Helmholtz problem using domain decomposition | 2019

Niall BootlandVictorita Dolean

We examine the use of the Dirichlet-to-Neumann coarse space within an additive Schwarz method to solve the Helmholtz equation in 2D. In particular, we focus on the selection of how many eigenfunctions should go into the coarse space. We find that wave number independent convergence of a preconditioned iterative method can be achieved in certain special cases with an appropriate and novel choice of threshold in the selection criteria. However, this property is lost in a more general setting, including the heterogeneous problem. Nonetheless, the approach converges in a small number of iterations for the homogeneous problem even for relatively large wave numbers and is robust to the number of subdomains used.

Spectral domain decomposition method for physically-based rendering of Royaumont abbey | 2019

Guillaume Gbikpi-BenissanPatrick CalletFrederic Magoules

In the context of a virtual reconstitution of the destroyed Royaumont abbey church, this paper investigates computer sciences issues intrinsic to the physically-based image rendering. First, a virtual model was designed from historical sources and archaeological descriptions. Then some materials physical properties were measured on remains of the church and on pieces from similar ancient churches. We specify the properties of our lighting source which is a representation of the sun, and present the rendering algorithm implemented in our software Virtuelium. In order to accelerate the computation of the interactions between light-rays and objects, this ray-tracing algorithm is parallelized by means of domain decomposition techniques. Numerical experiments show that the computational time saved by a classic parallelization is much less significant than that gained with our approach.

Spectral domain decomposition method for physically-based rendering of photochromic/electrochromic glass windows | 2019

Guillaume Gbikpi-BenissanPatrick CalletFrederic Magoules

This paper covers the time consuming issues intrinsic to physically-based image rendering algorithms. First, glass materials optical properties were measured on samples of real glasses and other objects materials inside an hotel room were characterized by deducing spectral data from multiple trichromatic images. We then present the rendering model and ray-tracing algorithm implemented in Virtuelium, an open source software. In order to accelerate the computation of the interactions between light rays and objects, the ray-tracing algorithm is parallelized by means of domain decomposition method techniques. Numerical experiments show that the speedups obtained with classical parallelization techniques are significantly less significant than those achieved with parallel domain decomposition methods.

Beam-tracing domain decomposition method for urban acoustic pollution | 2019

Guillaume Gbikpi-BenissanFrederic Magoules

This paper covers the fast solution of large acoustic problems on low-resources parallel platforms. A domain decomposition method is coupled with a dynamic load balancing scheme to efficiently accelerate a geometrical acoustic method. The geometrical method studied implements a beam-tracing method where intersections are handled as in a ray-tracing method. Beyond the distribution of the global processing upon multiple sub-domains, a second parallelization level is operated by means of multi-threading and shared memory mechanisms. Numerical experiments show that this method allows to handle large scale open domains for parallel computing purposes on few machines. Urban acoustic pollution arrising from car traffic was simulated on a large model of the Shinjuku district of Tokyo, Japan. The good speed-up results illustrate the performance of this new domain decomposition method.

A posteriori error analysis for Schwarz overlapping domain decomposition methods | 2019

Jehanzeb ChaudhryDon EstepSimon Tavener

Domain decomposition methods are widely used for the numerical solution of partial differential equations on high performance computers. We develop an adjoint-based a posteriori error analysis for both multiplicative and additive overlapping Schwarz domain decomposition methods. The numerical error in a user-specified functional of the solution (quantity of interest) is decomposed into contributions that arise as a result of the finite iteration between the subdomains and from the spatial discretization. The spatial discretization contribution is further decomposed into contributions arising from each subdomain. This decomposition of the numerical error is used to construct a two stage solution strategy that efficiently reduces the error in the quantity of interest by adjusting the relative contributions to the error.

A Galerkin-Collocation domain decomposition method: application to the evolution of cylindrical gravitational waves | 2019

W. O. BarretoJ. A. CrespoH. P. de OliveiraE. L. Rodrigues

We present a Galerkin-Collocation domain decomposition algorithm applied to the evolution of cylindrical unpolarized gravitational waves. We show the effectiveness of the algorithm in reproducing initial data with high localized gradients and in providing highly accurate dynamics. We characterize the gravitational radiation with the standard Newman-Penrose Weyl scalar $\Psi_4$. We generate wave templates for both polarization modes, $\times$ and $+$, outgoing and ingoing, to show how they exchange energy nonlinearly. In particular, considering an initially ingoing $\times$ wave, we were able to trace a possible imprint of the gravitational analog of the Faraday effect in the generated templates.

D3M: A deep domain decomposition method for partial differential equations | 2019

Ke LiKejun TangTianfan WuQifeng Liao

A state-of-the-art deep domain decomposition method (D3M) based on the variational principle is proposed for partial differential equations (PDEs). The solution of PDEs can be formulated as the solution of a constrained optimization problem, and we design a multi-fidelity neural network framework to solve this optimization problem. Our contribution is to develop a systematical computational procedure for the underlying problem in parallel with domain decomposition. Our analysis shows that the D3M approximation solution converges to the exact solution of underlying PDEs. Our proposed framework establishes a foundation to use variational deep learning in large-scale engineering problems and designs. We present a general mathematical framework of D3M, validate its accuracy and demonstrate its efficiency with numerical experiments.

A domain decomposition preconditioning for the integral equation formulation of the inverse scattering problem | 2019

Carlos BorgesGeorge Biros

We propose domain decomposition preconditioners for the solution of an integral equation formulation of forward and inverse acoustic scattering problems with point scatterers. We study both forward and inverse problems and propose preconditioning techniques to accelerate the iterative solvers. For the forward scattering problem, we extend the domain decomposition based preconditioning techniques presented for partial differential equations in {\em "A restricted additive Schwarz preconditioner for general sparse linear systems", SIAM Journal on Scientific Computing, 21 (1999), pp. 792--797}, to integral equations. We combine this domain decomposition preconditioner with a low-rank correction, which is easy to construct, forming a new preconditioner. For the inverse scattering problem, we use the forward problem preconditioner as a building block for constructing a preconditioner for the Gauss-Newton Hessian. We present numerical results that demonstrate the performance of both preconditioning strategies.

Splitting-based domain decomposition methods for two-phase flow with different rock types | 2019

Elyes Ahmed

In this paper, we are concerned with the global pressure formulation of immiscible incompressible two-phase flow between different rock types. We develop for this problem two robust schemes based on domain decomposition (DD) methods and operator-splitting techniques. The first scheme follows a sequential procedure in which the (global) pressure, the saturation-advection and the saturation-diffusion problems are fully decoupled. In this scheme, each problem is treated individually using various DD approaches and specialized numerical methods. The coupling between the different problems is explicit and the time-marching is with no iterations. To adapt to different time scales of problem components and different rock types, the novel scheme uses a multirate time stepping strategy, by taking multiple finer time steps for saturation-advection within one coarse time step for saturation-diffusion and pressure, and permits independent time steps for the advection step in the different rocks. In the second scheme, we review the classical Implicit Pressure--Explicit Saturation (IMPES) method (by decoupling only pressure and saturation) in the context of multirate coupling schemes and nonconforming-in-time DD approaches. For the discretization, the saturation-advection problem is approximated with the explicit Euler method in time, and in space with the cell-centered finite volume method of first order of Godunov type. The saturation-diffusion problem is approximated in time with the implicit Euler method and in space with the mixed finite element method, as in the pressure problem. Finally, in a series of numerical experiments, we investigate the practicality of the proposed schemes, the accuracy-in-time of the multirate and nonconforming time strategies, and compare the convergence of various DD methods within each approach.

A pure source transfer domain decomposition method for Helmholtz equations in unbounded domain | 2019

Yu DuHaijun Wu

We propose a pure source transfer domain decomposition method (PSTDDM) for solving the truncated perfectly matched layer (PML) approximation in bounded domain of Helmholtz scattering problem. The method is a modification of the STDDM proposed by [Z. Chen and X. Xiang, SIAM J. Numer. Anal., 51 (2013), pp. 2331--2356]. After decomposing the domain into $N$ non-overlapping layers, the STDDM is composed of two series steps of sources transfers and wave expansions, where $N-1$ truncated PML problems on two adjacent layers and $N-2$ truncated half-space PML problems are solved successively. While the PSTDDM consists merely of two parallel source transfer steps in two opposite directions, and in each step $N-1$ truncated PML problems on two adjacent layers are solved successively. One benefit of such a modification is that the truncated PML problems on two adjacent layers can be further solved by the PSTDDM along directions parallel to the layers. And therefore, we obtain a block-wise PSTDDM on the decomposition composed of $N^2$ squares, which reduces the size of subdomain problems and is more suitable for large-scale problems. Convergences of both the layer-wise PSTDDM and the block-wise PSTDDM are proved for the case of constant wave number. Numerical examples are included to show that the PSTDDM gives good approximations to the discrete Helmholtz equations with constant wave numbers and can be used as an efficient preconditioner in the preconditioned GMRES method for solving the discrete Helmholtz equations with constant and heterogeneous wave numbers.

A scalable multilevel domain decomposition preconditioner with a subspace-based coarsening algorithm for the neutron transport calculations | 2019

Fande KongYaqi WangDerek R. GastonAlexander D. LindsayCody J. PermannRichard C. Martineau

The multigroup neutron transport equations has been widely used to study the interactions of neutrons with their background materials in nuclear reactors. High-resolution simulations of the multigroup neutron transport equations using modern supercomputers require the development of scalable parallel solving techniques. In this paper, we study a scalable transport method for solving the algebraic system arising from the discretization of the multigroup neutron transport equations. The proposed transport method consists of a fully coupled Newton solver for the generalized eigenvalue problems and GMRES together with a novel multilevel domain decomposition preconditioner for the Jacobian system. The multilevel preconditioner has been successfully used for many problems, but the construction of coarse spaces for certain problems, especially for unstructured mesh problems, is expensive and often unscalable. We introduce a new subspace-based coarsening algorithm to address this issue by exploring the structure of the matrix in the discretized version of the neutron transport problems. We numerically demonstrate that the proposed transport method is highly scalable with more than 10,000 processor cores for the 3D C5G7 benchmark problem on unstructured meshes with billions of unknowns. Compared with the traditional multilevel domain decomposition method, the new approach equipped with the subspace-based coarsening algorithm is much faster on the construction of coarse spaces.

Natural domain decomposition algorithms for the solution of time-harmonic elastic waves | 2019

Romain BrunetVictorita DoleanMartin J. Gander

We study for the first time Schwarz domain decomposition methods for the solution of the Navier equations modeling the propagation of elastic waves. These equations in the time harmonic regime are difficult to solve by iterative methods, even more so than the Helmholtz equation. We first prove that the classical Schwarz method is not convergent when applied to the Navier equations, and can thus not be used as an iterative solver, only as a preconditioner for a Krylov method. We then introduce more natural transmission conditions between the subdomains, and show that if the overlap is not too small, this new Schwarz method is convergent. We illustrate our results with numerical experiments, both for situations covered by our technical two subdomain analysis, and situations that go far beyond, including many subdomains, cross points, heterogeneous materials in a transmission problem, and Krylov acceleration. Our numerical results show that the Schwarz method with adapted transmission conditions leads systematically to a better solver for the Navier equations than the classical Schwarz method.

Combined use of mixed and hybrid finite elements method with domain decomposition and spectral methods for a study of renormalization for the KPZ model | 2019

Ciro Diaz

The focus of this work is the numerical approximation of time-dependent partial differential equations associated to initial-boundary value problems. This master dissertation is mostly concerned with the actual computation of the solution to nonlinear stochastic evolution problems governed by Kardar-Parisi-Zhang (KPZ) models. In addition, the dissertation aims to contribute to corroborate, by means of a large set of numerical experiments, that the initial-boundary value problem with periodic boundary conditions for the equation KPZ is ill-posed and that such equation needs to be renormalized. The approach to discretization of KPZ equation perfomed by means of the use of hybrid and mixed finite elements with a domain decomposition procedure along with a pertinent mollification of the noise. The obtained solution is compared with the well known solution given by the Cole-Hopf transformation of the stochastic heat equation with multiplicative noise. We were able to verify that both solutions exhibit a good agreement, but there is a shift that grows as the support of the mollifier decreases. For the numerical aproximation of the stochastic heat equation we use a state-of-the-art numerical method for evaluating semilinear stochastic PDE , which in turn combine spectral techniques, Taylor's expantions and particular numerical treatment to the underlying noise. Furthermore, a state-of-the-art renormalization procedure introduced by Martin Hairer is used to renormalize KPZ equation that is validated with nontrivial numerical experiments.

An iterative domain decomposition, spectral finite element method on non-conforming meshes suitable for high frequency Helmholtz problems | 2018

Ryan GalaguszSteve McFee

The purpose of this research is to describe an efficient iterative method suitable for obtaining high accuracy solutions to high frequency time-harmonic scattering problems. The method allows for both refinement of local polynomial degree and non-conforming mesh refinement, including multiple hanging nodes per edge. Rather than globally assemble the finite element system, we describe an iterative domain decomposition method which can use element-wise fast solvers for elements of large degree. Since continuity between elements is enforced through moment equations, the resulting constraint equations are hierarchical. We show that, for high frequency problems, a subset of these constraints should be directly enforced, providing the coarse space in the dual-primal domain decomposition method. The subset of constraints is chosen based on a dispersion criterion involving mesh size and wavenumber. By increasing the size of the coarse space according to this criterion, the number of iterations in the domain decomposition method depends only weakly on the wavenumber. We demonstrate this convergence behaviour on standard domain decomposition test problems and conclude the paper with application of the method to electromagnetic problems in two dimensions. These examples include beam steering by lenses and photonic crystal waveguides, as well as radar cross section computation for dielectric, perfect electric conductor, and electromagnetic cloak scatterers.

An immersed boundary method for fluid-structure interaction based on overlapping domain decomposition | 2018

Maria Giuseppina Chiara NestolaBarna BecsekHadi ZolfaghariPatrick ZulianDario De MarinisRolf KrauseDominik Obrist

We present a novel framework inspired by the Immersed Boundary Method for predicting the fluid-structure interaction of complex structures immersed in flows with moderate to high Reynolds numbers. The main novelties of the proposed fluid-structure interaction framework are 1) the use of elastodynamics equations for the structure, 2) the use of a high-order Navier-Stokes solver for the flow, and 3) the variational transfer (L2-projection) for coupling the solid and fluid subproblems. The dynamic behavior of a deformable structure is simulated in a finite element framework by adopting a fully implicit scheme for its temporal integration. It allows for mechanical constitutive laws including nonhomogeneous and fiber-reinforced materials. The Navier-Stokes equations for the incompressible flow are discretized with high-order finite differences which allow for the direct numerical simulation of laminar, transitional and turbulent flows. The structure and the flow solvers are coupled by using an L2-projection method for the transfer of velocities and forces between the fluid grid and the solid mesh. This strategy allows for the numerical solution of coupled large scale problems based on nonconforming structured and unstructured grids. The framework is validated with the Turek-Hron benchmark and a newly proposed benchmark modelling the flow-induced oscillation of an inert plate. A three-dimensional simulation of an elastic beam in transitional flow is provided to show the solver's capability of coping with anisotropic elastic structures immersed in complex fluid flow.

A belief propagation algorithm based on domain decomposition | 2018

Brad Lackey

This note provides a detailed description and derivation of the domain decomposition algorithm that appears in previous works by the author. Given a large re-estimation problem, domain decomposition provides an iterative method for assembling Boltzmann distributions associated to small subproblems into an approximation of the Bayesian posterior of the whole problem. The algorithm is amenable to using Boltzmann sampling to approximate these Boltzmann distributions. In previous work, we have shown the capability of heuristic versions of this algorithm to solve LDPC decoding and circuit fault diagnosis problems too large to fit on quantum annealing hardware used for sampling. Here, we rigorously prove soundness of the method.

Four-dimensional tomographic reconstruction by time domain decomposition | 2018

Viktor V. NikitinMarcus CarlssonFredrik AnderssonRajmund Mokso

Since the beginnings of tomography, the requirement that the sample does not change during the acquisition of one tomographic rotation is unchanged. We derived and successfully implemented a tomographic reconstruction method which relaxes this decades-old requirement of static samples. In the presented method, dynamic tomographic data sets are decomposed in the temporal domain using basis functions and deploying an L1 regularization technique where the penalty factor is taken for spatial and temporal derivatives. We implemented the iterative algorithm for solving the regularization problem on modern GPU systems to demonstrate its practical use.

A monolithic approach to fluid-structure interaction based on a hybrid Eulerian-ALE fluid domain decomposition involving cut elements | 2018

Benedikt SchottChristoph AgerWolfgang A. Wall

A novel method for complex fluid-structure interaction (FSI) involving large structural deformation and motion is proposed. The new approach is based on a hybrid fluid formulation that combines the advantages of purely Eulerian (fixed-grid) and Arbitrary-Lagrangian-Eulerian (ALE moving mesh) formulations in the context of FSI. The structure - as commonly given in Lagrangian description - is surrounded by a fine resolved layer of fluid elements based on an ALE-framework. This ALE-fluid patch, which is embedded in an Eulerian background fluid domain, follows the deformation and motion of the structural interface. This approximation technique is not limited to Finite Element Methods, but can can also be realized within other frameworks like Finite Volume or Discontinuous Galerkin Methods. In this work, the surface coupling between the two disjoint fluid subdomains is imposed weakly using a stabilized Nitsche's technique in a Cut Finite Element Method (CutFEM) framework. At the fluid-solid interface, standard weak coupling of node-matching or non-matching finite element approximations can be utilized. As the fluid subdomains can be meshed independently, a sufficient mesh quality in the vicinity of the common fluid-structure interface can be assured. To our knowledge the proposed method is the only method (despite some overlapping domain decomposition approaches that suffer from other issues) that allows for capturing boundary layers and flow detachment via appropriate grids around largely moving and deforming bodies and is able to do this e.g. without the necessity of costly remeshing procedures. In addition it might also help to safe computational costs as now background grids can be much coarser. Various FSI-cases of rising complexity conclude the work.

Parallel SPH modeling using dynamic domain decomposition and load balancing displacement of Voronoi subdomains | 2018

M. S. EgorovaS. A. DyachkovA. N. ParshikovV. V. Zhakhovsky

A highly adaptive load balancing algorithm for parallel simulations using particle methods, such as molecular dynamics and smoothed particle hydrodynamics (SPH), is developed. Our algorithm is based on the dynamic spatial decomposition of simulated material samples between Voronoi subdomains, where each subdomain with all its particles is handled by a single computational process which is typically run on a single CPU core of a multiprocessor computing cluster. The algorithm displaces the positions of neighbor Voronoi subdomains in accordance with the local load imbalance between the corresponding processes. It results in particle transfers from heavy-loaded processes to less-loaded ones. Iteration of the algorithm puts into alignment the processor loads. Convergence to a well-balanced decomposition from imbalanced one is improved by the usage of multi-body terms in the balancing displacements. The high adaptability of the balancing algorithm to simulation conditions is illustrated by SPH modeling of the dynamic behavior of materials under extreme conditions, which are characterized by large pressure and velocity gradients, as a result of which the spatial distribution of particles varies greatly in time. The higher parallel efficiency of our algorithm in such conditions is demonstrated by comparison with the corresponding static decomposition of the computational domain. Our algorithm shows almost perfect strong scalability in tests using from tens to several thousand processes.

Galerkin-Collocation domain decomposition method for arbitrary binary black holes | 2018

W. BarretoP. C. M. ClementeH. P. de OliveiraB. Rodriguez-Mueller

We present a new computational framework for the Galerkin-collocation method for double domain in the context of ADM 3+1 approach in numerical relativity. This work enables us to perform high resolution calculations for initial sets of two arbitrary black holes. We use the Bowen-York method for binary systems and the puncture method to solve the Hamiltonian constraint. The nonlinear numerical code solves the set of equations for the spectral modes using the standard Newton-Raphson method, LU decomposition and Gaussian quadratures. We show convergence of our code for the conformal factor and the ADM mass. Thus, we display features of the conformal factor for different masses, spins and linear momenta.