My thoughts exactly...
Symmetric, (Strictly) diagonally dominant matrices are great: Non-singular, real spectrum, diagonalizable...In fact, purely from the fact that the eigenvalues can be bounded away from 0, many iterative methods will have provably fast O(n^2) convergence...beating the classic O(n^3) by an order of magnitude.
I'm not up to speed in the particular tricks used for the Symmetric, DD regime, but certainly one would only "naively" try solving this using Gaussian elimination, due to the special structure. One thing I thought was interesting was that the authors mention that the "previous" fast algorithm solves in:
Well, for n 10^52 (HUUUUUUUUUUUGE!!!) n^2 is less than nlog(n)^25, so there complexity constant becomes really important!!! I can't imagine that the "previous" algorithm was useful (practically speaking!)