# Quickly computing inversion of a large sparse partial stochastic matrix

Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing only the diagonal entries of $M$, and $R$ containing the remaining entries of $M$. What would be a fast way to compute $D(I−R)^{−1}$ (or a good approximation)? Instead of low computational complexity, I'm looking for fast practical performance.

What I actually care about is $D(I−R)^{−1}$ for a continuous stream of vectors $x$'s, though $M$ may also change (both nodes and edges), but less often. Looks similar to PageRank, but still quite different. What would be a fast implementation? - Thanks, Michelle

• Hello Michelle and welcome to Scicomp! Is the matrix $(I-R)$ well-conditioned, in general? This can have a big impact on whether approximating its inverse is practical or not. – Paul Jul 12 '12 at 15:23
• What do you know about the entries of $M$? You say they are sparse, so the vectors that make up $M$ are sparse as well. Are the few non-zero entries simply ones, or are they distributed real numbers? Also, are the diagonal entries of $M$ (i.e., the matrix $D$) always nonzero? – Wolfgang Bangerth Jul 12 '12 at 17:25
• Hello Paul, thanks. I don't know whether $(I-R)$ is technically well-conditioned, but intuitively the answer varies gradually with gradual changes in $M$. – Michelle Dolly Jul 12 '12 at 18:12
• Wolfgang, The non-zero entries are usually not 1, but distributed reals (< 1). Some diagonal entries may be zero, but most will be non-zero. Thanks. – Michelle Dolly Jul 12 '12 at 18:15
• Too bad. I had hoped that the diagonal entries are as sparse as the rest which would mean that $D$ would have only few nonzeros on the diagonal -- making the problem substantially lower-dimensional. – Wolfgang Bangerth Jul 12 '12 at 23:41

Here is an idea. How about developing $(I-R)^{-1}$ in a geometric series? It only converges if all the eigenvalues of R are smaller than 1. But if it does then
$D(I-R)^{-1} = D(I+R+R^2+\ldots)$