Search

Motivated by the unexpected failure of the triangle intersection component of the Projection Algorithm for Nonmatching Grids (PANG), this article provides a robust version with proof of backward stability. The new triangle intersection algorithm ensures consistency and parsimony across three types of calculations. The set of intersections produced by the algorithm, called representations, is shown to match the set of geometric intersections, called models. The article concludes with a comparison between the old and new intersection algorithms for PANG using an example found to reliably generate failures in the former.

We investigate a new type of preconditioner which is based on the analytic factorization of the operator into two parabolic factors. Approximate analytic factorizations lead to new block ILU preconditioners. We analyze the preconditioner at the continuous level where it is possible to optimize its performance. Numerical experiments illustrate the effectiveness of the new approach.

The first ideas for optimized Schwarz methods for Maxwell's equations came from the analysis of optimized Schwarz methods for the Helmholtz equation, see [3, 4, 2, 11]. For the case of the rot-rot formulation of the Maxwell equations, optimized Schwarz methods were developed in [1]. The systematic study of Schwarz methods for Maxwell's equations in their general formulation was started in [9, 10], and an entire hierarchy of families of optimized Schwarz methods was analyzed in [8], see also [5] for discontinuous Galerkin discretizations and large scale experiments. We present in this paper a first analysis of optimized Schwarz methods for Maxwell's equations with non-zero electric conductivity. We illustrate our analysis with numerical experiments.

Schwarz domain decomposition methods can be analyzed both at the continuous and discrete level. For consistent discretizations, one would naturally expect that the discretized method performs as predicted by the continuous analysis. We show in this short note for two model problems that this is not always the case, and that the discretization can both increase and decrease the convergence speed predicted by the continuous analysis.

The convergence of Schwarz methods can be influenced by the geome- try of the decomposition, and therefore also the optimized parameters in optimized Schwarz methods depend on the geometry. We present a first study of this influence, which reveals that in contrast to results in the literature so far, where only the interface length is taken into account, the diameter of the subdomains can play an important role as well. The new estimate also includes the influence of lateral boundary conditions.

We analyze overlapping Schwarz waveform relaxation for linear advection reaction diffusion equations. We prove linear convergence of the algorithm on unbounded time intervals and superlinear convergence on bounded time intervals. In both cases the convergence rates are shown to depend on the size of the overlap. The linear convergence result also depends on the number of subdomains, because it is limited by the classical steady state result of overlapping Schwarz for elliptic problems. The superlinear convergence result however is independent of the number of subdomains. Thus overlapping Schwarz waveform relaxation does not need a coarse space for robust convergence independent of the number of subdomains, if the algorithm is in the superlinear convergence regime. Numerical experiments confirm our analysis.

In many applications the viscous terms become only important in parts of the computational domain. As a typical example serves the flow around the wing of an airplane, where close to the wing the viscous terms in the Navier Stokes equations are essential for the solution, while away from the wing, Euler's equations would suffice for the simulation. This leads to the interesting problem of finding coupling conditions between these two partial differential equations of different type. While coupling conditions have been developed in the literature, for example by using a limiting procedure on a globally viscous problem, we are interested here to develop coupling conditions which lead to coupled solutions which are as close as possible to the fully viscous solution. We develop our new approach on the one dimensional model problem of advection reaction diffusion equations with pure advection reaction approximation in subregions, which leads to the problem of coupling first and second order operators. Our guiding principle for finding transmission conditions is an operator factorization, and we show both analytically and numerically that the new coupling conditions lead to coupled solutions which are much closer to the fully viscous ones than other coupling conditions from the literature.

The problem of finding the shortest road network is very old, the first written record goes back to a letter of Gauss replying to a question posed by Schumacher. After a historical review, we study the minimal road network problem using elementary mathematics, and show solutions for several examples.

Schwarz domain decomposition methods are the oldest domain decomposition methods. They were invented by Hermann Amandus Schwarz in 1869 as an analytical tool to rigorously prove results obtained by Riemann through a minimization principle. Renewed interest in these methods was sparked by the arrival of parallel computers, and variants of the method have been introduced and analyzed, both at the continuous and discrete level. It can be daunting to understand the similarities and subtle differences between all the variants, even for the specialist. This paper presents Schwarz methods as they were developed historically. From quotes by major contributors over time, we learn about the reasons for similarities and subtle differences between continuous and discrete variants. We also formally prove at the algebraic level equivalence and/or non-equivalence among the major variants for very general decompositions and many subdomains. We finally trace the motivations that led to the newest class called optimized Schwarz methods, illustrate how they can greatly enhance the performance of the solver, and show why one has to be cautious when testing them numerically.

