# 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

1
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
show 4 more comments

## 1 Answer

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)$

The problem would be reduced to (hopefully) not many sparse matrix multiplications.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 19, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9328204393386841, "perplexity_flag": "middle"}