|
Where n is dimensions of the matrix representing the linear system of equations, m the number of non-zero entries in the matrix. This is from a new paper by Koutis, Miller and Peng all from Carnegie Mellon: http://arxiv.org/pdf/1003.2958 I'm used to O(n^3) methods I learned in undergrad linear algebra. This kind of blows my mind. The only trouble is that I have no idea how it works. If I could get some pointers that would explain the groundwork (terms like graph sparsifiers and combinatorial preconditioner are bandied about just in the abstract), I'd be immensely appreciative. |
|
Some links to background and relevant papers appear on this webpage from Dan Spielman. Also his talk in the FOCS website http://techtalks.tv/focs/2010/ clarifies almost all the basic concepts.
(Nov 08 '10 at 09:18)
Alexandre Passos ♦
|
|
I'm not familiar with these techniques either, but it seems there are a few steps to understand the significance of this.
This paper, then, develops what they call an incremental sparsifier, which is a graph that approximates another given graph as you add edges in a specific way. With this guaranteed approximation they can build a solver that runs in the alloted time. I've just summarized their main claims here, and I have in no way verified or undersood their results. |