Looking for Patterns
Mathematics Professor Studies Widely Used Algorithm
By: Camlynne Waring
One might say the Haynals are a left-brain couple. Heidi Haynal is a mathematician and associate professor at Walla Walla University. Steve Haynal is an engineer, who manages a small business in addition to teaching WWU courses. Together, they have published a paper at the the Institute of Electrical and Electronic Engineer’s May 2013 International Conference on Acoustics, Speech, and Signal Processing, held in Vancouver, B.C., Canada. This paper continues the Haynals' recent research focus on the Fast Fourier Transform, and is their third peer-reviewed paper on this theme in the past two years.
“While Steve was working on an engineering project to analyze singing, he came up with a new way of looking at the FFT,” says Heidi. “He asked me for help with the mathematics to describe what he was finding out. Since I enjoy working on puzzles and hard problems, I've continued to help with this research.”
The Fast Fourier Transform, or FFT, is a mathematical algorithm widely used in engineering and computer science to do such things as detect edges in images, add artificial reverberation to recorded sound, and detect oil underground by analyzing reflected sound. The Haynals' specific contributions are currently theoretical and establish bounds on the complexity of the FFT as well as enumerate all variations of the FFT under certain constraints. “We were surprised to find undiscovered instances of FFT algorithms, even though this field has been studied intensely for almost 40 years,” say the Haynals.
Their research has been noticed by established experts in the field as well. Steven Johnson, professor at MIT and co-author of perhaps the most widely used FFT software library, FFTW, called the Haynals' research "an unusual approach to this problem" and has mentioned it on Wikipedia's FFT page.
The Haynals enjoy the patterns and puzzles they find in the FFT, and are continuing their research this summer by attempting to describe their new FFT instances with abstract algebra. “Currently, we can find new instances of small FFTs with a very random character,” says Heidi. “By applying abstract algebra, this summer we hope to find FFTs that are more regular and that can be described easily and succinctly even for large problem sizes.”