Timeline for Fast inversion of a special kind of matrices - approximations are ok
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 8, 2016 at 19:49 | history | edited | user9072 |
edited tags
|
|
| Jul 12, 2012 at 16:54 | comment | added | Suvrit | as the crudest baseline, i'd approximately solve the linear system $(I-R)z=x$ for each $x$ that comes in. If the $x$'s are not too different from each other, you can "warm-start" your linear system solvers (GMRES, PCG, etc.), and run those solvers to only a few iterations to save time---for a large sparse problem, this should give a reasonable approximation. | |
| Jul 12, 2012 at 14:51 | comment | added | Michelle Dolly | 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 | |
| Jul 12, 2012 at 14:40 | comment | added | Steve Huntsman | 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. | |
| Jul 12, 2012 at 10:16 | comment | added | David Ketcheson | I suggest asking on scicomp.stackexchange.com. | |
| Jul 12, 2012 at 9:21 | comment | added | Suvrit | 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$... | |
| Jul 12, 2012 at 6:43 | history | asked | Michelle Dolly | CC BY-SA 3.0 |