BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Martin J. Gander

Martin J. Gander appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NANumerical Analysismath.APmath.CA

Catalog footprint

What is connected

16works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2022arXiv

Closed form optimized transmission conditions for complex diffusion with many subdomains

Optimized transmission conditions in domain decomposition methods have been the focus of intensive research efforts over the past decade. Traditionally, transmission conditions are optimized for two subdomain model configurations, and then used in practice for many subdomains. We optimize here transmission conditions for the first time directly for many subdomains for a class of complex diffusion problems. Our asymptotic analysis leads to closed form optimized transmission conditions for many subdomains, and shows that the asymptotic best choice in the mesh size only differs from the two subdomain best choice in the constants, for which we derive the dependence on the number of subdomains explicitly, including the limiting case of an infinite number of subdomains, leading to new insight into scalability. Our results include both Robin and Ventcell transmission conditions, and we also optimize for the first time a two-sided Ventcell condition. We illustrate our results with numerical experiments, both for situations covered by our analysis and situations that go beyond.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Convergence of parallel overlapping domain decomposition methods for the Helmholtz equation

We analyse parallel overlapping Schwarz domain decomposition methods for the Helmholtz equation, where the subdomain problems satisfy first-order absorbing (impedance) transmission conditions, and exchange of information between subdomains is achieved using a partition of unity. We provide a novel analysis of this method at the PDE level (without discretization). First, we formulate the method as a fixed point iteration, and show (in dimensions 1,2,3) that it is well-defined in a tensor product of appropriate local function spaces, each with $L^2$ impedance boundary data. Given this, we then obtain a bound on the norm of the fixed point operator in terms of the local norms of certain impedance-to-impedance maps arising from local interactions between subdomains. These bounds provide conditions under which (some power of) the fixed point operator is a contraction. In 2-d, for rectangular domains and strip-wise domain decompositions (with each subdomain only overlapping its immediate neighbours), we present two techniques for verifying the assumptions on the impedance-to-impedance maps which ensure power contractivity of the fixed point operator. The first is through semiclassical analysis, which gives rigorous estimates valid as the frequency tends to infinity. These results verify the required assumptions for sufficiently large overlap. For more realistic domain decompositions, we directly compute the norms of the impedance-to-impedance maps by solving certain canonical (local) eigenvalue problems. We give numerical experiments that illustrate the theory. These also show that the iterative method remains convergent and/or provides a good preconditioner in cases not covered by the theory, including for general domain decompositions, such as those obtained via automatic graph-partitioning software.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Low-rank Parareal: a low-rank parallel-in-time integrator

In this work, the Parareal algorithm is applied to evolution problems that admit good low-rank approximations and for which the dynamical low-rank approximation (DLRA) can be used as time stepper. Many discrete integrators for DLRA have recently been proposed, based on splitting the projected vector field or by applying projected Runge--Kutta methods. The cost and accuracy of these methods are mostly governed by the rank chosen for the approximation. These properties are used in a new method, called low-rank Parareal, in order to obtain a time-parallel DLRA solver for evolution problems. The algorithm is analyzed on affine linear problems and the results are illustrated numerically.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the nonlinear Dirichlet-Neumann method and preconditioner for Newton's method

The Dirichlet-Neumann (DN) method has been extensively studied for linear partial differential equations, while little attention has been devoted to the nonlinear case. In this paper, we analyze the DN method both as a nonlinear iterative method and as a preconditioner for Newton's method. We discuss the nilpotent property and prove that under special conditions, there exists a relaxation parameter such that the DN method converges quadratically. We further prove that the convergence of Newton's method preconditioned by the DN method is independent of the relaxation parameter. Our numerical experiments further illustrate the mesh independent convergence of the DN method and compare it with other standard nonlinear preconditioners.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Schwarz methods by domain truncation

Schwarz methods use a decomposition of the computational domain into subdomains and need to put boundary conditions on the subdomain boundaries. In domain truncation one restricts the unbounded domain to a bounded computational domain and also needs to put boundary conditions on the computational domain boundaries. It turns out to be fruitful to think of the domain decomposition in Schwarz methods as truncation of the domain onto subdomains. The first truly optimal Schwarz method that converges in a finite number of steps was proposed in 1994 and used precisely transparent boundary conditions as transmission conditions between subdomains. Approximating these transparent boundary conditions for fast convergence of Schwarz methods led to the development of optimized Schwarz methods -- a name that has become common for Schwarz methods based on domain truncation. Compared to classical Schwarz methods which use simple Dirichlet transmission conditions and have been successfully used in a wide range of applications, optimized Schwarz methods are much less well understood, mainly due to their more sophisticated transmission conditions. This present situation is the motivation for our survey: to give a comprehensive review and precise exploration of convergence behaviors of optimized Schwarz methods based on Fourier analysis taking into account the original boundary conditions, many subdomain decompositions and layered media. The transmission conditions we study include the lowest order absorbing conditions (Robin), and also more advanced perfectly matched layers (PML), both developed first for domain truncation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Asymptotic Analysis for Overlap in Waveform Relaxation Methods for RC Type Circuits

