威诺格拉德快速傅里叶算法(英语:Winograd FFT)是由美国计算机科学家Shmuel Winograd在1978年提出。此算法可以找出最少的乘法运算量。
当把DFT的公式:
用矩阵方式来表示:
如果n是质数,则可以无视第一行与第一列,把n点的DFT用n-1点的回旋折积来取代。
使用此算法,可分为以下几个步骤,此处以n=5的DFT为例:
Step 1:消去第一行与第一列,式子可以改写如下:
Step 2:找出列与行的顺序:
a)找出一个原根 a,使得 .
b)用p[n]表示列与行的顺序:
在这例子中,N=5有两个原根:2与3。取2作为其原根,可得其顺序为:1,2,4,3。
故要将此矩阵 的第三列与第四列交换,第三行与第四行交换,把矩阵变成如下:
如此第一行与第一列都跟所求得的顺序:1,2,4,3一样,此为circular correlation的形式。
Step 3:为了要符合回旋折积的定义(矩阵的对角线的项数相同),故必须再将第二列与第四列交换,第二行与第四行交换,矩阵如下:
如此就可把N点DFT用N-1点的DFT来简化,表示如下: