论文标题
更快的walsh-hadamard和离散的傅立叶转换来自基质非rigities
Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity
论文作者
论文摘要
我们给出了Walsh-Hadamard Transform（WHT）的算法计数较低的算法和2 $ n $的输入的离散傅立叶变换（DFT）。 对于WHT，我们的新算法的操作计数为$ \ frac {23} {24} n \ log n + n + o（n）$。据我们所知，这给出了简单，民俗快速walsh-Hadamard变换算法的$ n \ log n $操作数量的首次改进。 对于DFT，我们的新FFT算法使用$ \ frac {15} {4} n \ log n + n + o（n）$真实的算术操作。我们的领先常数$ \ frac {15} {4} = 3.75 $从1965年起的cooley-tukey算法的$ 5 $上提高了$ 5 $，从1968年的Yavne的split-radix算法中带来了$ 4 $，从1968年起，从1968年开始，从而导致了常数$ \ frac {34} {34} {34} {34} {34} {3.77 = 3.77 = 3.77 = 3.77 nirction $;由Van Buskirk撰写，从2004年起，从2017年开始，Sergeev的理论优化版本的Van Buskirk的算法从Constant of Constant $ 3.76875 $。 我们的新WHT算法利用了有关WHT非基因的最新工作：我们将WHT矩阵分解为低级别基质和稀疏矩阵的总和，然后分析这些矩阵的结构以实现较低的运行计数。我们的新DFT算法来自一种新颖的减少，表明可以通过对WHT算法的调用来代替以前最佳FFT算法的一部分。用我们的新算法替换算法的民间传说会导致我们改善的FFT。
We give algorithms with lower arithmetic operation counts for both the Walsh-Hadamard Transform (WHT) and the Discrete Fourier Transform (DFT) on inputs of power-of-2 size $N$. For the WHT, our new algorithm has an operation count of $\frac{23}{24}N \log N + O(N)$. To our knowledge, this gives the first improvement on the $N \log N$ operation count of the simple, folklore Fast Walsh-Hadamard Transform algorithm. For the DFT, our new FFT algorithm uses $\frac{15}{4}N \log N + O(N)$ real arithmetic operations. Our leading constant $\frac{15}{4} = 3.75$ improves on the leading constant of $5$ from the Cooley-Tukey algorithm from 1965, leading constant $4$ from the split-radix algorithm of Yavne from 1968, leading constant $\frac{34}{9}=3.777\ldots$ from a modification of the split-radix algorithm by Van Buskirk from 2004, and leading constant $3.76875$ from a theoretically optimized version of Van Buskirk's algorithm by Sergeev from 2017. Our new WHT algorithm takes advantage of a recent line of work on the non-rigidity of the WHT: we decompose the WHT matrix as the sum of a low-rank matrix and a sparse matrix, and then analyze the structures of these matrices to achieve a lower operation count. Our new DFT algorithm comes from a novel reduction, showing that parts of the previous best FFT algorithms can be replaced by calls to an algorithm for the WHT. Replacing the folklore WHT algorithm with our new improved algorithm leads to our improved FFT.