Waveform relaxation (WR) methods are based on partitioning large circuits into sub-circuits which then are solved separately for multiple time steps in so-called time windows, and an iteration is used to converge to the global circuit solution in each time window. Classical WR converges quite slowly, especially when long time windows are used. To overcome this issue, optimized WR (OWR) was introduced which is based on optimized transmission conditions that transfer information between the sub-circuits more efficiently than classical WR. We study here for the first time the influence of overlapping sub-circuits in both WR and OWR applied to RC circuits. We give a circuit interpretation of the new transmission conditions in OWR and derive closed-form asymptotic expressions for the circuit elements representing the optimization parameter in OWR. Our analysis shows that the parameter is quite different in the overlapping case, compared to the nonoverlapping one. We then show numerically that our optimized choice performs well, also for cases not covered by our analysis. This paper provides a general methodology to derive optimized parameters and can be extended to other circuits or system of differential equations or space-time PDEs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Analysis of a New Harmonically Enriched Multiscale Coarse Space for Domain Decomposition Methods

We propose a new, harmonically enriched multiscale coarse space (HEM) for domain decomposition methods. For a coercive high contrast model problem, we show how to enrich the coarse space so that the method is robust against any variations and discontinuities in the problem parameters both inside subdomains and across and along subdomain boundaries. We prove our results for an enrichment strategy based on solving simple, lower dimensional eigenvalue problems on the interfaces between subdomains, and we call the resulting coarse space the spectral harmonically enriched multiscale coarse space (SHEM). We then also give a variant that performs equally well in practice, and does not require the solve of eigenvalue problems, which we call non-spectral harmonically enriched multiscale coarse space (NSHEM). Our enrichment process naturally reaches the optimal coarse space represented by the full discrete harmonic space, which enables us to turn the method into a direct solver (OHEM). We also extensively test our new coarse spaces numerically, and the results confirm our analysis

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Dirichlet-Neumann Waveform Relaxation Method for the 1D and 2D Heat and Wave Equations in Multiple subdomains

We present a Waveform Relaxation (WR) version of the Dirichlet-Neumann algorithm, formulated specially for multiple subdomains splitting for general parabolic and hyperbolic problems. This method is based on a non-overlapping spatial domain decomposition, and the iteration involves subdomain solves in space-time with corresponding interface condition, and finally organize an exchange of information between neighboring subdomains. Using a Fourier-Laplace transform argument, for a particular relaxation parameter, we present convergence analysis of the algorithm for the heat and wave equations. We prove superlinear convergence for finite time window in case of the heat equation, and finite step convergence for the wave equation. The convergence behavior however depends on the size of the subdomains and the time window length on which the algorithm is employed. We illustrate the performance of the algorithm with numerical results, and show a comparison with classical and optimized Schwarz WR methods.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A new Algorithm Based on Factorization for Heterogeneous Domain Decomposition

Often computational models are too expensive to be solved in the entire domain of simulation, and a cheaper model would suffice away from the main zone of interest. We present for the concrete example of an evolution problem of advection reaction diffusion type a heterogeneous domain decomposition algorithm which allows us to recover a solution that is very close to the solution of the fully viscous problem, but solves only an inviscid problem in parts of the domain. Our new algorithm is based on the factorization of the underlying differential operator, and we therefore call it factorization algorithm. We give a detailed error analysis, and show that we can obtain approximations in the viscous region which are much closer to the viscous solution in the entire domain of simulation than approximations obtained by other heterogeneous domain decomposition algorithms from the literature.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Analysis of a New Space-Time Parallel Multigrid Algorithm for Parabolic Problems

We present and analyze a new space-time parallel multigrid method for parabolic equations. The method is based on arbitrarily high order discontinuous Galerkin discretizations in time, and a finite element discretization in space. The key ingredient of the new algorithm is a block Jacobi smoother. We present a detailed convergence analysis when the algorithm is applied to the heat equation, and determine asymptotically optimal smoothing parameters, a precise criterion for semi-coarsening in time or full coarsening, and give an asymptotic two grid contraction factor estimate. We then explain how to implement the new multigrid algorithm in parallel, and show with numerical experiments its excellent strong and weak scalability properties.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Analysis of a Time Multigrid Algorithm for DG-Discretizations in Time

We present and analyze for a scalar linear evolution model problem a time multigrid algorithm for DG-discretizations in time. We derive asymptotically optimized parameters for the smoother, and also an asymptotically sharp convergence estimate for the two grid cycle. Our results hold for any A-stable time stepping scheme and represent the core component for space-time multigrid methods for parabolic partial differential equations. Our time multigrid method has excellent strong and weak scaling properties for parallelization in time, which we show with numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Analysis of Schwarz methods for a hybridizable discontinuous Galerkin discretization

