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.
Gram matrices of fast algebras have a rank structure
DI BENEDETTO, FABIO
2009-01-01
Abstract
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
