《快速算法》求取 ⇩

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 快速多项式变换-FPT307

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 用余弦正弦变换计算DWT437

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