Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity
Faster Walsh-Hadamard and Discrete Fourier Transforms from Matrix Non-rigidity
复制标题
来自矩阵非刚性的更快 Walsh-Hadamard 和离散傅立叶变换
DOI：
10.1145/3564246.3585188
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Rao, Kevin
中科院分区：
文献类型：
--
作者：
Alman, Josh;Rao, Kevin
对于输入为2的幂次N的Walsh-Hadamard变换（WHT）和离散傅里叶变换（DFT），我们给出了运算量更小的算法，对于WHT，我们的新算法的运算量为23/24 NlogN +O（N）.这是对传统快速Walsh-Hadamard变换算法的NlogN运算量的首次改进，对于DFT，新的FFT算法使用了15/4 NlogN +O（N）真实的算术运算。我们的前导常数15/4 = 3.75改进了1965年Cooley-Tukey算法的前导常数5，1968年Yavne的分裂基数算法的前导常数4，2004年货车Buskirk对分裂基数算法的修改的前导常数34/9=3.7777，和领先常数3.76875从理论上优化版本的货车Buskirk的算法由Sergeev从2017年。我们的新WHT算法利用了最近的工作线上的非刚性的WHT：我们将WHT矩阵分解为低秩矩阵和稀疏矩阵的和，然后分析这些矩阵的结构，以实现更低的运算量。我们的新DFT算法来自一个新的减少，表明以前最好的FFT算法的部分可以被替换为调用的WHT算法。用改进的FFT算法代替传统的WHT算法，得到改进的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 sizeN.For the WHT, our new algorithm has an operation count of 23/24NlogN+O(N). To our knowledge, this gives the first improvement on theNlogNoperation count of the simple, folklore Fast Walsh-Hadamard Transform algorithm.For the DFT, our new FFT algorithm uses 15/4NlogN+O(N) real arithmetic operations. Our leading constant 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 34/9=3.7777 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.
登录
查看更多内容
矩阵刚度的最新进展 - 一项调查
DOI：
--
发表时间：
2020
期刊：
arXiv.org
影响因子：
--
作者：
C. Ramya
通讯作者：
C. Ramya
克罗内克积、低深度电路和矩阵刚性
DOI：
--
发表时间：
2021
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Josh Alman
通讯作者：
Josh Alman
DOI：
10.1145/3055399.3055484
发表时间：
2016
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Josh Alman;Richard Ryan Williams
通讯作者：
Richard Ryan Williams
关于复杂 DFT 的真实复杂性
影响因子：
1.2
作者：
I. Sergeev
通讯作者：
I. Sergeev
使用矩阵熵的 2x2 酉门线性模型中傅里叶变换计算的下界
DOI：
--
发表时间：
2013
期刊：
Chicago journal of theoretical computer science
影响因子：
--
作者：
Nir Ailon
通讯作者：
Nir Ailon