# 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