A comparative application of Jacobi and Gauss Seidel’s numerical algorithms in page rank analysis

Abstract

In PageRank calculation the Jacobi matrix is given by d T (damping factor times transition matrix), a sparse matrix. The solution of the iteration is x, if the limit exists. The convergence is guaranteed, if the absolute value of the
largest eigen value of ƒv1ƒ{ Mƒw is less than one. In case of PageRank calculation this is fulfilled for 0< d < 1. An improved Gauss-Seidel iteration algorithm, based on the decomposition M ƒ­ D ƒy L ƒyU where D, L and U are the diagonal, lower triangular and upper triangular parts of M would yield x D ƒvL x U x bƒw i i i ƒ­ ƒ{ ƒy ƒy ƒy ƒy 1* * * 1 1 . Introducing a relaxation parameter £f ¡Ú 0 leads to a generalization of the Gauss-Seidel method
x ƒv ƒwx D ƒvL x U x bƒw i i i i ƒ­ ƒ{ ƒy ƒ{ ƒy ƒy ƒy ƒy 1 1* * * 1 1 ƒÜ ƒÜ . This work compares the two methods with a C++ code numerically.