Università degli Studi di Genova

Gram matrices of fast algebras have a rank structure
Abstract: We study the computational problem of finding the optimal preconditioner (in the sense of T. Chan) 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. Keywords: Toeplitz, Hankel, $\omega$-circulant, trigonometric and Hartley transforms, preconditioning, Gram matrix, semiseparable MSC: 65, 15 Pubblicato su: SIAM Journal on Matrix Analysis and Applications Vol. 31 (2009) N. 2 Pag. 526-545

Gram matrices of fast algebras have a rank structure