假设现在有2个矩阵a和b，分别是n行m列和x行y列，现在你要计算它们的二维卷积，也就是求出矩阵s满足：
\(s_{i,j}=\sum_{i'\leq i,j'\leq j}a_{i',j'}b_{i-i',j-j'}\)
先把两个矩阵的行数都扩展到不小于n+x的最小2的次幂数，列数同理，这个跟普通FFT一样。接下来分5步：
1.对a和b的每一行分别做普通DFT
2.对a和b的每一列分别做普通DFT
3.新建矩阵s，\(s_{i,j}=a_{i,j}b_{i,j}\)
4.对s的每一列分别做普通IDFT(别忘了做完之后乘上每列长度的逆元)
5.对s的每一行分别做普通IDFT(别忘了做完之后乘上每行长度的逆元)
然后s就是要求的结果了
标签：IDFT,DFT,FFT,矩阵,普通,笔记,二维 From： https://www.cnblogs.com/legendstane/p/16612715.html