A graph based approach to the convergence of some iterative methods for singular M-matrices and Markov chains
Borovac
Stefan
Borovac, Stefan
aut
2006-07-07
2006-07-19
2014-08-12
en
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.<p>
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.<p>
Schwarz methods are widely used as preconditioners for the numerical solution
of partial differential equations and can be classified as domain
decomposition methods.<p>
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.<p>
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.<p>
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. <p>
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.<p>
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.<p>
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.
Linear systems
M-matrices
Markov chains
singular matrices
iterative methods
block methods
additive Schwarz
multiplicative Schwarz
domain decomposition methods
overlap
asynchronous iterations
parallel iterations
two-stage
non-stationary
matrix graph theory
urn:nbn:de:hbz:468-20060359
2014-08-12T08:35:53.576Z
2014-08-12T09:50:00.492Z
published
Diss
fbc/mathematik/diss2006/borovac