Influence of preconditioning and blocking on accuracy in solving Markovian models

Beata Bylina; Jarosław Bylina

International Journal of Applied Mathematics and Computer Science (2009)

  • Volume: 19, Issue: 2, page 207-217
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Beata Bylina, and Jarosław Bylina. "Influence of preconditioning and blocking on accuracy in solving Markovian models." International Journal of Applied Mathematics and Computer Science 19.2 (2009): 207-217. <http://eudml.org/doc/207928>.

@article{BeataBylina2009,
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.},
author = {Beata Bylina, Jarosław Bylina},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {preconditioning; linear equations; blocking methods; Markov chains; WZ factorization; numerical examples},
language = {eng},
number = {2},
pages = {207-217},
title = {Influence of preconditioning and blocking on accuracy in solving Markovian models},
url = {http://eudml.org/doc/207928},
volume = {19},
year = {2009},
}

TY - JOUR
AU - Beata Bylina
AU - Jarosław Bylina
TI - Influence of preconditioning and blocking on accuracy in solving Markovian models
JO - International Journal of Applied Mathematics and Computer Science
PY - 2009
VL - 19
IS - 2
SP - 207
EP - 217
AB - 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.
LA - eng
KW - preconditioning; linear equations; blocking methods; Markov chains; WZ factorization; numerical examples
UR - http://eudml.org/doc/207928
ER -

References

top
  1. Benzi, M. and Ucar, B. (2007). Block triangular preconditioners for M-matrices and Markov chains, Electronic Transactions on Numerical Analysis 26(1): 209-227. Zbl1171.65388
  2. Bylina, B. and Bylina, J. (2004). Solving Markov chains with the WZ factorization for modelling networks, Proceedings of the 3rd International Conference Aplimat 2004, Bratislava, Slovakia, pp. 307-312. Zbl1081.68549
  3. Bylina, B. and Bylina, J. (2007). Linking of direct and iterative methods in Markovian models solving, Proceedings of the International Multiconference on Computer Science and Information Technology, Wisła, Poland, Vol. 2, pp. 467-477. Zbl1170.65022
  4. Bylina, B. and Bylina, J. (2008). Incomplete WZ decomposition algorithm for solving Markov chains, Journal of Applied Mathematics 1(2): 147-156. Zbl1081.68549
  5. Bylina, J. (2003). Distributed solving of Markov chains for computer network models, Annales UMCS Informatica 1(1): 15-20. 
  6. Campbell, S. L. and Meyer, C. D. (1979). Generalized Inverses of Linear Transformations, Pitman Publishing Ltd., London. Zbl0417.15002
  7. Chawla, M. and Khazal, R. (2003). A new WZ factorization for parallel solution of tridiagonal systems, International Journal of Computer Mathematics 80(1): 123-131. Zbl1035.65028
  8. Duff, I. S. (2004). Combining direct and iterative methods for the solution of large systems in different application areas, Technical Report RAL-TR-2004-033, Rutherford Appleton Laboratory, Chilton. 
  9. Evans, D. J. and Barulli, M. (1998). BSP linear solver for dense matrices, Parallel Computing 24(5-6): 777-795. Zbl0909.68013
  10. Evans, D. J. and Hatzopoulos, M. (1979). The parallel solution of linear system, International Journal of Computer Mathematics 7(3): 227-238. Zbl0442.65019
  11. Funderlic, R. E. and Meyer, C. D. (1986). Sensitivity of the stationary distrbution vector for an ergodic Markov chain, Linear Algebra and Its Applications 76(1): 1-17. Zbl0583.60064
  12. Funderlic, R. E. and Plemmons, R. J. (1986). Updating LU factorizations for computing stationary distributions, SIAM Journal on Algebraic and Discrete Methods 7(1): 30-42. Zbl0592.65014
  13. Golub, G. H. and Meyer, C. D. (1986). Using the QR factorization and group inversion to compute, differentiate and estimate the sensitivity of stationary distributions for Markov chains, SIAM Journal on Algebraic and Discrete Methods 7(2): 273-281. Zbl0594.60072
  14. Harrod, W. J. and Plemmons, R. J. (1984). Comparisons of some direct methods for computing stationary distributions of Markov chains, SIAM Journal on Scientific and Statistical Computing 5(2): 453-469. Zbl0574.65147
  15. Haviv, M. (1987). Aggregation/disagregation methods for computing the stationary distribution of a Markov chain, SIAM Journal on Numerical Analysis 24(4): 952-966. Zbl0637.65147
  16. Jennings, A. and Stewart, W. J. (1975). Simultaneous iteration for partial eigensolution of real matrices, Journal of the Institute of Mathematics and Its Applications 15(3): 351-361. Zbl0307.65042
  17. Pollett, P. K. and Stewart, D. E. (1994). An efficient procedure for computing quasi-stationary distributions of Markov chains with sparse transition structure, Advances in Applied Probability 26(1): 68-79. Zbl0797.60060
  18. Rao, S. C. S. and Sarita (2008). Parallel solution of large symmetric tridiagonal linear systems, Parallel Computing 34(3): 177-197. 
  19. Ridler-Rowe, C. J. (1967). On a stochastic model of an epidemic, Advances in Applied Probability 4(1): 19-33. Zbl0166.15903
  20. Saad, Y. and Schultz, M. H. (1986). GMRES: A generalized minimal residual algorithm for solving non-symmetric linear systems, SIAM Journal of Scientific and Statistical Computing 7(3): 856-869. Zbl0599.65018
  21. Schweitzer, P. J. and Kindle, K. W. (1986). An iterative aggregation-disaggregation algorithm for solving linear systems, Applied Mathematics and Computation 18(4): 313-353. Zbl0594.65020
  22. Stewart, W. (1994). Introduction to the Numerical Solution of Markov Chains, Princeton University Press, Chichester. Zbl0821.65099
  23. Stewart, W. J. and Jennings, A. (1981). A simultaneous iteration algorithm for real matrices, ACM Transactions on Mathematical Software 7(2): 184-198. Zbl0455.65028
  24. Yalamov, P. and Evans, D. J. (1995). The WZ matrix factorization method, Parallel Computing 21(7): 1111-1120. Zbl0875.68775

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.