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 an FFT algorithm. With our algorithm we achieve a speedup of a factor of about 2.25 for the multiplication of two polynomials with integer coefficients compared to multiplication by an FFT algorithm. Moreover this paper discusses multiplication of large integers as further application.

翻译：本文涉及环流矩阵。 事实表明, 在不使用 FFT 算法的情况下, 圆流矩阵可以在一个具有团结根基的环状圈内, 以O(n log(n)) 时间乘以矢量乘以O( n log(n) ) 。 我们的算法可以实现约2. 25 倍增系数, 使两个多倍数系数的乘法与FFFT 算法的乘法相乘。 此外, 本文还讨论大整数的乘法作为进一步应用。