论文标题
更快的Walsh-Hadamard转换和矩阵乘法使用有限字段使用查找表
Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables
论文作者
论文摘要
我们使用查找表来设计更快的算法，以解决有限字段的重要代数问题。这些更快的算法仅使用算术操作和查找表操作，可能有助于解释确定这些重要问题复杂性的困难。我们在恒定有限场上的结果如下。 可以使用$ o（n \ log n / \ log \ log \ log n）$ bit Operations计算长度$ n $的向量的walsh-hadamard变换。这将概括为定义为固定矩阵的Kronecker功率的任何变换。相比之下，快速的Walsh-Hadamard变换（类似于快速傅立叶变换）使用$ O（n \ log n）$算术操作，据信这是最佳的，直到恒定因素。 使用$ O（n^ω）$操作乘以两个$ n \ times n $矩阵的任何代数算法都可以使用$ o（n^ω/（\ log n）^{ω/ 2-1-1}）$ bit Operations转换为算法。例如，可以使用$ o（n^{2.81} /（\ log n）^{0.4}）$ bit操作将Strassen的算法转换为算法。确定最小的常数$ c $，这仍然是一个开放的问题，以便可以实现strassen的算法来使用$ c \ cdot n^{2.81} + o（n^{2.81}）$ arithmetic操作；使用查找表可以在位操作中保存一个超稳定因子。
We use lookup tables to design faster algorithms for important algebraic problems over finite fields. These faster algorithms, which only use arithmetic operations and lookup table operations, may help to explain the difficulty of determining the complexities of these important problems. Our results over a constant-sized finite field are as follows. The Walsh-Hadamard transform of a vector of length $N$ can be computed using $O(N \log N / \log \log N)$ bit operations. This generalizes to any transform defined as a Kronecker power of a fixed matrix. By comparison, the Fast Walsh-Hadamard transform (similar to the Fast Fourier transform) uses $O(N \log N)$ arithmetic operations, which is believed to be optimal up to constant factors. Any algebraic algorithm for multiplying two $N \times N$ matrices using $O(N^ω)$ operations can be converted into an algorithm using $O(N^ω/ (\log N)^{ω/2 - 1})$ bit operations. For example, Strassen's algorithm can be converted into an algorithm using $O(N^{2.81} / (\log N)^{0.4})$ bit operations. It remains an open problem with practical implications to determine the smallest constant $c$ such that Strassen's algorithm can be implemented to use $c \cdot N^{2.81} + o(N^{2.81})$ arithmetic operations; using a lookup table allows one to save a super-constant factor in bit operations.
