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

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.

---

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.