You know, I'll go out on the limb and say (unhelpfully) that a FFT is more efficient than any general dense matvec.