[amelius]

You can come close to that time complexity on a single CPU by using multigrid methods.

https://en.wikipedia.org/wiki/Multigrid_method

Unless of course your matrix has a prohibitively complicated structure.