A very efficient C package for computing the Walsh-Hadamard transform (WHT) of arbitrary size 2n. The package is adaptable, i.e., it optimizes itself to the computing platform where it is installed. The package easily installs (configure - make) on Unix/Linux platforms including SMP platforms.
The WHT (Walsh-Hadamard transform) of size 2n is defined as the matrix-vector multiplication WHT(2n)*x, wherewhere
denotes the 2-point DFT. We compute the WHT by using different recursive breakdown strategies. Combination of these strategies yields a large number of different breakdown trees corresponding to different algorithms. These algorithms differ in their data access during computation, but have all the same arithmetic cost (exactly n * 2n for a WHT(2n)). We adapt the package by searching in this algorithm space for the best match to the given computing platform. For more information we refer to the README file in the package. The design of our WHT package is based on an FFT package by Sebastian Egner.
Have a look at the best trees and runtimes for different architectures, found using dynamic programming. Note the big differences: the best trees are very platform-dependent.
|v1.8||05/16/03||Minor memory leakage removed.|
|v1.7||04/02/02||Support for multiprocessor machines using OpenMP.|
|v1.6||03/01/02||Ported to Mac OS X (Darwin). Benchmark tool added.|
|v1.5||01/22/02||Loop interleaving extended to five levels.|
|v1.4||12/03/01||Loop interleaving added. Measure method changed|
|v1.3||12/05/00||Better installation on alphas|
|v1.2||11/21/00||New split method "splitddl" integrated|
|v1.1||08/08/00||Pcl profiling added|
|v1.0||08/01/00||Bug removed which affects left expanded trees; simpler, automated installation and genetic algorithm added.|
|v0.0||05/10/99||First version of WHT package released.|