Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables

Josh Alman

Abstract

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^\omega)$ operations can be converted into an algorithm using $O(N^\omega / (\log N)^{\omega/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.

Introduction

In computational complexity, the efficiency of algebraic algorithms is traditionally measured by the number of arithmetic operations (additions and multiplications) required. Under this arithmetic model, the Fast Walsh-Hadamard Transform (WHT) is widely considered to have a lower bound of $\Omega(N \log N)$, and matrix multiplication is constrained by the exponent $\omega$. However, this model does not fully capture the capabilities of modern hardware, which can perform bitwise operations and utilize memory for lookup tables.

This paper explores the potential of the bit-operations model to surpass these traditional arithmetic lower bounds. By focusing on constant-sized finite fields (such as $\mathbb{F}_2$), we demonstrate that precomputing small sub-problems and storing them in lookup tables can yield asymptotic speedups for fundamental algebraic tasks.

Methodology: The "Precompute and Jump" Strategy

The core algorithmic strategy employed is a "precompute and jump" approach, which shares conceptual roots with the "Method of Four Russians." The methodology consists of three primary phases:

  1. Lookup Table Precomputation: The algorithm identifies a sub-problem size small enough that all possible inputs can be exhaustively precomputed. For a vector of length $K$ or a matrix of size $S \times S$, the results of the operation are stored in a table. Over a constant-sized finite field $\mathbb{F}_q$, the number of possible inputs is small enough that this table can be constructed in sub-linear time relative to the total problem size $N$.
  2. Modified Recursion:
    • For WHT: The algorithm utilizes Yates' algorithm, a standard recursive approach for Kronecker powers. Instead of recursing to the base case of a single element, the recursion terminates at size $K$. The algorithm then "jumps" through the final $K$ layers by retrieving the precomputed result from the lookup table.
  3. For Matrix Multiplication: The algorithm adapts existing fast algebraic methods (e.g., Strassen’s algorithm). Recursion is halted when sub-matrices reach size $S \times S$, at which point the product is retrieved from the precomputed table.
  4. Bit Operations Analysis: The complexity is evaluated based on the number of bit operations, where the cost of a lookup is proportional to the number of bits in the key and the retrieved value.

Key Results

Walsh-Hadamard Transform

The standard Fast WHT requires $O(N \log N)$ arithmetic operations. By applying the lookup table method, we improve the bit-complexity to $O(N \log N / \log \log N)$. This result is not limited to the WHT; it generalizes to any linear transform that can be expressed as a Kronecker power of a fixed matrix.

Matrix Multiplication

Any algebraic matrix multiplication algorithm with an exponent $\tau$ (where $O(N^\tau)$ is the arithmetic complexity) can be transformed into a bit-operation algorithm with a complexity of $O(N^\tau / (\log N)^{\tau/2 - 1})$.

Specific improvements include:

  • Strassen’s Algorithm: Complexity is reduced from $O(N^{2.81})$ to $O(N^{2.81} / (\log N)^{0.4})$.
  • State-of-the-Art Algorithms: For the current fastest known exponent $\tau \approx 2.373$, the complexity becomes $O(N^{2.373} / (\log N)^{0.186})$.

Discussion and Theoretical Implications

Breaking the Arithmetic Barrier

The most significant theoretical insight is that arithmetic circuit lower bounds do not necessarily apply to bit-complexity. By using $O(b)$ bit operations for a single lookup, the algorithm effectively executes multiple arithmetic operations simultaneously. This suggests that proving lower bounds for these problems is inherently difficult; any such proof must be "lookup table aware." If a proof technique does not account for the possibility of lookup tables, it cannot be used to establish a lower bound that exceeds these new upper bounds.

Limitations

Despite the asymptotic gains, there are practical and model-specific constraints:

  • Word RAM Model: For the WHT, the speedup does not currently translate to the standard word RAM model. The overhead required to permute bits into the correct format for a lookup table entry ($O(N)$ time) currently offsets the savings gained from the table itself.
  • Field Size Dependency: The advantage of this method is most pronounced in constant-sized fields. As the field size $q$ grows relative to $N$, the size of the required lookup table increases exponentially, eventually diminishing the "super-constant" benefit.
  • Practical Implementation: While the asymptotic win is clear, the constant factors associated with table management and memory access mean these algorithms may only outperform traditional methods at extremely large values of $N$.

Summary updated

Abstract

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^\omega)$ operations can be converted into an algorithm using $O(N^\omega / (\log N)^{\omega/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.
BibTeX
@inproceedings{alman2023faster,
  author = {Josh Alman},
  title = {{Faster Walsh-Hadamard Transform and Matrix Multiplication over Finite Fields using Lookup Tables}},
  booktitle = {SOSA},
  year = {2023},
  doi = {10.1137/1.9781611977585.ch13},
}

Loading related content...

Figure