%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Copyright (C) 1998 Keiichi Ishioka				       %
% 								       %
% �������ɽ�������ܤ��Ƥ���ʤ��, �ɤΤ褦�����ΤˤǤⲿ����ä� %
% ����ʣ�̤��ƺ����դ��뤳�Ȥ���Ĥ��ޤ�. �����Υɥ�����ȤȤ��λ� % 
% �ѵ�����¾�θ������������ݤ�, �ʲ��ξ��˽��äƲ�����.	       %
% 								       %
% ¾�θ������������ݤ�, ¾�θ���Ǥθ���ɽ���ؤ��ѹ����ϰϤ�ۤ��Ƹ� %
% �դ˰�̣���ѹ����ʤ�����.					       %
%								       %
% �����������ѵ����ˤ�, ���줬�����Ǥ��뤳��, �ޤ���ʸ�λ��ѵ��������� %
% ���Τ˰���Ŭ�Ѥ���뤳�Ȥ��������뤳��.			       %
%								       %
% �ϥ��ѡ��ƥ����Ȥξ��, Ʊ�쥵���Ⱦ�Ǹ�ʸ�Υ��ԡ����ݼ餹�뤳��. �� %
% ��, ���������ϥ��ѡ��ƥ����ȤΥڡ������餽�θ�ʸ�ؤΥ�󥯤��󶡤��� %
% ����.								       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%����   98/10/27 �в�����
%
\documentstyle[a4j]{jarticle}
\begin{document}

\begin{center}
\Large\bf FFT -- ��®���르�ꥺ���ȯ�� --
\end{center}

\begin{flushright}
\bf �в�����
\end{flushright}

\section{�Ϥ����}

FFT(Fast Fourier Transform = ��®�ա��ꥨ�Ѵ�)��, 
DFT(Discrete Fourier Transform = Υ���ա��ꥨ�Ѵ�)���®�˼¹Ԥ����ˡ
�Ǥ�. �����Ǥ�, �ա��ꥨ�Ѵ��ΰ�̣�������ˤĤ��Ƥϴ��ΤȤ���, DFT���
ñ��Ƴ������������, FFT���Τ�Τι�������ˤ˹ʤäƲ��⤷�Ƥ����ޤ�.

\section{Υ���ա��ꥨ�Ѵ�}

����$2\pi$��Ĵؿ�$f(x)$��ʲ��Τ褦�˥ա��ꥨ���Ÿ�����뤳�Ȥ�ͤ���
��:
\begin{equation}
f(x)=\sum_{k=-\infty}^{\infty}a_k e^{ikx}.
\label{Fourier-Expansion}
\end{equation}
$f(x)$���ͤ�������ˤ錄�ä�Ϣ³Ū��ʬ���äƤ����, Ÿ������$a_k$����
�ϰʲ��Υա��ꥨ��ʬ�ǵ��뤳�Ȥ��Ǥ��ޤ�:
\begin{equation}
a_k=\frac1{2\pi}\int^{2\pi}_0 f(x)e^{-ikx}dx.
\label{Fourier-Integral}
\end{equation}
������, �ؿ�$f(x)$����¬�ǡ������Ǥ�����, �ؿ��ͤ�Ϣ³Ū�ˤ�����줺, 
Υ��Ū��$x$���ͤ��Ф��Ƥ����ؿ��ͤ�Ϳ�����ʤ����Ȥ����̤Ǥ�.
�㤨��, $N$�Ĥ����ֳ֤���$x_j$:
\begin{equation}
x_j=\frac{2\pi}N j, \quad (j=0,1,\cdots,N-1),
\end{equation}
�Ǥδؿ���$f_j$:
\begin{equation}
f_j=f(x_j), \quad (j=0,1,\cdots,N-1),
\end{equation}
�Τߤ������Ƥ������ͤ��ޤ��礦. ���ΤȤ�, �ա��ꥨŸ��
(\ref{Fourier-Expansion})�ˤ�����Ÿ���ؿ�$e^{ikx}$��$N$�Ĥ���$x_j$�Ǥ�
��ɾ������ޤ���Τ�, $N$�����Υ٥��ȥ�Ȥߤʤ���ޤ�.
$N$�����Υ٥��ȥ�Ǥ��Τ�, �����켡��Ω����ʬ��$N$�Ĥ������ꤨ�ޤ���.
�ä˺��ξ��Τ褦����$x_j$�����ֳ֤ˤȤäƤ�����ˤ�,
\begin{equation}
e^{i(k+N)x_j}=e^{i(k+N)\frac{2\pi}N j}
=e^{2\pi i j}e^{ik\frac{2\pi}N j}=e^{ik\frac{2\pi}N j}=e^{ikx_j}
\end{equation}
�Ȥʤ�, �ȿ�$k$��$N$�������餷���٥��ȥ뤬�ȿ�$k$�Υ٥��ȥ������Ʊ��
��Τˤʤ�ޤ�. 
�����, ͭ�¤����Ǵؿ���ɾ�����뤿���, �����ȿ�����ʬ���̤��ȿ�����ʬ
�ȶ��̤��Ĥ��ʤ��ʤä�Ʊ��뤵��Ƥ��ޤ����Ȥˤ��ޤ�. 
���θ��ݤ�, �����ȿ�����ʬ�ˡ���̾�פ�Ϳ���Ƥ��ޤ��Ȥ������Ȥ�, �֥���
�����󥰡פȸƤФ�Ƥ��ޤ�.
���ä�, ���ξ��, �ա��ꥨ���Ÿ��
(\ref{Fourier-Expansion})��̵�¸Ĥ��¤�ͤ��������, ��Ω��$N$�Ĥ�
��ʬ����:
\begin{equation}
f_j=\sum_{k=0}^{N-1}a_ke^{ikx_j}, \quad (j=0,1,\cdots,N-1),
\label{IDFT}
\end{equation}
�Τߤ�ͤ���٤��Ǥ��뤳�Ȥ�ʬ����ޤ�.

