Welcome to MathOverflow

Question

2

1

Suppose I have a stochastic matrix $M$ (with thousands or millions of stochastic column vectors), which I split 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. Thanks. Michelle

flag	asked Jul 12 at 6:43 Michelle Dolly 21●1

1

probably you care about the operation $Mx$ or $M^{-1}x$, rather than the inverse itself, because if $M$ is huge, how do you store it? suppose it is sparse, then its inverse will be almost always dense, so a decent approximation might end up being dense too, and thus difficult to store. however, the crude approximation $(I-R)^{-1}=\sum_k R^k$ can be "quickly" applied to a vector $x$... – suVRit Jul 12 at 9:21

1

I suggest asking on scicomp.stackexchange.com. – David Ketcheson Jul 12 at 10:16

1

In general, so-called "black-box" linear algebra techniques offer very good theoretical and practical performance for sparse or structured matrix operations (which I presume covers your problem). The basic idea is to treat matrix multiplication as an oracle: in the sparse or structured case, this will have subquadratic complexity and can be leveraged to accelerate more complex operations. You can combine this thinking with Krylov methods. – Steve Huntsman Jul 12 at 14:40

Suvrit, Thanks. You're right. M is sparse, as it represents some links in a web graph. However, instead of $M^{-1}x$, I care about $D(I-R)^{-1}x$ for a continuous stream of $x$'s, though $M$ may also change (both nodes and edges), but less often. Looks similar to PageRank, but still quite different. Can we do better than this crude approximation? In either case, what would be a fast implementation? Thanks. - Michelle – Michelle Dolly Jul 12 at 14:51

David, Thanks for the suggestion. – Michelle Dolly Jul 12 at 15:10

show 1 more comment

Fast inversion of a special kind of matrices - approximations are ok

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.