高速フーリエ変換
[ X 0 X 1 X 2 X 3 ] = [ W 0 W 0 W 0 W 0 W 0 W 2 W 1 W 3 W 0 W 4 W 2 W 6 W 0 W 6 W 3 W 9 ] [ x 0 x 2 x 1 x 3 ] = [ W 0 W 0 W 0 W 0 W 0 W 0 W 0 W 2 W 1 W 0 W 1 W 2 W 0 W 0 W 2 W 0 W 2 W 0 W 0 W 2 W 3 W 0 W 3 W 2 ] [ x 0 x 2 x 1 x 3 ] {\displaystyle {\begin{aligned}{\begin{bmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{bmatrix}}&={\begin{bmatrix}W^{0}&W^{0}&W^{0}&W^{0}\\W^{0}&W^{2}&W^{1}&W^{3}\\W^{0}&W^{4}&W^{2}&W^{6}\\W^{0}&W^{6}&W^{3}&W^{9}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}\\&={\begin{bmatrix}W^{0}&W^{0}&W^{0}W^{0}&W^{0}W^{0}\\W^{0}&W^{2}&W^{1}W^{0}&W^{1}W^{2}\\W^{0}&W^{0}&W^{2}W^{0}&W^{2}W^{0}\\W^{0}&W^{2}&W^{3}W^{0}&W^{3}W^{2}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{2}\\x_{1}\\x_{3}\end{bmatrix}}\end{aligned}}}
高速フーリエ変換といえば一般的には1965年、ジェイムズ・クーリー(英語版) (J. W. Cooley) とジョン・テューキー (J. W. Tukey) が発見した とされているクーリー–テューキー型FFTアルゴリズム(英語版)を呼ぶ。同時期に高橋秀俊がクーリーとテューキーとは全く独立にフーリエ変換を高速で行うためのアルゴリズムを考案していた。しかし、1805年頃に既にガウスが同様のアルゴリズムを独自に発見していた(本ページの外部リンク先に同じ文章PDFへのリンクがある)。ガウスの論文以降、地球物理学や気候や潮位解析などの分野などで測定値に対する調和解析は行われていたので、計算上の工夫を必要とする応用分野で受け継がれていたようである(たとえば、Robart L. Nowack: "Development of the FFT and Applications in Geophysics", in Proceedings of the Cornelius Lanczos International Centenary Conference,SIAM, ISBN 978-0898713398 (1994), pp.