On Fast Computation of a Circulant Matrix-Vector Product

Andreas Rosowski

This paper deals with circulant matrices. It is shown that a circulant matrix can be multiplied by a vector in time O(n log(n)) in a ring with roots of unity without making use of…