Explore the vast range of titles available.

The parareal algorithm, which permits us to solve evolution problems in a time parallel fashion, has created a lot of attention over the past decade. The algorithm has its roots in the multiple shooting method for boundary value problems, which in the parareal algorithm is applied to initial value problems, with a particular coarse approximation of the Jacobian matrix. It is therefore of interest to formulate parareal-type algorithms for time-periodic problems, which also couple the end of the time interval with the beginning, and to analyze their performance in this context. We present and analyze two parareal algorithms for time-periodic problems: one with a periodic coarse problem and one with a nonperiodic coarse problem. An interesting advantage of the algorithm with the nonperiodic coarse problem is that no time-periodic problems need to be solved during the iteration, since on the time subdomains, the problems are not time-periodic either. We prove for both linear and nonlinear problems convergence of the new algorithms, with linear bounds on the convergence. We also extend these results to evolution partial differential equations using Fourier techniques. We illustrate our analysis with numerical experiments, both for model problems and the realistic application of a nonlinear cooled reverse-flow reactor system of partial differential equations. [PUBLICATION ABSTRACT]

Schwarz methods use a decomposition of the computational domain into subdomains and need to impose boundary conditions on the subdomain boundaries. In domain truncation one restricts the unbounded domain to a bounded computational domain and must also put boundary conditions on the computational domain boundaries. In both fields there are vast bodies of literature and research is very active and ongoing. It turns out to be fruitful to think of the domain decomposition in Schwarz methods as a truncation of the domain onto subdomains. Seminal precursors of this fundamental idea are papers by Hagstrom, Tewarson and Jazcilevich (1988), Després (1990) and Lions (1990). The first truly optimal Schwarz method that converges in a finite number of steps was proposed by Nataf (1993), 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. A key application of Schwarz methods with such sophisticated transmission conditions turned out to be time-harmonic wave propagation problems, because classical Schwarz methods simply do not work in this case. The past decade has given us many new Schwarz methods based on domain truncation. One review from an algorithmic perspective (Gander and Zhang 2019) showed the equivalence of many of these new methods to optimized Schwarz methods. The analysis of optimized Schwarz methods, however, is lagging behind their algorithmic development. The general abstract Schwarz framework cannot be used for the analysis of these methods, and thus there are many open theoretical questions about their convergence. Just as for practical multigrid methods, Fourier analysis has been instrumental for understanding the convergence of optimized Schwarz methods and for tuning their transmission conditions. Similar to local Fourier mode analysis in multigrid, the unbounded two-subdomain case is used as a model for Fourier analysis of optimized Schwarz methods due to its simplicity. Many aspects of the actual situation, e.g. boundary conditions of the original problem and the number of subdomains, were thus neglected in the unbounded two-subdomain analysis. While this gave important insight, new phenomena beyond the unbounded two-subdomain models were discovered. This present situation is the motivation for our survey: to give a comprehensive review and precise exploration of convergence behaviours of optimized Schwarz methods based on Fourier analysis, taking into account the original boundary conditions, many-subdomain decompositions and layered media. We consider as our model problem the operator $-\\Delta + \\eta $ in the diffusive case $\\eta>0$ (screened Laplace equation) or the oscillatory case $\\eta <0$ (Helmholtz equation), in order to show the fundamental difference in behaviour of Schwarz solvers for these problems. The transmission conditions we study include the lowest-order absorbing conditions (Robin), and also more advanced perfectly matched layers (PMLs), both developed first for domain truncation. Our intensive work over the last two years on this review has led to several new results presented here for the first time: in the bounded two-subdomain analysis for the Helmholtz equation, we see strong influence of the original boundary conditions imposed on the global problem on the convergence factor of the Schwarz methods, and the asymptotic convergence factors with small overlap can differ from the unbounded two-subdomain analysis. In the many-subdomain analysis, we find the scaling with the number of subdomains, e.g. when the subdomain size is fixed, robust convergence of the double-sweep Schwarz method for the free-space wave problem, either with fixed overlap and zeroth-order Taylor conditions or with a logarithmically growing PML, and we find that Schwarz methods with PMLs work like smoothers that converge faster for higher Fourier frequencies; in particular, for the free-space wave problem, plane waves (in the error) passing through interfaces at a right angle converge more slowly. In addition to our main focus on analysis in Sections 2 and 3, we start in Section 1 with an expository historical introduction to Schwarz methods, and in Section 4 we give a brief interpretation of the recently proposed optimal Schwarz methods for decompositions with cross-points from the viewpoint of transmission conditions. We conclude in Section 5 with a summary of open research problems. In Appendix A we provide a Matlab program for a block LU form of an optimal Schwarz method with cross-points, and in Appendix B we give the Maple program for the two-subdomain Fourier analysis.

