{
  "id": "enwiki-001374298660",
  "slug": "bailey-s-fft-algorithm",
  "title": "Bailey's FFT algorithm",
  "qid": "",
  "lead": "Bailey's FFT (also known as a 4-step FFT) is a high-performance algorithm for computing the fast Fourier transform (FFT). This variation of the Cooley–Tukey FFT algorithm was originally designed for systems with hierarchical memory, as is common in modern computers, and was the first FFT algorithm in this \"out of core\" class. The algorithm treats the samples as a two dimensional matrix (thus another name, a matrix FFT algorithm ) and executes short FFT operations on the columns and rows of the matrix, with multiplication by correction \"twiddle factors\" in between. The algorithm is named after an article by David H. Bailey, FFTs in external or hierarchical memory, published in 1989. In this article, Bailey credits the algorithm to W. M. Gentleman and G. Sande, who published their paper, Fast Fourier Transforms: for fun and profit, in 1966, more than two decades earlier. The algorithm can be considered a radix- \\sqrt n FFT decomposition.",
  "body": "Bailey's FFT (also known as a 4-step FFT) is a high-performance algorithm for computing the fast Fourier transform (FFT). This variation of the Cooley–Tukey FFT algorithm was originally designed for systems with hierarchical memory, as is common in modern computers, and was the first FFT algorithm in this \"out of core\" class. The algorithm treats the samples as a two dimensional matrix (thus another name, a matrix FFT algorithm ) and executes short FFT operations on the columns and rows of the matrix, with multiplication by correction \"twiddle factors\" in between. The algorithm is named after an article by David H. Bailey, FFTs in external or hierarchical memory, published in 1989. In this article, Bailey credits the algorithm to W. M. Gentleman and G. Sande, who published their paper, Fast Fourier Transforms: for fun and profit, in 1966, more than two decades earlier. The algorithm can be considered a radix- \\sqrt n FFT decomposition. Let n=n_1n_2 be the transform size, and let the input data be represented as a n_1\\times n_2 matrix. Bailey's four-step FFT consists of the following steps: Perform n_1 independent n_2 point FFTs on the input matrix. Multiply each resulting matrix element A_{jk} by the corresponding twiddle factor e^{\\pm 2\\pi i jk/n} , where the sign depends on the convention used for the transform. Transpose the resulting n_1\\times n_2 matrix to get a n_2\\times n_1 matrix. Perform n_2 independent n_1 point FFTs on the transposed matrix. When the component FFTs produce their outputs in natural order, the resulting transform is also in natural order and does not require a separate bit-reversal permutation. Bailey noted that n_1 and n_2 don't need to be equal, although on many systems the algorithm is the most efficient when they are chosen as close as possible to \\sqrt n . The algorithm resembles a 2-dimensional FFT; three-dimensional and higher dimensional extensions are known as 5-step FFT, 6-step FFT, etc. ==References== ==Sources==",
  "categories": [
    "114437564",
    "23603337",
    "26220375",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374298660",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789090641.0,
  "claims": [
    {
      "id": 33655331,
      "subject_qid": "",
      "subject_slug": "bailey-s-fft-algorithm",
      "predicate": "publication date",
      "object_text": "1989",
      "object_num": 19890000.0,
      "object_unit": null,
      "polarity": 1,
      "qualifier": "",
      "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374298660",
      "source_name": "Wikipedia",
      "source_tier": 3,
      "retrieved_at": 1792537372.7699318,
      "confidence": 0.95,
      "article_slug": "bailey-s-fft-algorithm",
      "span_start": 49,
      "span_end": 67
    },
    {
      "id": 33655332,
      "subject_qid": "",
      "subject_slug": "bailey-s-fft-algorithm",
      "predicate": "publication date",
      "object_text": "1966",
      "object_num": 19660000.0,
      "object_unit": null,
      "polarity": 1,
      "qualifier": "",
      "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374298660",
      "source_name": "Wikipedia",
      "source_tier": 3,
      "retrieved_at": 1792537372.7699325,
      "confidence": 0.95,
      "article_slug": "bailey-s-fft-algorithm",
      "span_start": 11,
      "span_end": 60
    }
  ],
  "contradictions": [],
  "confidence": 0.95,
  "csl": {
    "id": "enwiki-001374298660",
    "type": "webpage",
    "title": "Bailey's FFT algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/bailey-s-fft-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          17
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001374298660",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1374298660",
    "note": "Immutable snapshot enwiki-001374298660"
  }
}