Example: Two Butterfly Algorithms


This is an example of efficient prototyping of recurrences used on algorithms that exhibit a butterfly dependency pattern.

The butterfly is a graph with a regular pattern, but the pattern depends on the position in and size of the butterfly. A height 4 butterfly looks like

Butterfly graph (height 4)

A butterfly of height h will have h+1 rows (indexed 0 through h) and 2^h columns (indexed 0 through 2^h-1). A node is identified by index pairs in the the row-column order, thus for a height h butterfly we will be using indices in the range <0,0>; through <h,2^h-1>. A precise definition of the butterfly is given by the following:

Replicated sum

Assume that the 0'th row of the butterfly has been assigned some number. The replicated sum will add these numbers together, so that each node at the top will receive a copy of the sum. The intermediate nodes will contain various subsums.

sum(p) = sum(D(p,1)) + sum(D(p,2))

Fast Fourier Transform

The fast Fourier transform, the FFT, is a standard algorithm which utilises the butterfly structure fully. The inputs are placed on the bottom row, and the outputs appear on the top row.

fft(p) = fft(D(p,1)) + exp(a*row(p)/(2**col(p)))*fft(D(p,2))

The total execution time is n log n, where n=2^h is the number of input nodes, as expected of the FFT algorithm.


This was an example of efficient prototyping of recurrences.
1997 Magne Haveraaen, University of Bergen, Norway.