快速算法PDF电子书下载

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