  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.

Data Structures and Algorithms;Computational Complexity