線形代数 · 第25回 · 動画3 · インタラクティブ教材

行列が自分を半分に割る：高速フーリエ変換の再帰のしくみ

I重要な公式

公式	名称	説明
$w_n = e^{2\pi i / n}$	1 の原始 $n$ 乗根	$F_n$ の成分は $w_n$ のべき乗
$(w_n)^2 = w_{n/2}$	二乗の恒等式	$F_n$ と $F_{n/2}$ を結びつける
$F_n = \begin{bmatrix} I & D \\ I & -D \end{bmatrix} \begin{bmatrix} F_{n/2} & 0 \\ 0 & F_{n/2} \end{bmatrix} P$	FFT の分解	3 つの因子への分解
$T(n) = \tfrac{n}{2}\log_2 n$	FFT の計算量	素直な計算では $n^2$

II1 の冪根を二乗する

$n$ 乗根をそれぞれ二乗すると角度が 2 倍になり、 $n$ 個の点が $n/2$ 乗根の上に重なります。

n 8 二乗

💡 つまり $F_n$ の中には $F_{n/2}$ が隠れています。同じ $n/2$ 個の根が再び現れ、それがちょうど小さいほうの変換になるのです。

III素直な計算の計算量と FFT の計算量

変換の大きさ $n$ が増えるにつれて、 $n^2$ と $\tfrac{n}{2}\log_2 n$ はどう比べられるでしょうか。

log₂ n 1,024

💡 差は限りなく広がります。そのため、素直に計算すればとても手に負えない 100 万点の変換も、FFT ならリアルタイムで計算できます。

IV再帰の木

分割するたびにブロックの数は 2 倍、大きさは半分になるので、どの段の計算量も同じ $n/2$ です。

n 深さ

V確認クイズ

問1

$w_{64} = e^{2\pi i / 64}$ を 1 の原始 64 乗根とします。 $(w_{64})^2$ は何に等しいでしょうか。

✅ 正解です！ 二乗すると角度が 2 倍になり、位数は半分になります。

❌ 惜しい！ 思い出しましょう。 $e^{i\theta}$ を二乗すると $e^{i \cdot 2\theta}$ になります。 $2\pi/n$ の形の角度を 2 倍にすると $2\pi/(n/2)$ です。

解答を見る

解答：

指数関数を二乗すると角度が 2 倍になります。 $(w_{64})^2 = \left(e^{2\pi i / 64}\right)^2 = e^{4\pi i / 64} = e^{2\pi i / 32} = w_{32}.$

これが FFT の要となる恒等式 $(w_n)^2 = w_{n/2}$ です。この恒等式によって、 $F_n$ の中に $F_{n/2}$ が隠れていることが保証されます。

問2

$n = 1024$ のとき、FFT の分解を1 回だけ使う（1 段だけ分割する）と、素直な $n^2$ の方法と比べて複素数の掛け算はどれだけ減るでしょうか。

ヒント：1 段の計算量は $2 \cdot (n/2)^2 + n/2$ 回の掛け算です。

✅ 正解です！ 1 回の分割で約 2 倍速くなります。劇的な高速化は、これを再帰的に使うことで生まれます。

❌ 惜しい！ $2(n/2)^2 + n/2$ と $n^2$ を計算して比べましょう。比はおよそ $1/2$ です。

解答を見る

解答：

素直な計算の計算量： $n^2 = 1024^2 = 1{,}048{,}576$ 。

1 段だけの FFT の計算量： $2 \cdot (n/2)^2 + n/2 = 2 \cdot 512^2 + 512 = 524{,}288 + 512 = 524{,}800$ 。

元の手間のほぼ半分です。分解を 1 回使っただけで約 2 倍速くなります。大きな高速化は、この分解を最下段まで再帰的に使うことで得られます。

問3

再帰を最後まで使った FFT では、 $n = 1024$ のとき複素数の掛け算は何回必要でしょうか。

✅ 正解です！ $(1024/2)\cdot \log_2(1024) = 512 \cdot 10 = 5{,}120$ .

❌ 惜しい！ 公式 $(n/2)\log_2 n$ を $\log_2(1024) = 10$ として使いましょう。

解答を見る

解答：

FFT の計算量は $\tfrac{n}{2}\log_2 n$ です。

$n = 1024$ のとき $\frac{1024}{2} \cdot \log_2(1024) = 512 \cdot 10 = 5{,}120.$

素直な計算の $n^2 = 1{,}048{,}576$ と比べると、約 205 倍の高速化です。

問4

正しいか誤りか：FFT は素直な行列とベクトルの積とは異なる（近似的な）変換を計算し、精度と引き換えに速さを得ている。

✅ 正解です！ この分解は厳密な代数的恒等式です。同じ DFT を、より速く計算します。

❌ 惜しい！ FFT は近似ではなく厳密なアルゴリズムです。まったく同じ DFT を計算します。

解答を見る

解答：

FFT は、素直な方法とまったく同じ離散フーリエ変換を計算します。同じ行列 $F_n$ 、同じ出力、浮動小数点の丸め誤差を除けば同じ数値です。変わるのは道筋だけです。

分解 $F_n = \begin{bmatrix} I & D \\ I & -D \end{bmatrix} \begin{bmatrix} F_{n/2} & 0 \\ 0 & F_{n/2} \end{bmatrix} P$ は近似ではなく、厳密な代数的恒等式です。置換 $P$ の掛け算は 0 回（ポインタの計算だけ）なので、浮動小数点の演算は回転因子の掛け算と、再帰的な小さい FFT の中にしかありません。

正解数：0 / 4