0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Paul Jul 12 '12 at 15:23
  • $\begingroup$ 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? $\endgroup$ – Wolfgang Bangerth Jul 12 '12 at 17:25
  • $\begingroup$ 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$. $\endgroup$ – Michelle Dolly Jul 12 '12 at 18:12
  • $\begingroup$ 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. $\endgroup$ – Michelle Dolly Jul 12 '12 at 18:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Wolfgang Bangerth Jul 12 '12 at 23:41
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.