Asynchronous iterative algorithms are parallel iterative algorithms in which communications and iterations are not synchronized among processors. Thus, as soon as a processing unit finishes its own calculations, it starts the next cycle with the latest data received during a previous cycle, without waiting for any other processing unit to complete its own calculation. These algorithms increase the number of updates in some processors (as compared to the synchronous case) but suppress most idle times. This usually results in a reduction of the (execution) time to achieve convergence. Optimized Schwarz methods (OSM) are domain decomposition methods in which the transmission conditions between subdomains contain operators of the form \linebreak $\partial/\partial \nu +\Lambda$, where $\partial/\partial \nu$ is the outward normal derivative and $\Lambda$ is an optimized local approximation of the global Steklov-Poincar\'e operator. There is more than one family of transmission conditions that can be used for a given partial differential equation (e.g., the $OO0$ and $OO2$ families), each of these families containing a particular approximation of the Steklov-Poincar\'e operator. These transmission conditions have some parameters that are tuned to obtain a fast convergence rate. Optimized Schwarz methods are fast in terms of iteration count and can be implemented asynchronously. In this thesis we analyze the convergence behavior of the synchronous and asynchronous implementation of OSM applied to solve partial differential equations with a shifted Laplacian operator in bounded rectangular domains. We analyze two cases. In the first case we have a shift that can be either positive, negative or zero, a one-way domain decomposition and transmission conditions of the $OO2$ family. In the second case we have Poisson's equation, a domain decomposition with cross-points and $OO0$ transmission conditions. In both cases we reformulate the equations defining the problem into a fixed point iteration that is suitable for our analysis, then derive convergence proofs and analyze how the convergence rate varies with the number of subdomains, the amount of overlap, and the values of the parameters introduced in the transmission conditions. Additionally, we find the optimal values of the parameters and present some numerical experiments for the second case illustrating our theoretical results. To our knowledge this is the first time that a convergence analysis of optimized Schwarz is presented for bounded subdomains with multiple subdomains and arbitrary overlap. The analysis presented in this thesis also applies to problems with more general domains which can be decomposed as a union of rectangles.
Open access
Advanced Numerical Methods in Computational Mathematics
In this issue, we present two very different papers written in two very different styles. The first is a survey of the multiple timescales method for approximating solutions to differential equations. Multiple timescale methods are common in the literature and an integral part of many graduate programs. However, like riding a bicycle, you need some practice, experience, and insight to use it properly and have meaningful results. The second is an exposition on the Mountain Pass Lemma and related mathematical ideas underlying the existence of saddle points. Despite its name, the second article is no ordinary hike through the hills. In “Profits and Pitfalls of Timescales in Asymptotics,” author Ferdinand Verhulst presents a survey of multiple timescale methods. A colleague of mine once sarcastically pointed out that a tremendous amount of insight can be gleaned from the observation that in almost all problems, parameters are either larger than one or smaller than one, leading to an asymptotic approximation in one form or another. However, one does not have to look far to find problems where it is hard to handle the resulting asymptotic series using a simple Taylor series. Multiple timescales can resolve these problems, but the challenge remains of how to know what the multiple timescales should be without having special knowledge of the problem. Verhulst does an admirable job presenting the basic ideas behind determining timescales a priori using two basic concepts: normal forms and bifurcation theory. In the former case, one transforms the problem into a simpler expression to reveal underlying timescales. In the latter case, understanding the dynamics of a system in terms of bifurcations reveals the qualitative structure of the solution and therefore the timescales. Thus, the author puts order to a body of knowledge that can often appear to students as a disjoint collection of tricks for special problems. In “Mountain Passes and Saddle Points,” author James Bisgard develops the Mountain Pass Lemma of Ambrosetti and Rabinowitz which specifies sufficient conditions for the existence of saddle points. Beginning with accessible examples of smooth functions $F: R^2 \rightarrow R$, we can think of $F$ as the height of the landscape. The central element of this manuscript is a very clear proof of the Mountain Pass Lemma, which essentially states that if there is a local minimum in a valley surrounded by a mountain range and there is a point somewhere beyond the mountain range that is lower than the local minimum, then with an additional special requirement, it can be shown that there must be a mountain pass (saddle point) somewhere. While it may seem that there should always be a mountain pass without any additional requirements, the authors present some counterexamples early in the paper to show that this is not a trivial issue. (I could not resist the urge to fire up my tablet and explore some of the sample surfaces.) The special requirement is the Palais--Smale condition, which is the seemingly peculiar condition that every sequence $x_n$ having two properties, (1) that the height above these points is bounded and (2) that the $\| \nabla F(x_n) \|$ approaches zero, must have a convergent subsequence. The author goes on to extend the Mountain Pass Lemma to domains of any finite dimension and from there to Hilbert spaces. Finally, the author uses the concepts involved in the proof to develop methods for finding saddle points. In summary, the Education section in this issue has something for everyone. The first offering focuses on methods and techniques and would be ideal for a graduate course on perturbation methods or applied mathematics. The second paper is analytic, anchored to theorems and proofs but having ample discussion. It would find a home in an undergraduate and graduate real analysis course. Both take a fresh look at classic subjects in mathematics and could be used to liven up traditional courses in most undergraduate and graduate programs.
A review of optimal control theory for linear systems with quadratic cost functions is presented. Some of the theoretical and practical limitations are discussed with special reference to distributed parameter systems. First a procedure is described for finding the optimal control by constructing a sequence of controllers that converges to the optimal; this method is valid for systems of infinite dimension provided that the operators in the state differential equation satisfy certain conditions. The proof is carried out both for the finite and infinite time interval and the connection is shown with the Riccati equation. The main problem in implementation is that one needs complete knowledge of the state at all times in order to build the optimal controller, this is almost certainly impossible for distributed parameter systems. When the state cannot be measured completely it is proved that an optimal control is realisable for time invariant finite dimensional systems. \n \nThe problems of finding this control are then investigated and computational methods discussed. If the optimal control with complete knowledge of the state cannot be implemented, a method is presented whereby one can find bounds on the possible increase in the value of the cost function arising from the use of some sub-optimal control; several examples are considered. The constrained optimal control depends on the initial state and new optimisation criteria must be put forward to deal with the case in which the initial state is unknown; the most common consist of minimising the cost that can result from the worst initial state. It is then shown how the controllers designed according to these criteria may be improved by using one's limited observation at time zero to place some constraints on the initial state. The Liapunov matrix equation plays an important part in calculating the cost of any control so reducing the computational effort in its solution is useful. It is shown how this can be done and it is of special relevance for distributed parameter systems with their states expressed as an infinite series of eigenfunctions; the results are applied to a diffusion equation example. \n \nFinally, it is shown how optimal control theory may be applied to the design of proportional-integral-derivative controllers. This is done from two standpoints and the resulting controllers are shown to be identical, though the second method of proof is valid for infinite dimensional systems. The results are then applied to a simple example and to a distributed population dynamics system. The practicality of the methods of the thesis are applied to a system with realistic parameters; recommendations are made as to the best approaches. \n