Merging Jacobi and Gauss-Seidel Methods for Solving Markov Chains on Computer Clusters

Abstract—The authors consider the use of the parallel iterative methods for solving large sparse linear equation systems resulting from Markov chains—on a computer cluster. A combination of Jacobi and Gauss-Seidel iterative methods is examined in a parallel version. Some results of experiments for sparse systems with over 3 × 107 equations and about 2 × 108 nonzeros which we obtained from a Markovian model of a congestion control mechanism are reported. I