快速算法

第一章  卷積的快速算法                  
 1  卷積及其等價形式                  
 2  用分段循環(huán)卷積實現(xiàn)數(shù)字濾波                  
 2. 1  重疊保留法                  
 2. 2  重疊相加法                  
 3  短卷積的快速算法                  
 3. 1 Cook-Toom短卷積算法                  
 3. 2 Winograd短卷積算法                  
 3. 3  復數(shù)卷積及一般環(huán)中的卷積                  
 4  長卷積的計算                  
 4. 1  Agarwal-Cooley算法                  
 4. 2  分裂嵌套算法                  
 4. 3  迭代算法                  
 5  多維卷積的計算                  
 5. 1  多維循環(huán)卷積的計算                  
 5. 2  多維線性卷積的計算                  
 6  卷積的并行計算                  
 6. 1  基于直接計算的并行算法                  
 6. 2  快速算法的并行處理                  
 7  卷積的計算復雜性                  
 7. 1  算法和計算復雜性                  
 7. 2  矩陣乘向量的乘法次數(shù)下界                  
 7. 3  卷積的乘法復雜性                  
 附錄A  短循環(huán)卷積的Winograd算法                  
 附錄B  短多項式乘積算法                  
 參考文獻                  
 第二章  離散富里葉變換及其快速算法                  
 1  一維離散富里葉變換                  
 1. 1  離散富里葉變換的性質                  
 1. 2  特殊序列的離散富里葉變換                  
 2  離散富里葉變換的快速算法                  
 2. 1  Cooley-TukeyFFT算法                  
 2. 2  基-2FFT算法                  
 2. 3  基-4FFT算法                  
 3  Rader-BrennerFFT算法                  
 3. 1  Rader-BrennerFFT算法                  
 3. 2  簡化DFT的快速算法                  
 3. 3  實因子算法                  
 4  PreussFFT算法                  
 5  基-3FFT新算法                  
 6  多項式算法                  
 6. 1  Goertzel算法                  
 6. 2  z變換算法                  
 6. 3  遞歸割圓分解算法(RCFA)                  
 7  分裂基算法(SRFFT)                  
 8  快速富里葉變換的統(tǒng)一表示及并行計算                  
 8. 1  kronecker乘積及完全混合算子                  
 8. 2  富里葉變換矩陣的分解                  
 8. 3  FFT的并行計算                  
 8. 4  逆序置換矩陣的分解                  
 9  二維離散富里葉變換及其快速算法                  
 9. 1  二維DFT的行列算法                  
 9. 2  二維DFT的向量基算法                  
 10  DFT在計算卷積中的應用                  
 參考文獻                  
 第三章  素因子算法(FPT)和Winograd富里葉變換算法(WFTA)                  
 1  Bluestein算法                  
 2  Rader算法                  
 2. 1  N=p尹的Rader算法                  
 2. 2  N=pc的復合算法                  
 2. 3  N＝2l的Rader算法                  
 3  Winograd小NDFT算法                  
 4  素因子FFT算法(FPA)                  
 4. 1  一維DFT的多維映射                  
 4. 2  Good-Thomas素因子算法                  
 4. 3  分裂素因子算法                  
 5  Winograd富里葉變換算法(WFTA)                  
 5. 1  二維DFT的嵌套算法                  
 5. 2  Winograd富里葉變換算法(WFTA)                  
 5. 3  FPA和WFTA的混合算法                  
 5. 4  Johnson-Burrus富里葉變換算法(JBFTA)                  
 附錄  Winograd小NDFT算法                  
 參考文獻                  
 第四章  多項式變換及其應用                  
 1  多項式變換的引進                  
 2  有理數(shù)域上的多項式變換                  
 2. 1  一維多項式變換                  
 2. 2  二維及多維多項式變換                  
 3  快速多項式變換一FPT                  
 3. 1  一維快速多項式變換(FPT)                  
 3. 2  FPT在計算機上的實現(xiàn)                  
 3. 3  二維快速多項式變換(2D-FPT)                  
 4  二維數(shù)字卷積的多項式變換算法                  
 4. 1  二維循環(huán)卷積的FPT算法及其在計算機上的實現(xiàn)                  
 4. 2  二維循環(huán)卷積FPT算法的改進                  
 4. 3  任意長二維循環(huán)卷積的多項式變換算法                  
 5  一維數(shù)字卷積的多項式變換算法                  
 5. 1  多項式乘積的FPT算法                  
 5. 2  一維循環(huán)卷積的FPT算法                  
 6  二維離散富里葉變換的多項式變換算法                  
 6. 1  p×p二維DFT的多項式變換算法                  
 6. 2  2l×2 二維DFT的FPT算法及其在計算機上                  
 的實現(xiàn)                  
 6. 3  任意長二維DFT的多項式變換算法                  
 參考文獻                  
 第五章  其它離散變換及其快速算法                  
 1  各類離散余弦變換和正弦變換及其相互關系                  
 1. 1  各類DCT和DST及其相互關系                  
 1.  2  DFT的DCT算法                  
 2  離散余弦變換的快速算法                  
 2. 1  一維DCT的快速算法                  
 2. 2  二維DCT的快速算法                  
 3  離散w變換及其快速算法                  
 3. 1  w變換及其基本性質                  
 3. 2  用余弦正弦變換計算DWT                  
 3. 3  直接分解算法                  
 4  廣義離散富里葉變換(GFT)及其快速算法                  
 4. 1  廣義離散富里葉變換及其逆變換                  
 4. 2  GFT的快速算法                  
 5  DWT與GFT在卷積計算中的應用                  
 5. 1  用DHT計算循環(huán)卷積                  
 5. 2  用GFT和DWT計算斜循環(huán)卷積                  
 參考文獻                  
 第六章  格和樹的搜索算法                  
 1  格和樹                  
 2  動態(tài)規(guī)劃和Witerbi算法                  
 3  回溯法和Fano算法                  
 4  堆棧算法                  
 參考文獻                  
 第七章  有關Toeplitz矩陣快快速算法                  
 1  Toeplitz矩陣求逆的快速算法                  
 1. 1  k循環(huán)矩陣求逆的FFT算法                  
 1. 2  Toeplitz矩陣求逆的Trench算法                  
 2  分塊Toeplitz矩陣求逆的快速遞歸算法                  
 3  求解Toeplitz系統(tǒng)的Bareiss變換法以及Levinson算法                  
 4  求解一般Toeplitz系統(tǒng)的一種超快速算法                  
 5  求解對稱正定Toeplitz系統(tǒng)的預條件共軛梯度算法(PCGM)                  
 6  Toeplitz矩陣相乘的快速算法                  
 參考文獻