Gram matrices of fast algebras have a rank structure

We study the computational problem of finding the optimal preconditioner of a given matrix in an algebra related to a fast transform; ω-circulants, 16 trigonometric, and 8 Hartley-type algebras are considered. For all these cases we prove that the Gram matrix associated with a suitable sparse basis has a rank structure that can be described in terms of quasiseparability. As a consequence, the preconditioner can often be computed in linear time.