jornada / swifft

Swift Wavelet-based Inexact Fast Fourier Transform

SWIFFT - Swift Wavelet-based Inexact FFT

Copyright (C) 2011 Felipe H. da Jornada [email protected]

• Author: Felipe H. da Jornada [email protected]
• Created: 2011 December 09
• Keywords: C FFT FFTW Wavelet Approximate Inexact
• URL: http://github.com/jornada/swifft

Licensed under the GPL version 2 or later.

What is it?

SWIFFT is a library that implements an approximate Fast Fourier Transform (FFT) using Discrete Wavelet Transforms, and it is designed to be a drop-in replacement for FFTW calls. Depending on the approximation trade-off and input signal, SWIFFT can be more than twice as fast as the exact FFT algorithms.

Details

SWIFFT is a library that implements an approximate Fast Fourier Transform (FFT) using Discrete Wavelet Transforms, which is based on the algorithm developed by H. Guo and C. S. Burrus [1].

SWIFFT uses an efficient hybrid pruning scheme that mixes approximate FFT routines with high performance exact FFTs implemented in FFTW. The code can approximate FFTs in a controllable way, and the approximate algorithm is usually faster than the exact ones generated by FFTW.

The user has the freedom to choose the wavelet filter and the degree of pruning, so that one can choose the best approximation scheme for a particular problem.

[1] H. Guo and C. S. Burrus, Wavelet transform based fast approximate Fourier transform. 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing, v. 3, pp. 1973--1976 (1997).

Licensing

SWIFFT Copyright (C) 2011 Felipe H. da Jornada [email protected]

SWIFFT is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version.

SWIFFT is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with SWIFFT; see the file COPYING. If not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.