1 卷积及其等价形式 2
第一章 卷积的快速算法 2
2 用分段循环卷积实现数字滤波 5
2.1 重叠保留法 6
2.2 重叠相加法 7
3 短卷积的快速算法 8
3.1 Cook-Toom短卷积算法 8
3.2 Winograd短卷积算法 15
3.3 复数卷积及一般环中的卷积 32
4 长卷积的计算 36
4.1 Agarwal-Cooley算法 36
4.2 分裂嵌套算法 41
4.3 迭代算法 45
5 多维卷积的计算 53
5.1 多维循环卷积的计算 53
6 卷积的并行计算 56
5.2 多维线性卷积的计算 56
6.1 基于直接计算的并行算法 57
6.2 快速算法的并行处理 58
7 卷积的计算复杂性 59
7.1 算法和计算复杂性 59
7.2 矩阵乘向量的乘法次数下界 62
7.3 卷积的乘法复杂性 66
附录A 短循环卷积Winograd算法 71
附录B 短多项式乘积算法 79
参考文献 85
第二章 离散富里叶变换及其快速算法 87
1 一维离散富里叶变换 87
1.1 离散富里叶变换的性质 89
1.2 特殊序列的离散富里叶变换 94
2 离散富里叶变换的快速算法 100
2.2 基-2 FFT 算法 103
2.3 基-4 FFT 算法 108
3 Rader-Brenner FFT 算法 113
3.1 Rader-Brenner FFT 算法 113
3.2 简化DFT的快速算法 117
3.3 实因子算法 118
4 Preuss FFT 算法 123
5 基-3 FFT新算法 127
6 多项式算法 137
6.1 Goertzel算法 137
6.2 z变换算法 139
6.3 递归割圆分解算法(RCFA) 148
7 分裂基算法(SRFFT) 160
8 快速富里叶变换的统一表示及并行计算 165
8.1 kronecker乘积及完全混合算子 166
8.2 富里叶变换矩阵的分解 169
8.3 FFT的并行计算 178
8.4 逆序置换矩阵的分解 183
9 二维离散富里叶变换及其快速算法 186
9.1 二维DFT的行列算法 187
9.2 二维DFT的向量基算法 192
10 DFT在计算卷积中的应用 197
参考文献 202
第三章 素因子算法(FPT)和Winograd富里叶变换算法(WFTA) 204
1 Bluestein算法 204
2 Rader算法 207
2.1 N=p的Rader算法 207
2.2 N=Pc的复合算法 210
2.3 N=2l的Rader算法 215
3 Winograd小 N DFT算法 221
4 素因子FFT算法(FPA) 231
4.1 一维DFT的多维映射 232
4.2 Good-Thomas素因子算法 238
4.3 分裂素因子算法 242
5 Winograd富里叶变换算法(WFTA) 247
5.1 二维DFT的嵌套算法 247
5.2 Winograd富里叶变换算法(WFTA) 252
5.3 FPA 和WFTA的混合算法 260
5.4 Johnson-Burrrs富里叶变换算法(JBFTA) 262
附录 Winograd小N DFT算法 269
参考文献 275
第四章 多项式变换及其应用 278
1 多项式变换的引进 278
2 有理数域上的多项式变换 286
2.1 一维多项式变换 286
2.2 二维及多维多项式变换 302
3 快速多项式变换-FPT 307
3.1 一维快速多项式变换(FPT) 308
3.2 FPT在计算机上的实现 315
3.3 二维快速多项式变换(2D-FPT) 319
4 二维数字卷积的多项式变换算法 322
4.1 二维循环卷积的FPT算法及其在计算机上的实现 323
4.2 二维循环卷积FPT算法的改进 336
4.3 任意长二维循环卷积的多项式变换算法 349
5 一维数字卷积的多项式变换算法 354
5.1 多项式乘积的FPT算法 356
5.2 一维循环卷积的FPT算法 366
6 二维离散富里叶变换的多项式变换算法 370
6.1 p×p二维DFT的多项式变换算法 371
6.2 2t×2s二维DFT和FPT算法及其在计算机上的实现 375
6.3 任意长二维DFT的多项式变换算法 391
参考文献 397
第五章 其它离散变换及其快速算法 399
1 各类离散余弦变换和正弦变换及其相互关系 399
1.1 各类DCT和DST及其相互关系 400
1.2 DFT的DCT的算法 413
2 离散余弦变换的快速算法 415
2.1 一维DCT的快速算法 415
2.2 二维DCT的快速算法 426
3 离散W变换及其快速算法 434
3.1 W变换及其基本性质 435
3.2 用余弦正弦变换计算DWT 437
3.3 直接分解算法 446
4 广义离散富里叶变换(GFT)及其快速算法 454
4.1 广义离散富里叶变换及其逆变换 454
4.2 GFT的快速算法 455
5 DWT与GFT在卷积计算中的应用 459
5.1 用DHT计算循环卷积 459
5.2 用GFT和DWT计算斜循环卷积 462
参考文献 466
第六章 格和树的搜索算法 469
1 格和树 469
2 动态规划和Witerbl算法 472
3 回溯法和Fano算法 477
4 堆栈算法 481
参考文献 486
1 Toeplitz矩阵求逆的快速算法 487
1.1 k循环矩阵求逆的FFT算法 487
第七章 有关Toeplitz矩阵的快速算法 487
1.2 Toeplitz矩阵求逆的Trench算法 490
2 分块Toeplitz矩阵求逆的快速递归算法 497
3 求解Toeplitz系统的Bareiss变换法以及Levinson算法 504
4 求解一般Toeplitz系统的一种超快速算法 512
5 求解对称正定Toeplitz系统的预条件共轭梯度算法(PCGM) 528
6 Toeplitz矩阵相乘的快速算法 537
参考文献 549
2.1 Cooley-Tukey FFT 算法 1001