The parareal algorithm is a method to solve time-dependent problems parallel in time: it approximates parts of the solution later in time simultaneously to parts of the solution earlier in time. In this paper the relation of the parareal algorithm to space-time multigrid and multiple shooting methods is first briefly discussed. The focus of the paper is on new convergence results that show superlinear convergence of the algorithm when used on bounded time intervals, and linear convergence for unbounded intervals.

Patch substructuring methods are non-overlapping domain decomposition methods like classical substructuring methods, but they use information from geometric patches reaching into neighboring subdomains, condensated on the interfaces, to enhance the performance of the method, while keeping it non-overlapping. These methods are very convenient to use in practice, but their convergence properties have not been studied yet. We analyze geometric patch substructuring methods for the special case of one patch per interface. We show that this method is equivalent to an overlapping Schwarz method using Neumann transmission conditions. This equivalence is obtained by first studying a new, algebraic patch method, which is equivalent to the classical Schwarz method with Dirichlet transmission conditions and an overlap corresponding to the size of the patches. Our results motivate a new method, the Robin patch method, which is a linear combination of the algebraic and the geometric one, and can be interpreted as an optimized Schwarz method with Robin transmission conditions. This new method has a significantly faster convergence rate than both the algebraic and the geometric one. We complement our results by numerical experiments.

We study the asymptotic behavior of solutions for a

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 consider the Givens QR factorization of banded Hessenberg-Toeplitz matrices of large order and relatively small bandwidth. We investigate the asymptotic behavior of the R factor and the Givens rotation when the order of the matrix goes to infinity, and present some interesting convergence properties. These properties can lead to savings in the computation of the exact QR factorization and give insight for approximative QR factorizations of interest in preconditioning. The properties also reveal the relation between the limit of the main diagonal elements of R and the largest absolute root of a polynomial.

Absorbing boundary conditions have been developed for truncating unbounded computational domains to bounded ones. The authors investigate the use of absorbing boundary conditions in domain decomposition algorithms for the wave equation. Moreover, they optimize the absorbing boundary conditions in order to obtain a good performance of the Schwarz waveform relaxation algorithm. The analysis given is confirmed by numerical experiments.

A sequential spectral method (SSM) is a spectral method in which the unknown coefficients of the approximate spectral expansion are computed sequentially, one at a time, instead of simultaneously, like in a classical spectral method (CSM). These methods are especially suited for approximating difficult nonlinear integro-differential equations where the solution behavior is largely unknown and the problem lies in finding a solution of the large scale nonlinear system of equations for the unknown expansion coefficients. The SSM leads by iteration to the same solution as the underlying CSM and thus inherits its spectral accuracy, but it avoids the simultaneous solution of a large system of linear equations. We prove convergence of the SSM to the spectral approximation of the underlying spectral method for a general class of nonlinear elliptic integro-differential equations, and illustrate the effectiveness of the method on two applications.

Semilinear evolution equations arise in many applications ranging from mathematical biology to chemical reactions (e.g., combustion). The significant difficulty in these equations is the nonlinearity, which combined with the discretized diffusion operator leads to large systems of nonlinear equations. To solve these equations, Newton's method or a variant thereof is often used, and to achieve convergence can require individual fine tuning for each case. This can be especially difficult if nothing is known about the solution behavior. In addition, one observes in many cases that not all frequency components are equally important for the solution; the frequency interaction is determined by the nonlinearity. It is therefore of interest to work in frequency space when analyzing the unknown behavior of such problems numerically. We propose in this paper an algorithm which reduces the dimensionality of the nonlinear problems to be solved to a size chosen by the user. The algorithm performs a decomposition in frequency space into subspaces, and an iteration is used to obtain the solution of the original problem from the solutions on the frequency subspaces. We prove linear convergence of the algorithm on unbounded time intervals, a result which is also valid for the stationary case. On bounded time intervals, we show that the new algorithm converges superlinearly, a rate faster than any linear rate. We obtain this result by relating the algorithm to an algorithm of waveform relaxation type. By using time windows, one can thus achieve any linear contraction rate desired. An additional advantage of this algorithm is its inherent parallelism.

Recently a variant of the additive Schwarz (AS) preconditioner, the restricted additive Schwarz (RAS) preconditioner has been introduced, and numerical experiments showed that RAS converges faster and requires less communication than AS. We show in this paper how RAS, which is defined at the matrix level, can be interpreted as an iteration at the continuous level of the underlying problem. This interpretation reveals why RAS converges faster than classical AS.