BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR2001-402
ENTRY:: June 02, 2001
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Optimizing the Dimensional Method for Performing Multidimensional, Multiprocessor, Out-of-Core FFTs
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Fineman, Jeremy T.
DATE:: June 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-402.ps.Z
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR2001-402.pdf
ABSTRACT:: 
    We present an improved version of the Dimensional Method for computing
multidimensional Fast Fourier Transforms (FFTs) on a multiprocessor
system when the data consist of too many records to fit into
memory. Data are spread across parallel disks and processed in
sections. We use the Parallel Disk Model for analysis.
    The simple Dimensional Method performs the 1-dimensional FFTs for
each dimension in term. Between each dimension, an out-of-core
permutation is used to rearrange the data to contiguous locations.
The improved Dimensional Method processes multiple dimensions at a
time.
    We show that determining an optimal sequence and groupings of
dimensions is NP-complete. We then analyze the effects of two
modifications to the Dimensional Method independently: processing
multiple dimensions at one time, and processing single dimensions in a
different order.
    Finally, we show a lower bound on the I/O complexity of the
Dimensional Method and present an algorithm that is approximately
asymptotically optimal.
NOTE:: 
Senior Honors Thesis.  Advisor: Tom Cormen.
END:: ncstrl.dartmouthcs//TR2001-402