%T Optimizing the Dimensional Method for Performing Multidimensional, Multiprocessor, Out-of-Core FFTs
%A Jeremy T. Fineman
%R Technical Report TR2001-402
%I Dartmouth College, Computer Science
%C Hanover, NH
%D June 2001
%U http://www.cs.dartmouth.edu/reports/TR2001-402.ps.Z
%X
     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.
%Z
 Senior Honors Thesis.  Advisor: Tom Cormen.