Go to page

Bibliographic Metadata

 The document is publicly available on the WWW


This thesis concerns the interaction of two widely known topics in the field of applied mathematics. These are Markov chains (or likewise singular M-matrices) and Schwarz methods. Markov chains as well as singular M-matrices are extensively used, their range of application stretching from stochastic processes over network modeling to the discretisation of partial differential equations. Schwarz methods are widely used as preconditioners for the numerical solution of partial differential equations and can be classified as domain decomposition methods. Both topics are brought together for the solution of consistent square linear systems or likewise the Frobenius vector problem, i.e. a fixed point problem for nonnegative matrices of unit spectral radius. It is a known technique to solve such problems using block Jacobi or block Gauss-Seidel iterations. Schwarz methods can be seen as a generalisation of these techniques. They naturally occur in two setups, the additive Schwarz iterations and the multiplicative Schwarz iterations which extend the block Gauss-Seidel iteration. Both iterations have their own advantages. Additive Schwarz methods are easy to parallelise. Multiplicative Schwarz usually converges more rapidly but cannot be parallelised in such an easy way. However, it can be partly parallelised using block asynchronous iterations. In this work, solutions of linear systems having a positive fixed point using additive and (standard and asynchronous) multiplicative Schwarz iterations are considered. This is done for several different block updates including the standard (one-level) update, the two-stage update, and an update derived from the power iteration. Additionally, relaxed versions of the three block updates are considered. One main goal of this thesis lies in the detailed analysis of the structure of a nonnegative matrix having a positive fixed point. It turns out that such matrices possess some basic pattern which can be exploited to construct convergent Schwarz iterations. This pattern consists of either a spanning tree or a spanning forest within the transposed graph. Based on these patterns, operators for Schwarz iterations can be constructed which are consistent and (semi)convergent for several block updates. We put some special emphasise on the differences between non-relaxed and relaxed block updates. Additionally, we obtain some results for block asynchronous iterations. Altogether, several new results for additive and multiplicative Schwarz iterations as well as asynchronous iterations are achieved. In contrast to the known theory on this topics the theory presented here is completely uniform and based only on the structure of the given matrix which is either a spanning tree or a spanning forest within the transposed graph.