Characterizing And Enumerating Walsh-hadamard Transform Algorithms

Serre François, Püschel Markus. Arxiv 2017

[Paper]    
ARXIV Independent

We propose a way of characterizing the algorithms computing a Walsh-Hadamard transform that consist of a sequence of arrays of butterflies ($I_{2^{n-1}}\otimes {\text{DFT}}_2$) interleaved by linear permutations. Linear permutations are those that map linearly the binary representation of its element indices. We also propose a method to enumerate these algorithms.

Similar Work

• Permutation Search Methods Are Efficient Yet Faster Search Is Possible
• C-OPH Improving The Accuracy Of One Permutation Hashing (OPH) With Circulant Permutations
• One Permutation Hashing
• A Sparse Johnson-lindenstrauss Transform Using Fast Hashing