On computing the Discrete Fourier Transform.
New algorithms for computing the Discrete Fourier Transform of n points are described. For n in the range of a few tens to a few thousands these algorithms use substantially fewer multiplications than the best algorithm previously known, and about the same number of additions.
IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York 10598.
S
S
Winograd