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

DOI10.1016/j.tcs.2005.09.074zbMath1086.68151OpenAlexW2010311111MaRDI QIDQ818111

Hung-Jen Huang, Jeremy R. Johnson, Pawel Hitczenko

Publication date: 24 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.074

zbMATH Keywords

martingalescentral limit theoremWalsh-Hadamard transformrandom compositionsalgorithm search spaceautomated performance tuningdivide and conquer recurrencesperformance models

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computing methodologies for image processing (68U10) Application of orthogonal and other special functions (94A11)

Related Items

Unnamed Item

Uses Software

• ATLAS
• SPIRAL
• UHFFT
• FFTW
• PHiPAC

Cites Work

• A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures
• Analytic variations on quadtrees
• An asymptotic theory for recurrence relations based on minimization and maximization.
• Distinctness of compositions of an integer: A probabilistic analysis
• Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
• Improved master theorems for divide-and-conquer recurrences
• A limiting distribution for quicksort
• On the Multiplicity of Parts in a Random Composition of a Large Integer
• A limit theorem for “quicksort”
• Computational Science - ICCS 2001. International conference, San Francisco, CA, USA, May 28--30, 2001. Proceedings. Part 2
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item