What are 'Butterfly Combinations' and why are they called this way? In some scientific work describing Discrete Fourier Transform-algorithms, such as the well-known Cooley-Tukey algorithm, I came across the term 'Butterfly operations' and 'Butterfly combinations', which seem to refer to the fact that an algorithm takes elements that are half an array away (where the array itself is a power-of-two in size), which mean that if you want to write an iterative implementation, that you will have to bit-reverse the indices of the input (or the output).

Is this indeed what is called 'Butterfly combinations'? And why are these called 'Butterfly combinations'? What is the origin of this name?
So, a summary of the Wikipedia page on Butterfly Diagrams:


In Computing Science, a Butterfly is the portion of a computation that combines the results of (two) smaller computations into the larger one.
This is common in Discrete Fourier Transformation algorithms, as well as in the otherwise unrelated Viterbi Algorithm for finding the most likely sequence of hidden states.
It is called 'Butterfly' because of how it works in the base case where you combine two single-point results: (Image courtesy of Wikipedia)
The earliest occurrence in print of the term 'Butterfly' is thought to be in a 1969 MIT technical report: C. J. Weinstein (1969-11-21). Quantization Effects in Digital Filters.