Journal article
Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh–Hadamard transform
Theoretical computer science, v 352(1), pp 8-30
2006
Abstract
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.
Metrics
Details
- Title
- Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh–Hadamard transform
- Creators
- Paweł Hitczenko - Department of Mathematics, Drexel University, Philadelphia, PA 19104, USAJeremy R. Johnson - Department Computer Science, Drexel University, Philadelphia, PA 19104, USAHung-Jen Huang - Department Computer Science, Drexel University, Philadelphia, PA 19104, USA
- Publication Details
- Theoretical computer science, v 352(1), pp 8-30
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science; Mathematics
- Web of Science ID
- WOS:000235826900002
- Scopus ID
- 2-s2.0-32644438406
- Other Identifier
- 991014878606204721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Theory & Methods