New answers tagged matrices
3
I know this is a really old question, but it seems like this recent paper https://arxiv.org/abs/1912.08805 improves the runtime to $O(n^\omega)$, down from $O(n^3)$.
3
It's a good question. You can use a Laplacian solver if $A$ is symmetric and diagonally semi-dominant (SDD). This is the subject of Theorem 9.2 in your reference book from Vishnoi. A good exposition of the proof (which was originally by Gremban) can be found in Appendix A of the paper by Kelner, Orecchia, Sidford and Zhu (arXiv:1301.6628).
A recent result by ...
Top 50 recent answers are included
Related Tags
matrices × 133linear-algebra × 48
ds.algorithms × 40
cc.complexity-theory × 25
graph-theory × 16
reference-request × 12
time-complexity × 11
co.combinatorics × 9
matrix-product × 9
boolean-matrix × 9
na.numerical-analysis × 7
randomized-algorithms × 6
sparse-matrix × 6
graph-algorithms × 5
np-hardness × 5
optimization × 5
permanent × 5
approximation-algorithms × 4
quantum-computing × 3
lower-bounds × 3
randomness × 3
communication-complexity × 3
tree × 3
open-problem × 3
spectral-graph-theory × 3