Timeline for Efficiently compute the trace of a sparse matrix times the inverse of a sparse matrix?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 17, 2016 at 10:33 | comment | added | loup blanc | @ Suvrit , yes I forgot "sparsity". | |
| Feb 14, 2016 at 22:22 | comment | added | Suvrit | @loupblanc thanks! Why the $n^2$? The subroutines use only matrix-vector calls, and under the OP's assumption, each matrix*vector call costs $O(n)$. How large $m$ has to be is harder to determine and requires more analysis (it's the same thing as figuring out how many random samples one should draw to be able to compute something to a given accuracy). But maybe you are right it won't be truly $O(mn)$ because of the nested call to $A^{1/2}u$ --- there are other fancier ideas also possible, if I get a chance I'll try to mention those. | |
| Feb 14, 2016 at 18:26 | comment | added | loup blanc | @ Suvrit , very pretty post (+1, but that will not hardly change your total!). What about the complexity ? I think that it is in $O(mn^2)$ with a "not small" constant. How do you choose $m$ ? | |
| Dec 16, 2015 at 13:09 | history | edited | Suvrit | CC BY-SA 3.0 |
reformatted to make it easier to read.
|
| Dec 15, 2015 at 19:28 | history | edited | Suvrit | CC BY-SA 3.0 |
added more stuff
|
| Dec 15, 2015 at 19:21 | comment | added | Suvrit | @Jeff $A^{1/2}$ does not have to be explicitly available. For instance, all you need is access to a subroutine that approximates the vector $A^{1/2}u$, and this approximation can be also done using Lanczos (using Krylov methods). But we need to do this $m$ times for the $m$ random vectors $u_i$, which can be done reasonably fast --- at no point, there is any dense matrix involved.... | |
| Dec 15, 2015 at 18:54 | comment | added | Jeff | Interesting approach. I don't think I can access to $A^{1/2}$ unfortunately. As I've convinced of it, $A$ isn't low rank and so I think $A^{1/2}$ would be dense, with $O(n^2)$ non-zero entries. | |
| Dec 15, 2015 at 18:29 | history | answered | Suvrit | CC BY-SA 3.0 |