This thesis can be divided into three parts: cycles in domain decomposition methods; the equivalence between extrapolation methods and Krylov subspace methods, and; the intersection of simplices.
Domain decomposition methods subdivide a problem into subdomains, and resolves each subdomain individually before recombining them. Research into these methods concerns how to do the recombination procedure. It can be slow, and so we want to accelerate it, for example by using Newton’s method.
There are no criteria for the convergence of a domain decomposition method accelerated by Newton’s method. In the second chapter of this thesis I present a nonlinear PDE for which such a method does not converge. Instead, this method cycles between two points. By manipulating this PDE I find the period doubling and the same results in higher dimensions.
In the third chapter I consider three types of methods. Principally it concerns extrapolation methods, but also Krylov subspace methods and the multisecant equations. This latter method is an extension of the secant method to higher dimensions. In fact, there exist many methods that generalize this method, though most derive from these equations. By starting with these equations one can construct the extrapolation methods and afterwards the Krylov subspace methods. With this construction the three types of methods become equivalent.
The remainder of the thesis concerns an intersection algorithm for simplices which is robust. We consider first the algorithm for triangles, then tetrahedra, and finally simplices in arbitrary dimension. The algorithm uses the principle of parsimony, which tells us to do the smallest number of calculations necessary to find the result. We ask how much information each calculation tells us and we do not repeat calculations that tell us the same information.
Most of the last chapter is on the implementation of the algorithm. One must consider which intersections to calculate and how to store the calculations. I develop techniques to do these things in the context of simplices.
