<html>

  <head>
    <title>
      FFT_SERIAL - Fast Fourier Transform
    </title>
  </head>

  <body bgcolor="#EEEEEE" link="#CC0000" alink="#FF3300" vlink="#000055">

    <h1 align = "center">
      FFT_SERIAL <br> Fast Fourier Transform
    </h1>

    <hr>

    <p>
      <b>FFT_SERIAL</b> 
      is a FORTRAN77 program which 
      demonstrates the computation of a Fast Fourier Transform,
      and is intended as a starting point for developing a parallel version
      using OpenMP.
    </p>

    <p>
      On an Apple PowerPC G5 with two processors, the following results were
      observed:
      <table border="1" align="center">
        <tr>
          <th>N</th><th>Time</th><th>MegaFLOPS</th>
        </tr>
        <tr><td>     2</td><td>0.1134E-05</td><td>8.822</td></tr>
        <tr><td>     4</td><td>0.2358E-05</td><td>16.96</td></tr>
        <tr><td>     8</td><td>0.3859E-05</td><td>31.10</td></tr>
        <tr><td>    16</td><td>0.5845E-05</td><td>54.74</td></tr>
        <tr><td>    32</td><td>0.8674E-05</td><td>92.23</td></tr>
        <tr><td>    64</td><td>0.1886E-04</td><td>101.8</td></tr>
        <tr><td>   128</td><td>0.3590E-04</td><td>124.8</td></tr>
        <tr><td>   256</td><td>0.8220E-04</td><td>124.6</td></tr>
        <tr><td>   512</td><td>0.1629E-03</td><td>141.4</td></tr>
        <tr><td>  1024</td><td>0.3740E-03</td><td>136.9</td></tr>
        <tr><td>  2048</td><td>0.7607E-03</td><td>148.1</td></tr>
        <tr><td>  4096</td><td>0.1722E-02</td><td>142.7</td></tr>
        <tr><td>  8192</td><td>0.3535E-02</td><td>150.6</td></tr>
        <tr><td> 16384</td><td>0.8448E-02</td><td>135.8</td></tr>
        <tr><td> 32768</td><td>0.1898E-01</td><td>129.5</td></tr>
        <tr><td> 65536</td><td>0.4216E-01</td><td>124.3</td></tr>
        <tr><td>131072</td><td>0.8598E-01</td><td>129.6</td></tr>
      </table> 
    </p>

    <h3 align = "center">
      Languages:
    </h3>

    <p>
      <b>FFT_SERIAL</b> is available in
      <a href = "../../c_src/fft_serial/fft_serial.html">a C version</a> and
      <a href = "../../cpp_src/fft_serial/fft_serial.html">a C++ version</a> and
      <a href = "../../f77_src/fft_serial/fft_serial.html">a FORTRAN77 version</a> and
      <a href = "../../f_src/fft_serial/fft_serial.html">a FORTRAN90 version</a> and
      <a href = "../../m_src/fft_serial/fft_serial.html">a MATLAB version</a>.
    </p>

    <h3 align = "center">
      Related Data and Programs:
    </h3>

    <p>
      <a href = "../../f77_src/fft_openmp/fft_openmp.html">
      FFT_OPENMP</a>,
      a FORTRAN77 program which
      demonstrates the computation of a Fast Fourier Transform
      in parallel, using OpenMP.
    </p>

    <p>
      <a href = "../../f77_src/fftw3/fftw3.html">
      FFTW3</a>,
      FORTRAN77 programs which
      illustrate the use of the FFTW3 library for Fast Fourier Transforms,
      by Matteo Frigo and Steven Johnson.
    </p>

    <p>
      <a href = "../../f77_src/heated_plate/heated_plate.html">
      HEATED_PLATE</a>,
      a FORTRAN77 program which
      solves the steady state heat equation in a 2D
      rectangular region, and is intended as
      a starting point for implementing an OpenMP parallel version.
    </p>

    <p>
      <a href = "../../f77_src/md/md.html">
      MD</a>,
      a FORTRAN77 program which
      carries out a molecular dynamics simulation,
      and is intended as a starting point for developing a parallel version
      using OpenMP.
    <p>

    <p>
      <a href = "../../f77_src/mxm_serial/mxm_serial.html">
      MXM_SERIAL</a>,
      a FORTRAN77 program which
      sets up a matrix multiplication problem A=B*C,
      intended as a starting point for implementing a parallel version.
    </p>

    <p>
      <a href = "../../f77_src/openmp/openmp.html">
      OPENMP</a>,
      FORTRAN77 programs which
      illustrate the use of the OpenMP application program interface
      for carrying out parallel computations in a shared memory environment.
    </p>

    <p>
      <a href = "../../f77_src/poisson_serial/poisson_serial.html">
      POISSON_SERIAL</a>,
      a FORTRAN77 program which
      computes an approximate solution to the Poisson equation in a rectangle,
      and is intended as the starting point for the creation of a parallel version.
    </p>

    <p>
      <a href = "../../f77_src/prime_serial/prime_serial.html">
      PRIME_SERIAL</a>,
      a FORTRAN77 program which
      counts the number of primes between 1 and N,
      intended as a starting point for the creation of a parallel version.
    </p>

    <p>
      <a href = "../../f77_src/quad_serial/quad_serial.html">
      QUAD_SERIAL</a>,
      a FORTRAN77 program which
      approximates an integral using a quadrature rule,
      and is intended as a starting point for parallelization exercises.
    </p>

    <p>
      <a href = "../../f77_src/sftpack/sftpack.html">
      SFTPACK</a>
      a FORTRAN77 library which
      implements the "slow" Fourier transform, intended as a teaching
      tool and comparison with the fast Fourier transform.
    </p>

    <h3 align = "center">
      Reference:
    </h3>

    <p>
      <ol>
        <li>
          Wesley Petersen, Peter Arbenz, <br>
          Introduction to Parallel Computing - A practical guide with examples in C,<br>
          Oxford University Press,<br>
          ISBN: 0-19-851576-6,<br>
          LC: QA76.58.P47.
        </li>
        <li>
          Rohit Chandra, Leonardo Dagum, Dave Kohr, Dror Maydan,
          Jeff McDonald, Ramesh Menon,<br>
          Parallel Programming in OpenMP,<br>
          Morgan Kaufmann, 2001,<br>
          ISBN: 1-55860-671-8,<br>
          LC: QA76.642.P32.
        </li>
        <li>
          Barbara Chapman, Gabriele Jost, Ruud vanderPas, David Kuck,<br>
          Using OpenMP: Portable Shared Memory Parallel Processing,<br>
          MIT Press, 2007,<br>
          ISBN13: 978-0262533027,<br>
          LC: QA76.642.C49.
        </li>
      </ol>
    </p>

    <h3 align = "center">
      Source Code:
    </h3>

    <p>
      <ul>
        <li>
          <a href = "fft_serial.f">fft_serial.f</a>, the source code.
        </li>
        <li>
          <a href = "fft_serial.sh">fft_serial.sh</a>,
          commands to compile, link and load the program.
        </li>
      </ul>
    </p>

    <h3 align = "center">
      Examples and Tests:
    </h3>

    <p>
      <ul>
        <li>
          <a href = "fft_serial_output.txt">fft_serial_output.txt</a>,
          the output file.
        </li>
      </ul>
    </p>

    <h3 align = "center">
      List of Routines:
    </h3>

    <p>
      <ul>
        <li>
          <b>MAIN</b> is the main program for FFT_SERIAL.
        </li>
        <li>
          <b>CCOPY</b> copies a complex vector.
        </li>
        <li>
          <b>CFFT2</b> performs a complex Fast Fourier Transform.
        </li>
        <li>
          <b>CFFTI</b> sets up sine and cosine tables needed for the FFT calculation.
        </li>
        <li>
          <b>GGL</b> generates u(0,1) distributed random numbers. 
        </li>
        <li>
          <b>STEP</b> carries out one step of the workspace version of CFFT2.
        </li>
      </ul>
    </p>

    <p>
      You can go up one level to <a href = "../f77_src.html">
      the FORTRAN77 source codes</a>.
    </p>

    <hr>

    <i>
      Last revised on 16 July 2008.
    </i>

    <!-- John Burkardt -->

  </body>

  <!-- Initial HTML skeleton created by HTMLINDEX. -->

</html>
