"The most obvious way that sparsification can accelerate the solution of linear equations is by replacing the problem of solving systems in dense matrices by the problem of solving systems in sparse matrices. Recall that the Conjugate Gradient, used as a direct solver, can solve systems in n-dimensional matrices with m non-zero entries in time O(mn). So, if we could find a graph H with O(n) nonzero entries that was even a 1-approximation of G, then we could quickly solve systems in LG by using the Preconditioned Conjugate Gradient with LH as the preconditioner, and solving the systems in LH by the Conjugate Gradient. Each solve in H would then take time O(n^2), and the number of iterations of the PCG required to get an ǫ-accurate solution would be O(log ǫ−1). So, the total complexity would be O((m + n^2) log ǫ−1)."
I'm not really sure how you get O(n) 1-approximations of G (or even really what a 1-approximation is yet, as I haven't really read the paper), but that seems to be the idea, I think.
This is a common thing to use in randomized or approximate algorithms. For example, solving min-cut by assigning to 2 sets randomly is provably a 2-approximation.
I'm confused at how they claim O(m^{4/3}) (m is the number of edges) when even initializing an explicit n by n matrix is O(n^2), unless they assume that the graph isn't sparse (m>=k*n^1.5).
Or perhaps the matrix is sparsely represented.