Parallel computing applied to solving large Markov chains. A feasibility study.

• Autorzy: Szczerbiński Z.

Warianty tytułu

PL

Obliczenia równoległe w zastsowaniu do rozwiązywania dużych łańcuchów Markowa. Studium wykonalności

• Języki publikacji: EN

Abstrakty

EN

The article is concerned with parallel computation issues arising in numerical solution of systems of linear eąuations which describe stationary pro-babilitifis of stat.es in largc Markov chairis. Upon introduction to the .subject of Markov chains and their solution, several adeąuate solution methods arę surreyed, froni the cla.ssical through projection to decompositional ones. Each algoriUiin is accoinpaniocl by a study of its suitability to parallel computing (rnulti- and vector procfissing). Additional opinions on aspects of the potential for parallelization in the discussed methods arę contained in the conclusion.

PL

Artykuł jest poświęcony zagadnieniom obliczeń równoległych, występującym w trakcie numerycznego rozwiązywania układów równań liniowych, opisujących stacjonarne prawdopodobieństwa stanów w dużych łańcuchach Markowa. Po wprowadzeniu do tematyki łańcuchów Markowa, dokonano przeglądu wybranych metod rozwiązywania, począwszy od klasycznych, poprzez projekcyjne, do metod dekompozycyjnych. Dla każdego algorytmu została dokonana analiza, na ile nadaje się on do wykonania w trybie równoległym (wieloprocesorowyrn lub wektorowym). Dodatkowe uwagi dotyczące możliwości zrównoleglania dla omawianych metod zawarto w części końcowej.

Słowa kluczowe

EN

parallel computing; Markov chains; iterative methods; systems of linear equations

PL

oblczenia równoległe; łańcuchy Markowa; metody iteracyjne; układy równań liniowych

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2003
• Tom: Vol. 24, nr 4
• Strony: 7--28
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Szczerbiński Z.

• Polish Academy of Sciences, Institute for Theoretical and Applied Computer Science Gliwice

Bibliografia

• 1. Akl S. G.: Parallel Computations: Models and Methods. Prentice Hall, New Jersey 1997.
• 2. Amestoy P. R., Duff I. S.: Vectorization of a multiprocessor multifrontal code. International Journal of Supercomputer Applications, 1989, Vol. 3, pp. 41-59.
• 3. Amestoy P. R., Duff I. S., L’Excellent J. Y.: Multifrontal solvers within the PARASOL environment. In: Kagstrom B., Dongarra J., Elmroth E., Waśniewski J. (Eds.): Applied Parallel Computing PARA’98. Springer Verlag, Berlin 1998, pp. 7-11.
• 4. Barrett R., Berry M., Chan T., Demmel J., Dorato J., Dongarra J., Eijkhout V., Pozo R., Romine C., Van der Vogt H.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia 1994.
• 5. Courtois P. J.: Decomposability: Queueing and Computer System Applications. Academic Press, Orlando 1977.
• 6. Da Cunha R. D., Hopkins T.: Parallel overrelaxation algorithms for systems of linear equations. In: Welch P. et al (Eds.): Transputing '91. IOS Press, 1991, pp. 159-169.
• 7. Dryja M., Jankowska J., Jankowski M.: Survey of Numerical Methods and Algorithms. Part 2. WNT, Warsaw 1982.
• 8. Eisenstat S., Elman H., Schultz M.: Variational iterative methods for nonsymmetric systems of linear equations. SIAM Journal on Numerical Analysis, 1983, Vol. 20, pp. 345-357.
• 9. Evans D.: Parallel algorithms in computational linear algebra. In: Van Leeuven J., Lenstra J. (Eds.): Parallel Computers and Computations. Centrum voor Wiskunde en Informatica 1985.
• 10. Fletcher R.: Conjugate Gradient Methods for Indefinite Systems. Springer Verlag, Berlin 1976.
• 11. Fortuna Z., Macukow B., Wąsowski J.: Numerical Methods 4th ed. WNT, Warsaw 1998.
• 12. Freund R. W.: A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems. SIAM Journal on Scientific and Statistical Computing, 1996, Vol. 14, pp. 470-482.
• 13. Freund R. W., Nachtigal N. M.: QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numerische Mathematik, 1991, Vol. 60, pp. 315-339.
• 14. Golub G. H., Van Loan C. F.: Matrix Computations. The Johns Hopkins University Press, Baltimore 1983.
• 15. Gutknecht M, H.: Changing the norm in conjugate gradient type algorithms. SIAM Journal on Numerical Analysis, 1993, Vol. 30, pp. 40-56.
• 16. Hestenes M. R., Stiefel E.: Methods of conjugate gradients for solving linear systems. J. Research Natl. Bur. Standards, 1952, Vol. 49, pp. 409-436.
• 17. Knottenbelt W. J.: Parallel Performance Analysis of Large Markov Chains. Ph. D. Thesis, University of London, Imperial College of Science, Technology and Medicine 1999.
• 18. Kozielski S., Szczerbiński Z.: Parallel Computers: Architecture, Elements of Programming 2nd ed. WNT, Warsaw 1994.
• 19. Ma S., Chrono pou los A. T.: Implementation of iterative methods for large sparse nonsymmetric linear systems on parallel vector computers. International Journal on Supercomputing, 1990, Vol. 4, pp. 9-24.
• 20. Meijerrink J., Van der Vorst H.: An iterative solution method for linear systems for which rhe coefficient matrix is a symmetric m-matrix. Mathematical Computation, 1977, Vol. 31, pp. 148-162.
• 21. Paige С. C., Saunders M. A.: Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 1975, Vol. 12, pp. 617-624.
• 22. Pecka P.: An Object-Oriented Multithreaded System for Modelling Transient States in a Computer Network with Markov Chains. Ph. D. Thesis, Polish Academy of Sciences, Institute for Theoretical and Applied Computer Science, Gliwice 2002 (in Polish).
• 23. Quinn M. J., Deo N.: Parallel graph algorithms. Computing Surveys, 1984, Vol. 16, pp. 319-348.
• 24. Saad Y., Schultz M. H.: GMRES: a generalized minimal residual algorithm for solving non-symmetric linear systems. SIAM Journal on Scientific and Statistical Computing, 1986, Vol. 7, pp. 856-869.
• 25. Sleijpen G. L., Fokkema D. R.: BiCGSTAB(L) for linear equations involving unsym-metric matrices with complex spectrum. Electronic Transactions on Numerical Analysis, 1983, Vol. 1, pp. 11-32.
• 26. Sonneveld P.: CGS, a fast Lanczos-type solver for nonsymmetric systems. SIAM Journal on Scientific and Statistical Computing, 1989, Vol. 10, pp. 36-52.
• 27. Stewart W. J.: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton 1994.