@TechReport{baptist:fft,
  author = {Lauren M. Baptist},
  title = {Two Algorithms for Performing Multidimensional, Multiprocessor,
  Out-of-Core {FFTs}},
  year = {1999},
  month = {June},
  number = {PCS-TR99-350},
  institution = {Dept. of Computer Science, Dartmouth College},
  copyright = {Lauren M. Baptist},
  address = {Hanover, NH},
  URL = {ftp://ftp.cs.dartmouth.edu/TR/TR99-350.ps.Z},
  keywords = {parallel I/O, out of core, FFT, parallel algorithm, scientific
  computing, pario-bib},
  abstract = {We show two algorithms for computing multidimensional Fast
  Fourier Transforms (FFTs) on a multiprocessor system with distributed memory
  when problem sizes are so large that the data do not fit in the memory of the
  entire system. Instead, data reside on a parallel disk system and are brought
  into memory in sections. We use the Parallel Disk Model for implementation
  and analysis. \par The first method is a straightforward out-of-core variant
  of a well-known method for in-core, multidimensional FFTs. It performs
  1-dimensional FFT computations on each dimension in turn. This method is easy
  to generalize to any number of dimensions, and it also readily permits the
  individual dimensions to be of any sizes that are integer powers of~2. The
  key step is an out-of-core transpose operation that places the data along
  each dimension into contiguous positions on the parallel disk system so that
  the data for the 1-dimensional FFTs are contiguous.\par The second method is
  an adaptation of another well-known method for in-core, multidimensional
  FFTs. This method computes all dimensions simultaneously. It is more
  difficult to generalize to arbitrary radices and number of dimensions in this
  method than in the first method. Our present implementation is therefore
  limited to two dimensions of equal size, that are again integer powers of~2.
  \par We present I/O complexity analyses for both methods as well as empirical
  results for a DEC~2100 server and an SGI Origin~2000, each of which has a
  parallel disk system. Our results indicate that the methods are comparable in
  speed in two-dimensions.},
  comment = {Undergraduate Honors Thesis. Advisor: Tom Cormen.}
}