×

Additive Schwarz iterations for Markov chains. (English) Zbl 1097.65047

Author’s summary: A convergence analysis is presented for additive Schwarz iterations when applied to consistent singular systems of equations of the form \(Ax=b\). The theory applies to singular \(M\)-matrices with one-dimensional null space and is applicable in particular to systems representing ergodic Markov chains, and to certain discretizations of partial differential equations. Additive Schwarz can be seen as a generalization of block Jacobi, where the set of indices defining the diagonal blocks have nonempty intersection; this is called the overlap. The presence of overlap is known to accelerate the convergence of the methods in the nonsingular case. By providing convergence results, as well as some characteristics of the induced splitting, we hope to encourage the use of this additional computational tool for the solution of Markov chains and other singular systems. We present several numerical examples showing that additive Schwarz performs better than block Jacobi. For completeness, a few numerical experiments with block Gauss-Seidel and multiplicative Schwarz are also included.

MSC:

65F10 Iterative numerical methods for linear systems
65C40 Numerical analysis or methods applied to Markov chains
15B48 Positive matrices and their generalizations; cones of matrices
60J22 Computational methods in Markov chains

Software:

MARCA
PDFBibTeX XMLCite
Full Text: DOI