[jmblpati]

The constants are galactic: any 'fast matrix multiplication' algorithm outside of Strassen's algorithm has some incredible constants that are somewhat intrinsic to the recursive framework. The algorithm is primarily of theoretical importance (prior to this no one knew whether sparsity significantly helped methods of this type for solving linear systems), but it is not implementable.

However the block Krylov algorithm itself presented in this paper has a little bit more of a chance of being implementable than fast matrix multiplication (the matrix multipliciation is only used to solve small linear systems to deal with small eigendirections in the Krylov subspace). I am still skeptical that this is a truly practical algorithm due to its complexity, but unlike the case of generic FMM there is no obvious bottleneck.

On the other hand, in recent years Dan Spielman and collaborators have been working on fast implementations of Laplacian solvers: https://github.com/danspielman/Laplacians.jl I believe a lot of the fixed constants and combinatorial routines are changed from what is theoretically provable, but from screwing around with the code in the past it seems very fast in practice.