Didn't read TFA, but it's hard to think of a linear algebra operation that is both that slow and takes time independent of n and k.