Husband-Wife Research Team Presents Work
Heidi and Steve Haynal study a mathematical tool
Heidi Haynal, mathematics professor at Walla Walla University, along with her husband, Dr. Steve Haynal, recently presented their findings on Discrete Fourier Transform, which is a mathematical tool commonly used in engineering and computer science to analyze and manipulate images and sounds.
After researching DFT, the Haynals found the minimum number of multiplications and additions necessary for certain classes of the DFT, and provided instances of these algorithms.
“We concluded that satisfiability solvers can be used to explore a rich family of algorithms that implement the Discrete Fourier Transform,” says Heidi. “Our lower bounds result answers an academic question, but we uncovered several new open questions to explore in future research.” Some of the Haynal's findings surprised them.
“Even though the Discrete Fourier Transform has been a well-studied subject since the late 1960s, no one has proved bounds on algorithm complexity,” Heidi explains. “We were surprised to be able to prove some such bounds and find instances of new algorithms with lower multiplication and addition counts than the best known.
”At the beginning, Heidi said that she and her husband did not plan to do the project together. They first became interested when Steve was using the DFT in a project involving harmonic analysis of sound. “He was curious about the inner workings of the DFT algorithm and noticed that techniques he used at Intel could be, but had never been, applied to exploring families of these algorithms,” says Heidi.
The Haynals presented their findings at the Ninth International Workshop on Satisfiability Modulo Theories held in Snowbird, Utah, this last summer. They have also presented their findings at Intel, the University of California at Santa Barbara, and WWU. The Haynals’ research is also scheduled to be published in the Journal of Satisfiability, Boolean Modeling and Computation.
“Although the initial result came in a matter of months, we slaved for more than a year on preparing and polishing our final paper,” says Heidi. “It is satisfying to discover something new and receive affirmation from fellow experts. But really, we think it’s downright fun to work on solving the research puzzle.”