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

PL

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

EN

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

• 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