We introduce a new class of simultaneously diagonalizable real matrices, the γ -matrices, which include both symmetric circulant matrices and a subclass of the set of all reverse circulant matrices. We define some algorithms for fast computation of the product between a γ -matrix and a real vector. We proved that the computational cost of a multiplication between a γ -matrix and a real vector is of at most 74nlog2n+o(nlog2n) additions and 12nlog2n+o(nlog2n) multiplications. Our algorithm can be used to improve the performance of general discrete transforms for multiplications of real vectors.
A Fast Discrete Transform for a Class of Simultaneously Diagonalizable Matrices
Boccuto A.;Gerace I.
;Giorgetti V.
2022
Abstract
We introduce a new class of simultaneously diagonalizable real matrices, the γ -matrices, which include both symmetric circulant matrices and a subclass of the set of all reverse circulant matrices. We define some algorithms for fast computation of the product between a γ -matrix and a real vector. We proved that the computational cost of a multiplication between a γ -matrix and a real vector is of at most 74nlog2n+o(nlog2n) additions and 12nlog2n+o(nlog2n) multiplications. Our algorithm can be used to improve the performance of general discrete transforms for multiplications of real vectors.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.
