BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2001-388
ENTRY:: May 24, 2001
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Applying the Vector Radix Method to Multidimensional,  Multiprocessor, Out-of-Core Fast Fourier Transforms
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Ringenburg, Michael F.
DATE:: March 2001
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: Compressed Postscript at http://www.cs.dartmouth.edu/reports/TR2001-388.ps.Z
ABSTRACT:: 
We describe an efficient algorithm for calculating Fast Fourier
Transforms on matrices of arbitrarily high dimension using the
vector-radix method when the problem size is out-of-core (i.e.,
when the size of the data set is larger than the total available
memory of the system).  The algorithm takes advantage of multiple
processors when they are present, but it is also efficient on single-processor
systems.  Our work is an extension of work done by Lauren Baptist in
[Bapt99], which applied the vector-radix method to 2-dimensional
out-of-core matrices.
      To determine the effectiveness of the algorithm, we present
empirical results as well as an analysis of the I/O, communication,
and computational complexity.  We perform the empirical tests on
a DEC 2100 server and on a cluster of Pentium-based Linux
workstations.  We compare our results with the traditional
dimensional method of calculating multidimensional FFTs, and show
that as the number of dimensions increases, the vector-radix-based
algorithm becomes increasingly effective relative to the dimensional
method.
      In order to calculate the complexity of the algorithm, it was
necessary to develop a method for analyzing the interprocessor
communication costs of the BMMC data-permutation algorithm
(presented in [CSW98]) used by our FFT algorithms.  We present
this analysis method and show how it was derived.
NOTE:: 
Masters Thesis.  Advisor: Tom Cormen.
END:: ncstrl.dartmouthcs//TR2001-388