�Ǥ�, Ÿ��(\ref{IDFT})�ˤ�����, Ϳ����줿�ؿ���$f_j$����Ÿ������$a_k$
�����ˤϤɤ�����Ф褤�Ǥ��礦��? �����פ��Ĥ���ˡ��, 
��(\ref{IDFT})�κ��դ����ΤʤΤ�����, (\ref{IDFT})��$N$��ϢΩ�켡����
���Ȥ��Ʋ򤱤�$a_k$����ޤ�פȤ�����ΤǤ���, �¤Ϥ�äȤ��ޤ���ˡ��
����ޤ�. ���������¤θ����ˤ��,  ����$l$��$N$���ܿ���
�ʤ����ˤ�,
\begin{equation}
\sum_{j=0}^{N-1}e^{ilx_j}
=\sum_{j=0}^{N-1}e^{il\frac{2\pi}{N}j}
=\sum_{j=0}^{N-1}\left(e^{il\frac{2\pi}{N}}\right)^j
=\frac{\left(e^{il\frac{2\pi}{N}}\right)^N-1}{e^{il\frac{2\pi}{N}}-1}=0,
\end{equation}
�Ȥʤ뤳�Ȥ�ʬ����ޤ���, ����$l$��$N$���ܿ��ξ��ˤ�
\begin{equation}
\sum_{j=0}^{N-1}e^{ilx_j}
=\sum_{j=0}^{N-1}e^{il\frac{2\pi}{N}j}
=\sum_{j=0}^{N-1}1^j=N,
\end{equation}
�Ȥʤ뤳�Ȥ�ʬ����ޤ�. ���ä�, (\ref{IDFT})��ξ�դ�$e^{-ikx_j}\quad
(k=0,1,\cdots,N-1)$��ݤ���$j$�ˤĤ������¤�Ȥ��,
\begin{equation}
(����)=\sum_{j=0}^{N-1}f_je^{-ikx_j},
\end{equation}
\begin{equation}
(����)=\sum_{j=0}^{N-1}\left(\sum_{k'=0}^{N-1}a_{k'}e^{ik'x_j}\right)e^{-ikx_j}
=\sum_{k'=0}^{N-1}a_{k'}\left(\sum_{j=0}^{N-1}e^{i(k'-k)x_j}\right)
=Na_k,
\end{equation}
�������ޤ�. ������, (\ref{IDFT})�ˤ�����$k$��$k'$�˽񴹤�, 
$k'-k$��$N$���ܿ��ˤʤ�Τ�, $k'=k$�Ȥʤ�Ȥ������Ǥ��뤳�Ȥ��Ѥ��ޤ�
��. �ʾ夫��, $a_k$����뤿��θ���:
\begin{equation}
a_k=\frac1N\sum_{j=0}^{N-1}f_je^{-ikx_j}, \quad (k=0,1,\cdots,N-1),
\label{DFT}
\end{equation}
������줿���Ȥˤʤ�ޤ�. $f(x)$��Ϣ³�̤Ȥ���Ϳ�����Ƥ������Υա�
�ꥨ��ʬ�μ�(\ref{Fourier-Integral})�ȸ�����٤��, ���μ���, ��ʬ���
ʬ����ˡŪ���¤��֤���������ΤˤʤäƤ��뤳�Ȥ�ʬ����ޤ�.

�ʾ�ˤ��, �ؿ���ɾ������Υ��Ū��Ϳ����줿����Ÿ������$a_k$�ȴؿ�
��$f_j$�Ȥδ֤δط���(\ref{IDFT}),(\ref{DFT})��Ƴ����ޤ�����, ����
��μ���Υ���ա��ꥨ�Ѵ�(Discrete Fourier Transform = DFT)�ȸƤФ�Ƥ�
�ޤ�.

\section{��®�ա��ꥨ�Ѵ�}

DFT��2�Ĥμ�(\ref{DFT})��(\ref{IDFT})�Ȥ�, �ߤ����Ѵ��ȵ��Ѵ��Ȥδط�
�ˤ���ޤ���, �ؤ�Ʊ�����򤷤Ƥ��뤳�Ȥ˵����Ĥ��ޤ�. �º�, 
(\ref{DFT})��ξ�դ�$N$�ܤ���ʣ�Ƕ����Ȥ��,
\begin{equation}
(Na_k)^*=\sum_{j=0}^{N-1}f_j^*e^{ikx_j}
=\sum_{j=0}^{N-1}f_j^*e^{ik\frac{2\pi}N j}
=\sum_{j=0}^{N-1}f_j^*e^{ij\frac{2\pi}N k}
=\sum_{j=0}^{N-1}f_j^*e^{ijx_k},
\end{equation}
�Ȥʤ�, (\ref{IDFT})������Ʊ�����˵��夵��ޤ�. ���ä�, DFT�η׻��ˤ�
���ƹͤ�����, (\ref{IDFT})���η��Τߤ�ͤ�������ǽ�ʬ�Ǥ��뤳�Ȥ�ʬ
����ޤ�. �Ȥ����櫓��, �ʲ�(\ref{IDFT})���η׻��ˤĤ��ƹͤ��Ƥ����櫓
�Ǥ���, �ص���, $x_j=2\pi j/N$�Ǥ��뤳�Ȥ�Ȥä�, �ʲ��Τ褦�ʷ��˽�
���Ƥ����ޤ�:
\begin{equation}
F(j)=\sum_{k=0}^{N-1}W_N^{jk}A(k), \quad (j=0,1,\cdots,N-1).
\label{WDFT}
\end{equation}
������, $F(j)=f_j$, $A(k)=a_k$�Ƚ�ľ��, $W_N=e^{\frac{2\pi i}N}$����
��Ƥ��ޤ�. 

����, (\ref{WDFT})���η׻��ˤĤ��ƹͤ��Ƥ����ޤ��礦. ���η׻���,
$N\times N$����$(W_N^{jk})$��$N$�����٥��ȥ�$a_k$��ݤ��뤳�Ȥ�¾�ʤ�
�ޤ��󤫤�, ɬ�פʷ׻��̤�, �Ѥ�$N^2$����¤�$N(N-1)$���, �Ȥ��
${\cal O}(N^2)$��Ȥ������Ȥˤʤ�ޤ�. 
���ä�, �㤨��$N=10000$�ξ���ͤ����, DFT�η׻��Τ����
$N^2=1$���󥪡������α黻��ɬ�פˤʤ�ޤ�. ���Ǥ�, �ѥ��������ǽ����
�夷��, ��®�Τ�Τˤʤ��1GFlops(1�ô֤�10�������ư�������黻��¹�
�Ǥ���)�����äƤ��ޤ�����, �������٤η׻��ʤ�ѥ�����Ǥ��ʤ����Ȥ�
����ޤ���. ������, �Żҷ׻��������ϴ��ǤϤ����;͵�ʤ��Ȥ���äƤ���
��ޤ���Ǥ���. 1960ǯ��ˤʤäƤ�äȥ����ѡ�����ԥ塼�����ȸƤФ��
��®�׻���������Ƥ��ޤ�����, ����Ǥ⤿������1MFlops(1�ô֤�100�����
��ư�������黻��¹ԤǤ���)���٤�ǽ�Ϥ�������ޤ���Ǥ���. �Ȥ����櫓
��, �����Ϻ�®�η׻�����ȤäƤ�, �嵭��DFT�η׻���100�ðʾ夫���äƤ�
�ޤ��Ȥ��������Ǥ���, $N$���礭������DFT�ϵ��ڤˤϼ¹ԤǤ��ޤ���Ǥ�
��.

������, ��DFT��׻����뤿��β������ޤ���ˡ�Ϥʤ���?�פȤ����Τ������
�����Ǥ���, ��ɬ�פ�ȯ������פθ��ɤ���˹�®�ա��ꥨ�Ѵ�(Fast
Fourier Transform = FFT)�����ޤ�뤳�Ȥˤʤ�ޤ���.
�����Ǥ�, ����Ĺ�ˤϤʤ�ޤ���, FFT�Ρ�ȯ���ԡפǤ��� Cooley and
Tukey (1965)����ʸ�˱�äƤ��γ��פ򸫤Ƥ����ޤ��礦.

�ޤ�, �Ѵ���Ĺ��$N$��$N=N_1P$��2�Ĥ�����$N_1,P$���ѤˤʤäƤ����
���ͤ��ޤ�. ���ΤȤ�, (\ref{WDFT})��ź��$j,k$���줾���2�Ĥ�ź������
$(j_p,j_1)$, $(k_1,k_p)$�ˤ�ä�,
\begin{equation}
j=N_1j_p+j_1,\quad (j_1=0,1,\cdots,N_1-1; \ j_p=0,1,\cdots,P-1),
\end{equation}
\begin{equation}
k=Pk_1+k_p,\quad (k_1=0,1,\cdots,N_1-1;\ k_p=0,1,\cdots,P-1),
\end{equation}
�Τ褦��ɽ�����뤳�Ȥˤ��ޤ�. �����, C�ʤɤΥץ�����ߥ󥰸���ˤ���
��, $N_1\times P$�����$P\times N_1$��2���������ȤäƤ���ȹͤ�
���ʬ����䤹�����⤷��ޤ���.
����ɽ����Ȥ���, (\ref{WDFT})�ϰʲ��Τ褦�˽񴹤����ޤ�:
\begin{equation}
F(j_p,j_1) = \sum_{k_1=0}^{N_1-1}\sum_{k_p=0}^{P-1}
               W_N^{(N_1j_p+j_1)(Pk_1+k_p)}A(k_1,k_p).
\label{WDFT2}
\end{equation}
������,
\begin{eqnarray*}
W_N^{(N_1j_p+j_1)(Pk_1+k_p)}
 &=& W_N^{N_1Pj_pk_1+Pj_1k_1+(N_1j_p+j_1)k_p}\\
 &=& W_N^{Nj_pk_1}W_N^{Pj_1k_1}W_N^{(N_1j_p+j_1)k_p}\\
 &=& (W_N^N)^{j_pk_1}W_N^{Pj_1k_1}W_N^{(N_1j_p+j_1)k_p}\\
 &=& W_N^{Pj_1k_1}W_N^{(N_1j_p+j_1)k_p}
\end{eqnarray*}
�Ǥ��뤳�Ȥ����դ����, (\ref{WDFT2})��,
\begin{equation}
F(j_p,j_1) = \sum_{k_p=0}^{P-1}W_N^{(N_1j_p+j_1)k_p}
 \sum_{k_1=0}^{N_1-1}W_N^{Pj_1k_1}A(k_1,k_p),
\label{WDFT3}
\end{equation}
���ʤ��, 
\begin{equation}
F(j_p,j_1) = \sum_{k_p=0}^{P-1}W_N^{(N_1j_p+j_1)k_p}A_1(j_1,k_p),
\quad (j_1=0,1,\cdots,N_1-1;\ j_p=0,1,\cdots,P-1),
\label{WDFTD1}
\end{equation}
\begin{equation}
A_1(j_1,k_p) = \sum_{k_1=0}^{N_1-1}W_N^{Pj_1k_1}A(k_1,k_p),
\quad (j_1=0,1,\cdots,N_1-1;\ k_p=0,1,\cdots,P-1),
\label{WDFTD2}
\end{equation}
��2�ʳ���ʬ�򤵤�ޤ�. ����, ���Τ褦��ʬ�򤹤��, �黻������ɤ��Ѳ�
���뤫�����Ƥߤޤ��礦.
�ޤ�, (\ref{WDFTD2})�ˤ��Ѥ�$N_1^2��P$��, �¤�$N_1(N_1-1)��P$��ɬ�פ�,
(\ref{WDFTD2})�ˤĤ��Ƥ�, �Ѥ�$P^2��N_1$��, �¤�$P(P-1)��N_1$��
�Ȥʤ�ޤ�����, ��פ�, �Ѥ�$N_1P(N_1+P)=N(N_1+P)$��, 
�¤�$N_1P(N_1+P-2)=N(N_1+P-2)$��ɬ�פȤ������Ȥˤʤ�ޤ�.
���ä�, ${\cal O}(N^2)$�η׻��̤�${\cal O}(N(N_1+P))$�ˤʤä����Ȥ�
�ʤ�ޤ�. �ǽ��$N=10000$�ξ��η׻��̤���ˤȤ�ޤ�����, ���ξ��,
$N_1=P=100$�ȤȤäƤ������, $N^2=1$����η׻��̤�$N(N_1+P)=200$��
���, $1/50$�˸������뤳�Ȥˤʤ�ޤ�.

����Ǥ⽽ʬ�ˤ��Ф餷�����ɤʤΤǤ���, �����, $P=N_2Q$��$P$��2�Ĥ���
�����Ѥ�ʬ��Ǥ�����ˤ�, $j_p,k_p$���줾���2�Ĥ�ź������
$(j_q,j_2)$, $(k_2,k_q)$�ˤ�ä�,
\begin{equation}
j_p=N_2j_q+j_2,\quad (j_2=0,1,\cdots,N_2-1;\ j_q=0,1,\cdots,Q-1),
\end{equation}
\begin{equation}
k_p=Qk_2+k_q,\quad (k_2=0,1,\cdots,N_2-1;\ k_q=0,1,\cdots,Q-1),
\end{equation}
��ɽ�����Ȥˤ��, 
(\ref{WDFTD1})�η׻��ϰʲ��Τ褦���ѷ��Ǥ��ޤ�(�ʲ�, ź�����ϰϤˤĤ�
�ƤϾ�ά���Ƥ��ޤ�):
\begin{eqnarray}
F(j_q,j_2,j_1) 
 &=& \sum_{k_q=0}^{Q-1}\sum_{k_2=0}^{N_2-1}
  W_N^{(N_1(N_2j_q+j_2)+j_1)(Qk_2+k_q)}A_1(j_1,k_2,k_q)\\
 &=& \sum_{k_q=0}^{Q-1}W_N^{(N_1(N_2j_q+j_2)+j_1)k_q}
  \sum_{k_2=0}^{N_2-1}W_N^{Q(N_1(N_2j_q+j_2)+j_1)k_2}A_1(j_1,k_2,k_q)\\
 &=& \sum_{k_q=0}^{Q-1}W_N^{(N_1(N_2j_q+j_2)+j_1)k_q}A_2(j_1,j_2,k_q).
\label{WDFT4}
\end{eqnarray}
������, $W_N^{QN_1N_2}=W_N^N=1$�Ǥ��뤳�Ȥ����դ���,
\begin{equation}
A_2(j_1,j_2,k_q)=\sum_{k_2=0}^{N_2-1}W_N^{Q(N_1j_2+j_1)k_2}
  A_1(j_1,k_2,k_q)
\end{equation}
�����ޤ���.
���Τ褦��ʬ�򤹤��, �׻��̤�${\cal O}(N(N_1+N_2+Q))$�˲������뤳��
�ˤʤ�ޤ�. �����$Q=N_3R$��ɽ�����Ȥ���(\ref{WDFT4})$��ʬ�򤹤��
\cdots$��,����ʬ��򷫤��֤��Ƥ������Ȥ�ͤ����, ���,
$N=N_1N_2\cdots N_m$�ΤȤ�,
$F(j)$�ϰʲ��Τ褦��������Ū���Ƿ׻��Ǥ��뤳�Ȥˤʤ�ޤ�.
\begin{enumerate}
\item
�ޤ�, �ʲ��Τ褦�˽����$A_1$��$A$�������ޤ�:
\begin{equation}
\begin{array}{c}
Q_1=N_1;\quad P_1=N/Q_1,\\
\displaystyle
A_1(j_1,k_p) = \sum_{k_1=0}^{N_1-1}W_N^{P_1j_1k_1}A(k_1,k_p),\\
\quad (j_1=0,1,\cdots,N_1-1;\ k_p=0,1,\cdots,P_1-1).
\end{array}
\label{FFT1}
\end{equation}
\item
���Ȥ�$l=2,3,\cdots,m$�ˤĤ���, ������Ū�˽��$A_l$����Ƥ����ޤ�:
\begin{equation}
\begin{array}{c}
Q_l=N_1N_2\cdots N_l;\quad P_l=N/Q_l,\\
\displaystyle
A_l(j_1,j_2,\cdots,j_{l-1},j_l,k_p)=\sum_{k_l=0}^{N_l-1}
    W_N^{P_l(Q_{l-1}j_l+Q_{l-2}j_{l-1}+\cdots+Q_1j_2+j_1)k_l}
    A_{l-1}(j_1,j_2,\cdots,j_{l-1},k_l,k_p)\\
\quad (j_r=0,1,\cdots,N_r-1\ (r=1,2,\cdots,l); \ k_p=0,1,\cdots,P_l-1).
\end{array}
\label{FFT2}
\end{equation}
\item
�ʾ�򷫤��֤��Ƥ����Ⱥǽ�Ū��$A_m$����ޤ�Τ�, ���줫��$F$��ź������
���ؤ��ˤ�äưʲ��Τ褦�˵��ޤ�:
\begin{equation}
\begin{array}{c}
\displaystyle
F(j_m,j_{m-1},\cdots,j_2,j_1)=A_m(j_1,j_2,\cdots,j_{m-1},j_m),\\
\quad (j_r=0,1,\cdots,N_r-1\ (r=1,2,\cdots,m)).
\end{array}
\label{FFT3}
\end{equation}
\end{enumerate}
�����, ����$A$�������$F$�����뤳�Ȥ��Ǥ��ޤ���.
�פ����׻��̤�, �����Ƥߤ�Ф���ʬ����ޤ��褦��,
${\cal O}(N(N_1+N_2+\cdots +N_m))$�ˤޤǸ��餵��뤳�Ȥˤʤ�ޤ�.
�ä�, $N$����������$r$��沤ˤ�ä�, $N=r^m$�Ƚ񤱤���ˤ�,
$N_1=N_2=\cdots =N_m=r$�ȤȤ��, ${\cal O}(Nrm)={\cal O}(Nr\log_r N)$
��ɽ���ޤ�.
�ǽ��$N=10000$�ξ��ˤĤ���, $r=10$�ȤȤ��, 
�׻��̤�, 
${\cal O}(Nr\log_r N)={\cal O}(10^4\times 10\times 4)={\cal O}(400000)$,
�Ȥʤ�, ���DFT��ľ�ܷ׻�����Τ�ɬ�פ�1����η׻��̤�, 40����Ȥʤ�,
$1/250$�ˤޤǸ������뤳�Ȥˤʤ�ޤ�
\footnote{��äȤ�, ���ξ��$10000=(2\times 5)^4=2^4\times 5^4$
�Ȥ��٤���ʬ�򤷤�����, �׻��̤�${\cal O}(10^4\times (2\times4
+5\times 4))={\cal O}(280000)$��, ����˾��ʤ��ʤ�ޤ�.}.

�ʾ�Υ��르�ꥺ��ˤ�ä�, ${\cal O}(N^2)$�η׻��̤�ɬ�פ��ä�DFT��
${\cal O}(N\log N)$�η׻��̤ǤǤ��뤳�Ȥ�ʬ����ޤ�. ���Υ��르�ꥺ���
Cooley and Tukey (1965)�ˤ�ä�ȯɽ����\footnote{Cooley and Tukey
(1965)�Ǥ�, ����Ū��ɽ���Ȥ��Ƥ�
$N=2^m$�ξ��Τߤ�������ޤ��Τ�, $N$���嵭�Τ褦�˰��̤�$N_r$��ʬ
�򤵤����ˤĤ��Ƥ�ɽ����, ���μ㴳�γ�ĥ�Ǥ��� Bergland (1967)�ˤ��
�Ƥ��ޤ�.}, Fast Fourier Transform = FFT
�ȸƤФ�Ƥ��ޤ�. ���Υ��르�ꥺ���Ȥ����Ȥˤ��׻��̤θ����Ϸ�Ū��
����, ���르�ꥺ�༫�Τ����˴����ʤΤ�1965ǯ�ޤ�ȯ������ʤ��ä��Ȥ�
�����Ȥ��Ի׵Ĥ˻פ������⤤��ä���뤫�⤷��ޤ���. ���ε���Ϥ��
�Ȥ��, �ǽ�˾Ҳ𤷤���ʬ�ǡ�ȯ���ԡפȤ�����̤��դ����Τ⤽�Τ����
��. �º�, Cooley and Tukey (1965)�����ˤ�Ʊ�ͤΥ��르�ꥺ�����Ω��ȯ
����, �º�, �ץ�����ߥ󥰤ޤǹԤäƤ����ͤ⤤���ΤǤ���, FFT��ºݤ�
���˹��᤿�ΤϤ���5�ڡ����δʷ����ʸ�Ǥ����Τ�, ���Ǥ�FFT��ȯ���Ԥα�
���� Cooley and Tukey (1965)��Ϳ�����Ƥ��ޤ�. ���Τ������FFT�����
�ˤĤ��Ƥ�, Brigham ``The Fast Fourier Transform'' (1974) (ˮ��:
����������ֹ�®�ա��ꥨ�Ѵ���(1978)) ����1�Ϥ������˾ܤ����ޤȤ���
�Ƥ��ޤ�.

\section{����ɽ���ˤ��FFT������}

����ǽҤ٤����Ƥ�FFT�δ���Ū�ʹ���ˡ�ϿԤ���Ƥ���, ������Ǥ�FFT���
������ץ�����ब����Ϥ��Ǥ���, FFT�μ�ˡ�˴���ʤ������ϡֳΤ���
�����Ƥߤ�ȷ׻��̤���Ū�˸���Τ�ʬ���뤱��, ź�����������Ƥ��Ƽ���
�ߤ���.�פȤ������ݤ��������¿���Ȼפ��ޤ�. ���Τ褦�ʾ���, ���Τ�
�׻���ή������׻��η���ɽ�����Ƥ����������ưפˤʤ�ޤ�. $N$��2��
沤ξ��ˤĤ��ƤϤ��������ʶ��ʽ�˺ܤäƤ��ޤ��Τ�, �����Ǥ�
$N=6=3\times 2$�ξ��ˤĤ��������FFT���르�ꥺ������η��ǽ񤭲���
�Ƥߤޤ��礦.

�ޤ�, DFT�������(\ref{WDFT})��$N=6$�ξ��ˤĤ��ƽ񤤤Ƥ����ޤ�:
\begin{equation}
  \left[\begin{array}{l}
   F(0)\\F(1)\\F(2)\\F(3)\\F(4)\\F(5)
  \end{array}\right]
 =
  \left[\begin{array}{llllll}
  \omega^0 &\omega^0 &\omega^0    &\omega^0    &\omega^0    &\omega^0    \\
  \omega^0 &\omega^1 &\omega^2    &\omega^3    &\omega^4    &\omega^5    \\
  \omega^0 &\omega^2 &\omega^4    &\omega^6    &\omega^8    &\omega^{10} \\
  \omega^0 &\omega^3 &\omega^6    &\omega^9    &\omega^{12} &\omega^{15} \\
  \omega^0 &\omega^4 &\omega^8    &\omega^{12} &\omega^{16} &\omega^{20} \\
  \omega^0 &\omega^5 &\omega^{10} &\omega^{15} &\omega^{20} &\omega^{25} \\
  \end{array}\right]
  \left[\begin{array}{l}
   A(0)\\A(1)\\A(2)\\A(3)\\A(4)\\A(5)
  \end{array}\right].
 \label{DFT-M}
\end{equation}
������, $\omega=W_6$�Ȥ��Ƥ��ޤ�.
����, ����ǽҤ٤�FFT���르�ꥺ���$N_1=3,N_2=2$�Ȥ��ƽ񤭲����ߤޤ�:
\begin{equation}
  \left[\begin{array}{l}
   F(0)\\F(1)\\F(2)\\F(3)\\F(4)\\F(5)
  \end{array}\right]
 =
  \left[\begin{array}{llllll}
    1 &   0 &   0 &   0 &   0  &   0  \\
    0 &   0 &   1 &   0 &   0  &   0  \\
    0 &   0 &   0 &   0 &   1  &   0  \\
    0 &   1 &   0 &   0 &   0  &   0  \\
    0 &   0 &   0 &   1 &   0  &   0  \\
    0 &   0 &   0 &   0 &   0  &   1 
  \end{array}\right]
  \left[\begin{array}{llllll}
  \omega^0 & \omega^0 &   0 &   0 &   0  &   0  \\
  \omega^0 & \omega^3 &   0 &   0 &   0  &   0  \\
    0 &   0 & \omega^0 & \omega^1 &   0  &   0  \\
    0 &   0 & \omega^0 & \omega^4 &   0  &   0  \\
    0 &   0 &   0 &   0 & \omega^0  & \omega^2  \\
    0 &   0 &   0 &   0 & \omega^0  & \omega^5 
  \end{array}\right]
  \left[\begin{array}{llllll}
  \omega^0 &   0 & \omega^0 &   0 & \omega^0  &   0  \\
    0 & \omega^0 &   0 & \omega^0 &   0  & \omega^0  \\
  \omega^0 &   0 & \omega^2 &   0 & \omega^4  &   0  \\
    0 & \omega^0 &   0 & \omega^2 &   0  & \omega^4  \\
  \omega^0 &   0 & \omega^4 &   0 & \omega^8  &   0  \\
    0 & \omega^0 &   0 & \omega^4 &   0  & \omega^8 
  \end{array}\right]
  \left[\begin{array}{l}
   A(0)\\A(1)\\A(2)\\A(3)\\A(4)\\A(5)
  \end{array}\right].
 \label{FFT-M}
\end{equation}
ξ�Ԥ�������Ʊ���黻�ˤʤäƤ��뤳�Ȥ�, (\ref{FFT-M})�α��դ�3�Ĥ���
��������Ѥ�׻���, $\omega^6=\omega^0=1$�Ǥ��뤳�Ȥ����դ���д�ñ��
��ǧ�Ǥ��ޤ�.
FFT�Υ��르�ꥺ��ˤ�äƷ׻��̤���������Τ�(\ref{FFT-M})�򸫤�а���
������, (\ref{DFT-M})�α��դι���(\ref{FFT-M})�Ǥ�������ʬ�ξ��ʤ���
������Ѥ�ʬ�򤵤�Ƥ��뤿��, �黻�򱦤���Ԥ��ȷ׻���������ʤ��ƺѤ�
�Ȥ������Ȥ�¾�ʤ�ʤ����Ȥ�ʬ����ޤ�.

�ޤ�, ���Τ褦�ʹ���ɽ����Ȥ���, FFT���르�ꥺ����̤η����ˤĤ��Ƥ�
���̤����ɤ��ʤ�ޤ�. �㤨��, (\ref{DFT-M})�α��դι�����оι���Ǥ�
�뤿��, ž�֤�ȤäƤ�Ʊ�����ˤʤ�ޤ�. ������, (\ref{FFT-M})�α��դ�
����Ƥ���3�Ĥ���������������Τ�ž�֤�ȤäƤ��ɤ����Ȥˤʤ�, ������
���$A$�Υ٥��ȥ�˱黻��������ν��֤��Ѥ����뤳�Ȥˤʤ�ޤ�. 
�������� Cooley and Tukey�Υ��르�ꥺ���``ž��''���������륢�르�ꥺ
�बƳ����ޤ���, �ޤ�, (\ref{FFT-M})�ǤϺǸ���¤��ؤ��ι��󤬳ݤ���
��Ƥ��ޤ���, �����¤��ؤ�����������ι�����������
``self-sorting''���Υ��르�ꥺ�����Ƥ���Ƥ��ޤ�. ������FFT�Τ���
�����ʷ��֤ˤĤ��Ƥ�, Temperton (1983)�˾ܺ٤���������Ƥ��ޤ�.

\section{Faster Fourier Transform?}

FFT�δ���Ū���르�ꥺ�बCooley and Tukey (1965)�ˤ�ä�ȯɽ����ư���, 
����˷׻����Ψ�����뤿��θ��椬��¿���Ԥ��ޤ���. 
FFT���׻���${\cal O}(N^2)$��${\cal O}(N\log N)$�˸����������褦�ˤϷ�
Ū�ǤϤ���ޤ���, ���ˤ�äƤ�2�����٤θ�Ψ���ˤĤʤ���ޤ��Τ�,
�ʲ�, ���θ�Ψ���γ�ά�򸫤Ƥ����ޤ��礦.

\subsection{$N$���ǿ��ξ���DFT}
\label{Winograd}

FFT���Ѵ��ι��$N$��$N=N_1N_2\cdots N_m$��ʬ��Ǥ������DFT�ι�®��
��ޤ��ΤǤ���, $N$���ǿ��ξ��ˤϤ��μ�ϻȤ��ޤ���. �㤨��,
$N=5$�ξ���DFT:
\begin{equation}
  \left[\begin{array}{l}
   F(0)\\F(1)\\F(2)\\F(3)\\F(4)
  \end{array}\right]
 =
  \left[\begin{array}{llllll}
  \omega^0 & \omega^0 & \omega^0    & \omega^0    & \omega^0    \\
  \omega^0 & \omega^1 & \omega^2    & \omega^3    & \omega^4    \\
  \omega^0 & \omega^2 & \omega^4    & \omega^6    & \omega^8    \\
  \omega^0 & \omega^3 & \omega^6    & \omega^9    & \omega^{12} \\
  \omega^0 & \omega^4 & \omega^8    & \omega^{12} & \omega^{16} \\
  \end{array}\right]
  \left[\begin{array}{l}
   A(0)\\A(1)\\A(2)\\A(3)\\A(4)
  \end{array}\right],
 \label{DFT-M5}
\end{equation}
��ͤ��Ƥߤޤ��礦. 
������, $\omega=W_5$��ά�����Ƥ��ޤ�.
���ξ��, $\omega^0=1$�ʤΤ�, ������ʬ�Ȥξ軻��ɬ�פʤ�
���Ȥ��θ���Ƥ�, ���η׻��ˤϾ軻16��, �û�20��Ϥɤ����Ƥ�ɬ�פʤ褦
�˸����ޤ�. ������, �ʲ��Τ褦�˷׻��������פ����, ���ʤ��黻�����
���η׻�����ǽ�ˤʤ�ޤ�. �ޤ�, $\theta=2\pi/5$�Ȥ���5�Ĥ����:
\begin{equation}
c_1=\frac{\cos\theta+\cos 2\theta}2-1,\ 
c_2=\frac{\cos\theta-\cos 2\theta}2,\ 
c_3=i(\sin\theta+\sin2\theta),\ 
c_4=i\sin2\theta,\ 
c_5=i(\sin\theta-\sin 2\theta),
\end{equation}
������äƷ׻����Ƥ�����, $F(0),\cdots,F(4)$��,
\begin{equation}
\begin{array}{lllll}
s_1=A(1)+A(4),& s_2=A(1)-A(4),& s_3=A(3)+A(2),& s_4=A(3)-A(2),& \\
t_1=s_1+s_3,& t_2=s_1-s_3,& t_3=s_2+s_4,& F(0)=t_1+A(0),& \\
u_1=c_1 t_1,& u_2=c_2 t_2,& u_3=c_3 s_2,& u_4=c_4 t_3,& u_5=c_5 s_4,\\
v_1=F(0)+u_1,& v_2=v_1+u_2,& v_3=v_1-u_2,& v_4=u_3-u_4,& v_5=u_4+u_5,\\
F(1)=v_2+v_4, & F(2)=v_3+v_5,& F(3)=v_3-v_5, & F(4)=v_2-v_4 & 
\end{array}
\label{DFT5}
\end{equation}
�μ��Ƿ׻��Ǥ��ޤ�. ���μ����פ���黻�����, �軻5��, �ø���17��
��, DFT��������ɤ���η׻����⤫�ʤ꾯�ʤ��ʤäƤ��ޤ�. 
������, (\ref{DFT5})�˸����軻�Ϥ��٤�, (�¿��ޤ��Ͻ����)$\times$ʣ
�ǿ��η��ˤʤäƤ��뤿��, �׻����������Τ褦��ʣ�ǿ���2�Ĥμ¿����Ȥ�
����ɽ�������ξ軻�����, $5\times 2=10$��ˤʤ�ޤ���,
(\ref{DFT-M5})�����Ϥ��٤�
ʣ�ǿ�$\times$ʣ�ǿ��η��Ǥ�����, ʣ�ǿ���2�Ĥμ¿����ȤȤ���ɽ������
��ξ軻�����$16\times 4=64$��Ǥ���, �������礭�����Ȥ�ʬ����ޤ�.
���Τ褦�ʸ�Ψ����, �ǽ�Rader (1968)�ˤ�ä���Ƥ���ޤ�����, 
Winograd (1978)�ˤ�ä��͡���$N$���Ф��Ʒ���Ū��Ƴ����ˡ����������ޤ�
��.

�ޤ�, ���μ�ˡ��FFT���Τ�Τι�®���ˤ���ѤǤ��ޤ�. 
FFT�Υ��르�ꥺ������������(\ref{FFT2})�ϰʲ��Τ褦��2�ʳ���ʬΥ�Ǥ�
�ޤ�:
\begin{eqnarray}
A'_{l-1}(j_1,j_2,\cdots,j_{l-1},k_l,k_p) &=&
    W_N^{P_l(Q_{l-2}j_{l-1}+\cdots+Q_1j_2+j_1)k_l}
    A_{l-1}(j_1,j_2,\cdots,j_{l-1},k_l,k_p),
\label{FFT-ROT}\\
A_l(j_1,j_2,\cdots,j_{l-1},j_l,k_p) &=& \sum_{k_l=0}^{N_l-1}
    W_{N_l}^{j_lk_l}
    A'_{l-1}(j_1,j_2,\cdots,j_{l-1},k_l,k_p).
\label{FFT-Nl}
\end{eqnarray}
������, $W_N^{P_lQ_{l-1}}=W_N^{N/N_l}=W_{N_l}$�Ǥ��뤳�Ȥ��Ѥ��ޤ���.
���Τ褦�ˤ����, (\ref{FFT-Nl})������Ĺ��$N_l$��DFT�Ǥ�����, ����DFT��
�׻���\ref{Winograd}�Τ褦�˺�Ŭ�����Ƥ��������Τ�FFT�ι�®���ˤĤʤ�
��ޤ�. �����(\ref{FFT2})�η׻��ˤ�$N\cdot N_l$��ξ軻��ɬ�פʤΤ���
����, (\ref{FFT-ROT})��$N$��, (\ref{FFT-Nl})��$(N/N_l)\cdot N_l^2$���
�軻��ɬ�פ�, ������ɤ���Ǥ�2�ʳ���ʬ�����(\ref{FFT-ROT})��ʬ������
������������Ƥ��ޤ��ޤ���, \ref{Winograd}�κ�Ŭ����ԤäƤ�����, ���
�α黻�ˤ�����軻��������ʤ긺�餻�뤿���Ψ���ˤĤʤ���櫓�Ǥ�.
�ޤ�, ���Τ褦���ѷ������ݤ�(\ref{FFT-ROT})�α��դη�����
��ž����(= twiddle factor)�ȸƤФ�Ƥ��ޤ�.

\subsection{PFA = Prime Factor Algorithm}

�̾��FFT�Υ��르�ꥺ��Ǥϲ�ž���Ҥ�¸�ߤ��Բ���ʤΤǤ���, 
��ž���Ҥ�ȼ��ʤ����르�ꥺ���¸�ߤ��ޤ�.

�Ѵ���Ĺ��$N$��$N=N_1N_2$��2�Ĥ��������ѤȤʤäƤ������ͤ��ޤ�.
������, FFT�ξ��Ȱۤʤ�, $N_1$��$N_2$�Ȥϸߤ����ǤǤ���Ȥ�������
�դ��Ƥ����ޤ�.

�ޤ�, $N_1$��$N_2$�Ȥϸߤ����ǤǤ���Ȥ��������,
\begin{equation}
p_1N_2=p_2N_1+1, \quad q_2N_1=q_1N_2+1, \quad 
(0<p_1,q_1<N_1,\ 0<p_2,q_2<N_2)
\label{MOD}
\end{equation}
����������$p_1,p_2,q_1,q_2$�����٤ޤ�\footnote{�桼����åɤθ߽�ˡ��
�ȤäƤ�����, $p_1,p_2,q_1,q_2$������Ū�������ޤ�.
�㤨��, $N_1=25,N_2=16$�ξ��ˤ�, $p_1=11,p_2=7,q_1=14,q_2=9$�Ȥʤ��
��.}.
���ΤȤ�, DFT�μ�(\ref{WDFT})��ź��$j,k$���줾���2�Ĥ�ź������
$(j_1,j_2)$, $(k_1,k_2)$�ˤ�äưʲ��Τ褦��ɽ�����Ȥˤ��ޤ�:
\begin{equation}
j=(p_1N_2j_1+q_2N_1j_2) \mbox{mod} N,
\quad (j_1=0,1,\cdots,N_1-1;\ j_2=0,1,\cdots,N_2-1),
\label{JMAP}
\end{equation}
\begin{equation}
k=(N_2k_1+N_1k_2) \mbox{mod} N,
\quad (k_1=0,1,\cdots,N_1-1;\ k_2=0,1,\cdots,N_2-1).
\label{KMAP}
\end{equation}
������$j,k$�Τ��٤Ƥ��ϰϤ򤳤�ǥ��С��Ǥ���Τ����ˤʤ�Ȥ����Ǥ���, 
�����, (\ref{MOD})�������Ѥ����, ���줾��εռ�����,
\begin{equation}
j_1=(j) \mbox{mod} N_1,\quad j_2=(j) \mbox{mod} N_2,
\end{equation}
\begin{equation}
k_1=(p_1k) \mbox{mod} N_1,\quad k_2=(q_2k) \mbox{mod} N_2,
\end{equation}
�Ⱥ��뤳�Ȥ��ݾڤ���ޤ�. 
����, $W_N^N=1$�Ǥ��뤳�Ȥ����դ����,
\begin{eqnarray*}
W_N^{jk}&=& W_N^{(p_1N_2j_1+q_2N_1j_2)(N_2k_1+N_1k_2)}\\
     &=& W_N^{p_1N_2N_2j_1k_1+q_2N_1N_1j_2k_2+N_1N_2(p_1j_1k_2+q_2j_2k_1)}\\
  &=& W_N^{p_1N_2N_2j_1k_1+q_2N_1N_1j_2k_2}\\
  &=& W_N^{(p_2N_1+1)N_2j_1k_1+(q_1N_2+1)N_1j_2k_2}\\
  &=& W_N^{N_2j_1k_1+N_1j_2k_2}\\
  &=& W_{N_1}^{j_1k_1}W_{N_2}^{j_2k_2},
\end{eqnarray*}
�Ȥʤ뤳�Ȥ�ʬ����ޤ�����, ����DFT�μ�(\ref{WDFT})��,
\begin{equation}
F(j_1,j_2) = \sum_{k_2=0}^{N_2-1}W_{N_2}^{j_2k_2}\sum_{k_1=0}^{N_1-1}
               W_{N_1}^{j_1k_1}A(k_1,k_2),
\end{equation}
���ѷ��Ǥ��뤳�Ȥˤʤ�ޤ�. FFT�ξ��Ȥϰۤʤ�, ����ʬ��ξ���Ĺ��
$N_1$��DFT��Ĺ��$N_2$��DFT�������֤���������, ;ʬ�ʲ�ž���Ҥ��Ѥʤ�
���ʤ�, �軻��FFT�˳Ӥ٤ƾ��ʤ��ƺѤळ�Ȥˤʤ�ޤ�.
�ޤ�, ����ʬ���FFT��Ʊ�ͤ�, $N_2$�������2�Ĥθߤ����Ǥ��������Ѥ�ɽ
�������$\cdots$, �Τ褦��³���Ƥ������Ȥ��Ǥ��ޤ�.
���Τ褦�ˤ���, $N$��ߤ����Ǥ�����Ʊ�Τ��Ѥ�ʬ�򤷤�, ����ʬ�����
��DFT��嵭�Τ褦��ʬ�򤷤Ƥ������르�ꥺ���,
PFA(= Prime Factor Algorithm)�ȸƤФ�Ƥ��ޤ�.

PFA��ȯ����FFT���Ť�, Good (1958)�ˤ����Τܤ�ΤǤ���, $N$��ߤ�����
��������ʬ�򤷤ʤ���Фʤ�ʤ��Ȥ������󤬤��뤳�Ȥ�, (\ref{JMAP}),
(\ref{KMAP})�ˤ���¤��ؤ���ʣ���ʤ��Ȥ���, ����Ϥ��ޤ����Ū�ȹͤ�
���Ƥ��ʤ��ä��褦�Ǥ�. ������, �׻��̤�FFT��꾯�ʤ��ƺѤ�ʤɤ�̥
��Ū����������äƤ��뤿��, ���θ���ɤ�ä����, FFT���¤�DFT��ͭ�Ϥ�
�׻�ˡ�ȸ��ʤ���Ƥ��ޤ�. �ޤ�, Winograd (1978)��PFA�μ�ˡ��
\ref{Winograd}�μ�ˡ���Ȥ߹�碌�뤳�Ȥˤ�ä�, ����˾軻����򸺤餷
���׻�ˡ(Winograd�Υ��르�ꥺ��)����Ƥ��Ƥ��ޤ�.
�����դξܺ٤� Temperton (1988)�˥�ӥ塼����Ƥ��ޤ���, FFT��PFA���ȹ�
�������٤ʼ����ˤĤ��Ƥ�, Temperton (1992)�ˤ�ä��������Ƥ��ޤ�.

\subsection{�׻����˹�碌����Ŭ��}

�����ޤǤθ�Ψ���ε�����, �׻����׵ᤵ���軻��û��β���������Ȥ�
���ä�, ����Сִ���פε����Ǥ���, �ºݤ�FFT��׻����ѤΥץ�������
���Ƹ���Ū�˼������뤿��ˤ�, ���η׻�����CPU�����ι�¤���θ����
��ʤ���Фʤ�ޤ���. �㤨��, ���Ȥ��黻��������ʤ��Ƥ�, ���껲�Ȥ�
¿������˼ºݤˤ��٤��ʤäƤ��ޤ��褦�ʥ��르�ꥺ��Ϥ���ˤ���ޤ�.
�ޤ�, �����ѡ�����ԥ塼�����ʤɤǤϾ軻��Ȳû��郎���åȤˤʤäƤ���
����, �軻�β���Τߤ򸺤餹�����Ǥϰ�̣���ʤ��ʤ�, �׻���������դ���
����Фʤ�ʤ����ϰۤʤ�ޤ�.

���Τ���, �Ƕ�Ǥ�, ���르�ꥺ��������, \ref{Winograd}�ǽҤ٤��褦��
��Ŭ�����줿�ץ������κ�����׻����˹�碌�Ƽ�ưŪ�˹Ԥ��褦�ʵ��Ѥ�
��ȯ����Ƥ��Ƥ��ޤ�.
������Ǥ�, MIT�� Frigo and Johnson �ˤ��FFTW(= The Fastest Fourier
Transform in the West)�Ϻǿ��θ������̤�Ȥꤳ�ޤ줿ͥ�줿�ե꡼����
�ȥ������Ǥ���, ���󥿡��ͥåȤ������ǽ�Ǥ�
({\tt http://theory.lcs.mit.edu/\~{ }fftw/}).
����FFTW��, ����Ū�ˤ褯�Ȥ��Ƥ���ѥ�����������ơ�������CPU
�˹礻����Ŭ������ʬ�ˤʤ���Ƥ���, ¾�Υե꡼��FFT���եȥ���������®
�ޤ��Ϥ���ʾ�Υѥե����ޥ󥹤򼨤��Ƥ��ޤ�.
�⤷���긵�η׻�����FFT��Ԥ�ɬ�פ�������ˤϤ������ꤷ�ƻȤäƤߤ�
��뤳�Ȥ����ᤷ�ޤ�.

\section{FFT�α���}

FFT���르�ꥺ���ȯ���ˤ�ä�, $N$��Ĺ��DFT�����ڤ˷׻��Ǥ���褦�ˤʤ�
�����ä������礭����, FFT�ϼ¤�¿�ͤ�ʬ��Ǳ��Ѥ���Ƥ��ޤ�.
�Ǥ�ľ��Ū�ʱ��Ѥ�, �͡��ʿ���λ�����ǡ����Υ��ڥ��ȥ���Ϥ�, Ϳ����
�줿�ǡ����ˤɤμ��ȿ�����ʬ��¿���ޤޤ�뤫�Ȥ��ä��׻��ˤ�, $N$��Ĺ
���Ȥ��Ȥ���FFT���������ä˰��Ϥ�ȯ�����ޤ�. �ǡ����Υ��ڥ��ȥ����
��, ������Ф���FFT�α��ѤˤĤ��Ƥ�, ����(1977)�򻲾Ȥ������ɤ��Ǥ���
��.

FFT�ι�®������ǽ�ˤ�����Τΰ�Ĥ�, ���ڥ��ȥ�ˡ�ȸƤФ������ʬ����
���β�ˡ������ޤ�. �㤨��,
\begin{equation}
\frac{\partial u}{\partial t}+u\frac{\partial u}{\partial x}=0,
\quad \mbox{�������:}\ u(x+2\pi,t)=u(x,t),
\end{equation}
�Τ褦������ʬ�����������Ū�˲򤯾���ͤ��ޤ��礦.
��ŵŪ�ʺ�ʬˡ�Ǥ�$x$��������ֳ֤�ʬ��
$x_j=(2\pi/N)j, \quad (j=0,1,\cdots,N-1)$��Ȥä�, 
����ʬ$\partial u/\partial x$��ʬ���֤κ�ʬ�Ƕ������ΤǤ���, 
���ڥ��ȥ�ˡ��, FFT�ˤ�ä�$u(x,t)$��Fourier���Ÿ������, ����ʬ��
����Fourier���Ÿ������Ŭ�Ѥ��뤳�Ȥˤ�äƺ�ʬ������ʤ�����, �����
̩�ʲ����褦�Ȥ����ˡ�Ǥ�.
���β�ˡ��, ��ή�Υ��ߥ�졼������, ����Ū��ŷ��ͽ��η׻����Ѥ����
�Ƥ��ޤ�. ���β���Ǥ��Ф���̾����Ф��� Clive Temperton ��, ���⤽��
ECMWF(= European Centre for Medium-Range Weather Forecasts: �衼���å�
���ŷ��ͽ�󥻥󥿡�)�Υ����åդǤ���, ŷ��ͽ��η׻��˻Ȥ������, FFT
�μ����ˤĤ��Ƥθ����ԤäƤ����櫓�Ǥ�.
���ڥ��ȥ�ˡ�ˤĤ��Ƥ�, Canuto, {\it et al.}
(1988)�����˾ܤ������ʽ�Ǥ��Τ�, ��̣�Τ������Ϥ�����򻲾Ȥ��Ƥߤ�
������.

�ޤ�, �Ƕ�Ǥ�, JPEG��MPEG�Τ褦��, �Ż߲��ư��Υǡ����ΰ��̤ˤ�
FFT���Ȥ��Ƥ��ޤ�
\footnote{��̩�ˤ�, DCT(= Discrete Cosine Transform: Υ�����������Ѵ�)
�Ǥ���, DFT�μ¿���ʬ������Ȥ�������褦�ʤ�Τ�, FFT������Ʊ���褦��
���르�ꥺ��ǹ�®������ޤ�.}.
�������̤�FFT���ɤΤ褦�˻Ȥ��Ƥ��뤫�ˤĤ��Ƥ�,
�ĸ�(1997)�˾Ҳ𤵤�Ƥ��ޤ�.

\section{������}

�����ޤ�, ���ä�FFT�δ��ܤˤĤ��Ʋ��⤷�Ƥ��ޤ�����, FFT�Τ褦�ʥ��르
�ꥺ��ο�������Τ���ˤ�, ��ξ�Ǥη׻������ǤϤʤ�, ��ʬ���ȤǷ׻�
���ץ�������񤤤Ƥߤ뤳�Ȥ���ƻ�Ǥ��Τ�, �ץ�����ߥ󥰤Ǥ���Ķ���
���äƤ������Ϥ��ҡּ�ʬ�ʤ�μ���FFT�ץ������פ��äƤߤ����
�褤�Ȼפ��ޤ�.
����FFTW�Τ褦�ʡ֥ץ��פν񤤤������Υ��եȥ������ˤϤʤ��ʤ������Ǥ�
�Ǥ��ޤ��󤫤�, �ִ��ˤ����Τ��ȯ�����褦�Ȥ���Τϥ���פȻפ���
���⤷��ޤ���.
������,������դΡֶ�����˴�ˡפǤϤ���ޤ���, FFT�Τ褦�ʡֵ��ѡ�
�����ѡפˤ��Ƥ��ޤ�ʤ�����ˤ�, ����, ��ͤ��ηä����θ�����������,
�֤�ä���, ��ʬ����äȤ������եȤ�񤤤���.�פȤ������餤�ε������
������¿������Ƥۤ����ȻפäƤ��ޤ�.

\section{����ʸ��}

\begin{description}
\item Bergland, G. D., 1967:
The Fast Fourier Transform Recursive Equations for Arbitrary Length
Records,
{\it Math. Comp.}, {\bf 21}, 236--238.
\item Brigham, E. Oran, 1974: {\it The Fast Fourier Transform},
Prentice-Hall.
(ˮ��: �����Ρ����潨�� ��, 1978, �ֹ�®�ա��ꥨ�Ѵ��ײʳص��ѽ��Ǽ�,
262pp.)
\item Good, I. J., 1958:
The Interaction of Algorithm and Practical Fourier Series,
{\it J. Roy. Statist. Soc. Ser. B}, {\bf 20}, 361--372.
\item Canuto, C., M. Y. Hussaini, A. Quarteroni, and T. A. Zang, 1988:
{\it Spectral Methods in Fluid Dynamics.} Springer, 567pp.
\item Cooley, J. W. and J. W. Tukey, 1965:
An Algorithm for the Machine Calculation of Complex Fourier Series,
{\it Math. Comp.}, {\bf 19}, 297--301.
\item ���ͺ, 1977: ���ڥ��ȥ����,
ī�ҽ�Ź, 300pp.
\item Rader, C. M., 1968: 
Discrete Fourier Transforms When the Number of Data Samples is Prime,
{\it Proc. IEEE}, {\bf 5}, 1107--1108.
\item �ĸ�����, 1997: MPEG --���󥿡��ͥåȻ���α�������,
bit�̺��֥��󥿡��ͥåȻ���ο��ء�, ��Ω����.
\item Temperton, C., 1983: 
Self-Sorting Mixed-Radix Fast Fourier Transforms,
{\it J. Comp. Phys.}, {\bf 52}, 1--23.
\item Temperton, C., 1988: 
Nesting Strategies for Prime Factor FFT Algorithms,
{\it J. Comp. Phys.}, {\bf 82}, 247--268.
\item Temperton, C., 1992: 
A Generalized Prime Factor FFT Algorithm for Any N=$2^p3^q5^r$,
{\it SIAM J. Sci. Stat. Comput.}, {\bf 13}, 676--686.
\item Winograd, S., 1978: 
On Computing the Discrete Fourier Transform,
{\it Math. Comp.}, {\bf 32}, 175--199.
\end{description}

\end{document}