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

Improve this question
$\endgroup$
9
  • $\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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 23:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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