Schwarz methods are attractive parallel solvers for large scale linear systems obtained when partial differential equations are discretized. For hybridizable discontinuous Galerkin (HDG) methods, this is a relatively new field of research, because HDG methods impose continuity across elements using a Robin condition, while classical Schwarz solvers use Dirichlet transmission conditions. Robin conditions are used in optimized Schwarz methods to get faster convergence compared to classical Schwarz methods, and this even without overlap, when the Robin parameter is well chosen. We present in this paper a rigorous convergence analysis of Schwarz methods for the concrete case of hybridizable interior penalty (IPH) method. We show that the penalization parameter needed for convergence of IPH leads to slow convergence of the classical additive Schwarz method, and propose a modified solver which leads to much faster convergence. Our analysis is entirely at the discrete level, and thus holds for arbitrary interfaces between two subdomains. We then generalize the method to the case of many subdomains, including cross points, and obtain a new class of preconditioners for Krylov subspace methods which exhibit better convergence properties than the classical additive Schwarz preconditioner. We illustrate our results with numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Cross-Points in Domain Decomposition Methods with a Finite Element Discretization

Non-overlapping domain decomposition methods necessarily have to exchange Dirichlet and Neumann traces at interfaces in order to be able to converge to the underlying mono-domain solution. Well known such non-overlapping methods are the Dirichlet-Neumann method, the FETI and Neumann-Neumann methods, and optimized Schwarz methods. For all these methods, cross-points in the domain decomposition configuration where more than two subdomains meet do not pose any problem at the continuous level, but care must be taken when the methods are discretized. We show in this paper two possible approaches for the consistent discretization of Neumann conditions at cross-points in a Finite Element setting.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Dirichlet-Neumann and Neumann-Neumann Waveform Relaxation Algorithms for Parabolic Problems

We present a waveform relaxation version of the Dirichlet-Neumann and Neumann-Neumann methods for parabolic problems. Like the Dirichlet-Neumann method for steady problems, the method is based on a non-overlapping spatial domain decomposition, and the iteration involves subdomain solves with Dirichlet boundary conditions followed by subdomain solves with Neumann boundary conditions. For the Neumann-Neumann method, one step of the method consists of solving the subdomain problems using Dirichlet interface conditions, followed by a correction step involving Neumann interface conditions. However, each subdomain problem is now in space and time, and the interface conditions are also time-dependent. Using Laplace transforms, we show for the heat equation that when we consider finite time intervals, the Dirichlet-Neumann and Neumann-Neumann methods converge superlinearly for an optimal choice of the relaxation parameter, similar to the case of Schwarz waveform relaxation algorithms. The convergence rate depends on the size of the subdomains as well as the length of the time window. For any other choice of the relaxation parameter, convergence is only linear. We illustrate our results with numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Dirichlet-Neumann and Neumann-Neumann Waveform Relaxation for the Wave Equation

We present a Waveform Relaxation (WR) version of the Dirichlet-Neumann and Neumann-Neumann algorithms for the wave equation in space time. Each method is based on a non-overlapping spatial domain decomposition, and the iteration involves subdomain solves in space time with corresponding interface condition, followed by a correction step. Using a Laplace transform argument, for a particular relaxation parameter, we prove convergence of both algorithms in a finite number of steps for finite time intervals. The number of steps depends on the size of the subdomains and the time window length on which the algorithms are employed. We illustrate the performance of the algorithms with numerical results, and also show a comparison with classical and optimized Schwarz WR methods.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Optimized Schwarz Waveform Relaxation for Advection Reaction Diffusion Equations in Two Dimensions

Optimized Schwarz Waveform Relaxation methods have been developed over the last decade for the parallel solution of evolution problems. They are based on a decomposition in space and an iteration, where only subproblems in space-time need to be solved. Each subproblem can be simulated using an adapted numerical method, for example with local time stepping, or one can even use a different model in different subdomains, which makes these methods very suitable also from a modeling point of view. For rapid convergence however, it is important to use effective transmission conditions between the space-time subdomains, and for best performance, these transmission conditions need to take the physics of the underlying evolution problem into account. The optimization of these transmission conditions leads to a mathematically hard best approximation problem of homographic type. We study in this paper in detail this problem for the case of linear advection reaction diffusion equations in two spatial dimensions. We prove comprehensively best approximation results for transmission conditions of Robin and Ventcel type. We give for each case closed form asymptotic values for the parameters, which guarantee asymptotically best performance of the iterative methods. We finally show extensive numerical experiments, and we measure performance corresponding to our analysis

0 citations0 reviewsNo code linkedOpen access