威諾格拉德快速傅立葉變換演算法 威諾格拉德快速傅立葉演算法英語Winograd FFT是由美國電腦科學家Shmuel Winograd英语Shmuel Winograd在年提出此演算法可以找出最少的乘法運算量 當把DFT的公式 y j   k   n   x k e  j  π n i k j        n   displaystyle yjsum knxkejbeginmatrixfrac pi nendmatrixikqquad jcdots n 用矩陣方式來表示  y  y   y n             w w   w n   w n          w n   w   n     w  n     n    w  n     n      x  x   x n     w  e  j  π n displaystyle beginbmatrixyyvdots ynendbmatrixbeginbmatrixcdots wwcdots wnwnvdots vdots vdots cdots vdots vdots wnwncdots wnnwnnendbmatrixbeginbmatrixxxvdots xnendbmatrixquad wejbeginmatrixfrac pi nendmatrix 如果n是質數則可以無視第一行與第一列把n點的DFT用n點的迴旋摺積來取代