Gram Matrices of Fast Algebras Have a Rank Structure
Fabio Di Benedetto · SIAM Journal on Matrix Analysis and Applications · 2009
We study the computational problem of finding the optimal preconditioner (in the sense of [T. Chan, SIAM J. Sci. Stat. Comp., 9 (1988), pp. 766–771]) of a given matrix in an algebra related to a fast transform; $\omega$-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.