Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform

摘要

This paper explores the performance of a family of algorithms for computing the Walsh-Hadamard transform, a useful computation in signal and image processing. Recent empirical work has shown that the family of algorithms exhibit a wide range of performance and that it is non-trivial to determine which algorithm is optimal on a given computer. This paper provides a theoretical basis for the performance distribution. Performance is modeled by a family of recurrence relations that determine the number of instructions required to execute a given algorithm, and the recurrence relations can be used to explore the performance of the space of algorithms. The recurrence relations are related to standard divide and conquer recurrences, however, there are a variable number of recursive parts which can grow to infinity as the input size increases. Thus standard approaches to solving such recurrences cannot be used and new techniques must be developed. In this paper, the minimum, maximum, expected values, and variances are calculated and the limiting distribution is obtained.