The SLIB Portable Scheme Library
SLIB supports Bigloo, Chez, ELK 3.0, Gambit 4.0, Gauche, Guile, JScheme, Kawa, Larceny, MacScheme, MIT/GNU Scheme, Pocket Scheme, RScheme, scheme->C, Scheme48, SCM, SCM Mac, scsh, sisc, Stk, T3.1, umb-scheme, and VSCM.Documentation includes a manifest, installation instructions, and coding standards for the library. Each library package is documented.
SLIB, Guile, Kawa, MIT/GNU Scheme, and SCM are GNU packages.
slib-3b6 is a minor release. Details at http://cvs.savannah.gnu.org/viewvc/*checkout*/slib/slib/ChangeLog
- Add a Scheme procedure to eliminate specified variables from a list of equations to the commutative-ring (symbolic algebra) package.
- Augment dft.scm to work efficiently on non-power-of-two sized arrays.
Rupinder Singh (for the GSoC) proposed a plan of work:
We start with a basic implementation of the Cooley-Tukey Algorithm. Cooley-Tukey is probably the most popular and efficient (subject to limitations) algorithm for calculating DFT. Quoting from it's Wikipedia article: "The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm". It has been successful in achiveing a complexity of O(N logN) for composite numbers. Cooley-Tukey functions by expressing, recursively, the DFT of size N as N = N1 x N2 (where N1, N2 ≥ 1).
There are a couple of improvements / pruning that can be made to this algorithm. For example, if we incorporate Chinese Remainder Theorem to choose N1 and N2, we can avoid the 'Twiddle Factors' arising as Phase terms. Also, if at any stage of the recursion N comes out to be a larger prime, the Cooley-Tukey algorithm deviates from its O(N logN) performance and moves towards a O(N2) performance. Here comes the Rader's Algorithm.
Rader's Algorithm computes the DFT of prime sizes through a cyclic convolution. The performance of this Algorithm is O(N logN) (after zero padding N to a power of 2). If a DHT (Discrete Hartley Transform) is incorporated, using modified versions of the re-indexing routine, there can be a gain factor of two (Johnson and Frigo, 2007).
Hence, the algorithm can be reasonably expected to achieve a O(1/2 N logN) performance, faster than original Cooley-Tukey Algorithm (O(N2) in prime case), Bluestein's Algorithm, Winograd's Algorithm and also better than a more recent Montium Tile-Processor (exp(N)).
Therefore, this calls for a restructuring of the existing DFT mechanism. The major changes would be introduction of a new module to implement Chinese Remainder Theorem, another for Rader's Algorithm, and then it's cyclic convolution, Optimizing it by DHT, and Finally, the encapsulating Cooley-Tukey algorithm.
I am a guest and not a member of the MIT Computer Science and Artificial Intelligence Laboratory.
My actions and comments do not reflect in any way on MIT.|
|agj @ alum.mit.edu||Go Figure!|