<abstract xml:lang="en" xmlns="http://www.w3.org/1999/xhtml"><p>The article considers the effectiveness of various methods used to solve systems of linear equations (which emerge while modeling computer networks and systems with Markov chains) and the practical influence of the methods applied on accuracy. The paper considers some hybrids of both direct and iterative methods. Two varieties of the Gauss elimination will be considered as an example of direct methods: the LU factorization method and the WZ factorization method. The Gauss-Seidel iterative method will be discussed. The paper also shows preconditioning (with the use of incomplete Gauss elimination) and dividing the matrix into blocks where blocks are solved applying direct methods. The motivation for such hybrids is a very high condition number (which is bad) for coefficient matrices occuring in Markov chains and, thus, slow convergence of traditional iterative methods. Also, the blocking, preconditioning and merging of both are analysed. The paper presents the impact of linked methods on both the time and accuracy of finding vector probability. The results of an experiment are given for two groups of matrices: those derived from some very abstract Markovian models, and those from a general 2D Markov chain.</p></abstract>

The article considers the effectiveness of various methods used to solve systems of linear equations (which emerge while modeling computer networks and systems with Markov chains) and the practical influence of the methods applied on accuracy. The paper considers some hybrids of both direct and iterative methods. Two varieties of the Gauss elimination will be considered as an example of direct methods: the LU factorization method and the WZ factorization method. The Gauss-Seidel iterative method will be discussed. The paper also shows preconditioning (with the use of incomplete Gauss elimination) and dividing the matrix into blocks where blocks are solved applying direct methods. The motivation for such hybrids is a very high condition number (which is bad) for coefficient matrices occuring in Markov chains and, thus, slow convergence of traditional iterative methods. Also, the blocking, preconditioning and merging of both are analysed. The paper presents the impact of linked methods on both the time and accuracy of finding vector probability. The results of an experiment are given for two groups of matrices: those derived from some very abstract Markovian models, and those from a general 2D Markov chain.

Influence of Preconditioning and Blocking on Accuracy in Solving Markovian Models

Institute of Mathematics, Marie Curie-Skłodowska University, Pl. M. Curie-Skłodowskiej 1, 20-031 Lublin, Poland

International Journal of Applied Mathematics and Computer Science

The article considers the effectiveness of various methods used to solve systems of linear equations (which emerge while modeling computer networks and systems...

Influence of Preconditioning and Blocking on Accuracy in Solving Markovian Models

Publié en ligne: 08 juil. 2009

Pages: 207 - 217

DOI: https://doi.org/10.2478/v10006-009-0017-3

Mots clés
preconditioning, linear equations, blocking methods, Markov chains, WZ factorization

This content is open access.

Influence of Preconditioning and Blocking on Accuracy in Solving Markovian Models

Publié en ligne: 08 juil. 2009

Pages: 207 - 217

DOI: https://doi.org/10.2478/v10006-009-0017-3

Mots cléspreconditioning, linear equations, blocking methods, Markov chains, WZ factorization

This content is open access.

Mots clés
preconditioning, linear equations, blocking methods, Markov chains, WZ factorization