Optimized Schwarz methods are a new class of Schwarz methods with greatly enhanced convergence properties. They converge uniformly faster than classical Schwarz methods and their convergence rates dare asymptotically much better than the convergence rates of classical Schwarz methods if the overlap is of the order of the mesh parameter, which is often the case in practical applications. They achieve this performance by using new transmission conditions between subdomains which greatly enhance the information exchange between subdomains and are motivated by the physics of the underlying problem. We analyze in this paper these new methods for symmetric positive definite problems and show their relation to other modern domain decomposition methods like the new Finite Element Tearing and Interconnect (FETI) variants.

We introduce a new non-overlapping optimized Schwarz method for fully anisotropic diffusion problems. Optimized Schwarz methods take into account the underlying physical properties of the problem at hand in the transmission conditions, and are thus ideally suited for solving anisotropic diffusion problems. We first study the new method at the continuous level for two subdomains, prove its convergence for general transmission conditions of Ventcell type using energy estimates, and also derive convergence factors to determine the optimal choice of parameters in the transmission conditions. We then derive optimized Robin and Ventcell parameters at the continuous level for fully anisotropic diffusion, both for the case of unbounded and bounded domains. We next present a discretization of the algorithm using discrete duality finite volumes, which are ideally suited for fully anisotropic diffusion on very general meshes. We prove a new convergence result for the discretized optimized Schwarz method with two subdomains using energy estimates for general Ventcell transmission conditions. We finally study the convergence of the new optimized Schwarz method numerically using parameters obtained from the continuous analysis. We find that the predicted optimized parameters work very well in practice, and that for certain anisotropies which we characterize, our new bounded domain analysis is important.

Cross-points in domain decomposition, i.e., points where more than two subdomains meet, have received substantial attention over the past years, since domain decomposition methods often need special attention in their definition at cross-points, in particular if the transmission conditions of the domain decomposition method contain derivatives, like in the Dirichlet-Neumann method. We study here for the first time the convergence of the Dirichlet-Neumann method at the continuous level in the presence of cross-points. We show that its iterates can be uniquely decomposed into two parts, an even symmetric part that converges geometrically, like when there are no cross-points present, and an odd symmetric part, which generates a singularity at the cross-point and is not convergent. We illustrate our analysis with numerical experiments.

A novel parallel algorithm for the integration of linear initial-value problems is proposed. This algorithm is based on the simple observation that homogeneous problems can typically be integrated much faster than inhomogeneous problems. An overlapping time-domain decomposition is utilized to obtain decoupled inhomogeneous and homogeneous subproblems, and a near-optimal Krylov method is used for the fast exponential integration of the homogeneous subproblems. We present an error analysis and discuss the parallel scaling of our algorithm. The efficiency of this approach is demonstrated with numerical examples. [PUBLICATION ABSTRACT]

The so-called Ritz–Galerkin method is one of the most fundamental tools of modern computing. Its origins lie in Hilbert's \"direct\" approach to the variational calculus of Euler–Lagrange and in the thesis of Walther Ritz, who died 100 years ago at the age of 31 after a long battle with tuberculosis. The thesis was submitted in 1902 in Göttingen, during a period of dramatic developments in physics. Ritz tried to explain the phenomenon of Balmer series in spectroscopy using eigenvalue problems of partial differential equations on rectangular domains. While this physical model quickly turned out to be completely obsolete, his mathematics later enabled him to solve difficult problems in applied sciences. He thereby revolutionized the variational calculus and became one of the fathers of modern computational mathematics. We will see in this article that the path leading to modern computational methods and theory involved a long struggle over three centuries requiring the efforts of many great mathematicians.

Over the past decade, partial differential equation models in elliptical geometries have become a focus of interest in several scientific and engineering applications: the classical studies of flow past a cylinder, the spherical particles in nano-fluids and spherical water filled domains are replaced by elliptical geometries which more accurately describe a wider class of physical problems of interest. Optimized Schwarz methods (OSMs) are among the best parallel methods for such models. We study here for the first time OSMs with elliptical domain decompositions, i.e. decompositions into an ellipse and elliptical rings. Using the technique of separation of variables, we decouple the spatial variables and reduce the subdomain problems to radial Mathieu like equations defined on finite intervals, which allows us to derive and study a new family of OSMs. Our analysis reveals that the optimized transmission parameters are not constants any more along the elliptical interfaces. We can prove however also that using the constant optimized parameters from the straight interface analysis in the literature scaled locally by the interface curvature is still efficient in an asymptotic sense, which leads to the important discovery of a unique factor in the optimized parameters and asymptotic performance determined by the geometry of the decomposition. We use numerical examples to illustrate our analysis and findings.

We study non-overlapping Schwarz methods for solving a steady-state diffusion problem in heterogeneous media. Various optimized transmission conditions are determined by solving the corresponding min-max problems; we consider different choices of Robin conditions and second order conditions. To compare the resulting methods, we analyze the convergence in two separate asymptotic regimes: when the mesh size is small, and when the jump in the coefficient is large. It is shown that optimized two-sided Robin transmission conditions are very effective in both regimes; in particular they give mesh independent convergence. Numerical experiments are presented to illustrate and confirm the theoretical results.

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 the 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 we 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.