SMCTools 2009: Tools for Solving Structured Markov Chains

TITLE: A Software Tool for the Steady-state Analysis of Google-like
Stochastic Matrices

AUTHORS: Tugrul Dayar and Gokce N. Noyan

ABSTRACT: The problem of computing the steady-state vector of positive 
stochastic matrices which are convex combinations of sparse, nonnegative 
matrices possibly having zero rows with appropriately chosen rank-1 
matrices is addressed by a software tool. The dynamically changing 
matrices used by the Google search engine in ranking web pages are among 
the largest of such matrices. Ranking pages amounts to solving for the 
steady-state vectors of these matrices. The tool implements the power, 
quadratically extrapolated power, and iterative methods based on various 
block partitionings, including those with block triangular form and with
triangular blocks obtained using cutsets.

KEY WORDS: Markov chains, steady–state vector, Google