離散Fourier変換 (Modified:2005-04-20)

離散Fourier変換の概念を可換環R上へ一般化し、複素数上や整数の剰余環上の離散Fourier変換の性質や高速算法の議論を統一的に行なえるようにすることを目的とする。最初に離散Fourier変換を可換環R上で定義し、その諸性質を整理する。その上で高速算法について論ずる。

条件1.1 (離散Fourier変換を定義するための必要条件)
　Rを可換環とする。

∃n:自然数,∃ζ∈R:ζは1の原始n乗根 (i.e. ζⁿ=1, n>k>0 → ζ^k≠1)
∃n^-1∈R (i.e. nをRの元とみなしたときにその逆元が存在する)
n>k>0 → ∑_i=0^n-1ζ^ik=0

　上の条件の下で、ζによって生成される巡回群をG={1,ζ,…,ζ_n-1}とする。GからRへの関数全体の集合をC(G)={f:G→R}とすると、C(G)にはRから自然に加法と乗法が定義され、それによって可換環となる。さらにスカラー倍を自然に定義することによってR上の多元環となる。

定義1.2 (C(G)上の双線形形式( , ))
　C(G)上の双線形形式( , ):C(G)×C(G)→Rを次のように定義する。

(f,g)

n^-1

n-1
Σ
i=0

f(ζⁱ)g(ζ^-i)

　f,g∈C(G)

　上の定義でζ^-i=ζ^n-iであることに注意せよ。これがR上の双線形形式になることは明らかなので証明は略す。次の定理は、C(G)がこの双線形形式について直交な基底をもつことを示す。

定理1.3 (C(G)上の標準直交基底とそのFourier展開)
　k=0,…,n-1についてe_k(ζⁱ)=ζ^ikによってe_k:C(G)→Rを定義すると{e_k:k=0,…,n-1}はC(G)の直交基底となる。すなわち、任意のf∈C(G)は、

n-1
Σ
i=0

(f,e_i)e_i

と一意的に表現することができる。これをfのFourier展開と呼ぶ。

証明　

(e_k,e_l)

n^-1

n-1
Σ
i=0

ζ^ikζ^-il

n^-1

n-1
Σ
i=0

ζ^i(k-l)

ここで、条件3.を使うと

(e_k,e_l)

　k≠l

(e_k,e_l)

　k=l

となり、{e_k:k=0,…,n-1}が互いに直交していることがわかる。∑_i=0^n-1λ_ie_i=0と仮定すると、k=0,…,n-1に対して

λ_k

n-1
Σ
i=0

λ_i(e_i,e_k)

(

n-1
Σ
i=0

λ_ie_i

,e_k)

となるから、{e_k:k=0,…,n-1}は線形独立である。f∈C(G),k=0,…,n-1について、

n-1
Σ
i=0

(f,e_i)e_i(ζ^k)

n-1
Σ
i=0

(n^-1

n-1
Σ
l=0

f(ζ^l)ζ^-il

)ζ^ik

n^-1

n-1
Σ
l=0

f(ζ^l)

(

n-1
Σ
i=0

ζ^i(k-l)

)

n^-1f(ζ^k)(

n-1
Σ
i=0

ζ⁰

)

f(ζ^k)

となることから証明が終了する。ここでも条件3.が使われている。 ■

定義1.4 (Fourier変換・逆Fourier変換)
　Fourier変換F:C(G)→C(G)を次のように定義する。

F(f)(ζ^k)

n-1
Σ
s=0

f(ζ^s)ζ^sk

　f∈C(G),

　k=0,…,n-1

逆Fourier変換F^-1:C(G)→C(G)を次のように定義する。

F^-1(f)(ζ^r)

n^-1

n-1
Σ
t=0

f(ζ^t)ζ^-tr

　f∈C(G),

　r=0,…,n-1

定理1.5 (R-加群としての同型性)
　Fourier変換F:C(G)→C(G)はR-加群としての同型写像を与え、逆Fourier変換F^-1はその逆写像である。

証明　線形性は明らかである。条件3.を使うことによって以下のように同型性を示すことができる。

F^-1・F(f)(ζ^r)

n^-1

n-1
Σ
t=0

F(f)(ζ^t)ζ^-tr

n^-1

n-1
Σ
t=0

(

n-1
Σ
s=0

f(ζ^s)ζ^st

)ζ^-tr

n^-1

n-1
Σ
s=0

f(ζ^s)(

n-1
Σ
t=0

ζ^t(s-r)

)

n^-1f(ζ^r)(

n-1
Σ
t=0

ζ⁰)

f(ζ^r)

F・F^-1(f)(ζ^k)

n-1
Σ
s=0

F^-1(f)(ζ^s)ζ^sk

n-1
Σ
s=0

(n^-1

n-1
Σ
t=0

f(ζ^t)ζ^-ts

)ζ^sk

n^-1

n-1
Σ
t=0

f(ζ^t)(

n-1
Σ
s=0

ζ^s(k-t)

)

n^-1f(ζ^k)(

n-1
Σ
s=0

ζ⁰

)

f(ζ^k)

■

定義1.6 (C(G)上の畳み込み)
　f,g∈C(G)に対して、畳み込みf*g∈C(G)を次のように定義する。

f*g(ζ^r)

n-1
Σ
i=0

f(ζ^r-i)g(ζⁱ)

　r=0,…,n-1

　C(G)はこの畳み込みを積としても可換環となり、さらにR上の多元環となる。これをGのR上の群環と呼び、R[G]と書く。C(G)とR[G]はR-加群としては同じものであるが、積の違いを区別するために記号を使い分ける。

命題1.7
　R[G]はR上の可換な多元環である。

δ∈R[G]:δ(1)=1, δ(ζⁱ)=0, i=1,…,n-1 とすると f*δ=f, f∈R[G]
f*g=g*f, f,g∈R[G]
f*(g*h)=(f*g)*h, f,g,h∈R[G]
f*(g+h)=f*g+f*h, f,g,h∈R[G]
(λf)*g=λ(f*g), λ∈R, f,g∈R[G]

証明　1.は直接計算する。

f*δ(ζ^r)

n-1
Σ
i=0

f(ζ^r-i)δ(ζⁱ)

f(ζ^r)

2.はr-i=tと変数変換すればよい。

f*g(ζ^r)

n-1
Σ
i=0

f(ζ^r-i)g(ζⁱ)

n-1
Σ
i≡0(mod n)

f(ζ^r-i)g(ζⁱ)

r
Σ
t=r-(n-1)

f(ζ^t)g(ζ^r-t)

g*f(ζ^r)

3.は可換性を利用する。

f*(g*h)(ζ^r)

n-1
Σ
i=0

(g*h)(ζ^r-i)f(ζⁱ)

n-1
Σ
i=0

(

n-1
Σ
j=0

g(ζ^(r-i)-j)h(ζ^j)

)f(ζⁱ)

n-1
Σ
j=0

(

n-1
Σ
i=0

g(ζ^(r-j)-i)f(ζⁱ)

)h(ζ^j)

n-1
Σ
j=0

(f*g)(ζ^r-j)h(ζ^j)

(f*g)*h(ζ^r)

4.と5.は明らかである。 ■

定理1.8 (R-多元環としての同型性)
　Fourier変換F:R[G]→C(G)はR-多元環としての同型写像を与え、逆Fourier変換F^-1はその逆写像である。すなわち、同値な性質

F(f*g)=F(f)F(g), f,g∈R[G]
F^-1(fg)=F^-1(f)*F^-1(g), f,g∈C(G)
F(fg)=F(f)*F(g), f,g∈C(G)
F^-1(f*g)=F^-1(f)F^-1(g), f,g∈R[G]

が成り立つ。

証明　1.のみを証明すればよい。

F(f*g)(ζⁱ)

n-1
Σ
s=0

f*g(ζ^s)ζ^si

n-1
Σ
s=0

(

n-1
Σ
t=0

f(ζ^s-t)g(ζ^t)

)ζ^si

n-1
Σ
s=0

n-1
Σ
t=0

f(ζ^s-t)ζ^(s-t)ig(ζ^t)ζ^ti

n-1
Σ
t=0

(

n-1
Σ
s=0

f(ζ^s-t)ζ^(s-t)i

)g(ζ^t)ζ^ti

n-1
Σ
t=0

F(f)(ζⁱ)g(ζ^t)ζ^ti

F(f)(ζⁱ)F(g)(ζⁱ)

■

定理1.9 (構造定理)
　R上の多項式環R[X]からR[G]へのR-線形写像を

X^r

→

e_r,

　r=0,…,n-1

を線形拡張するように定義する。この核は(Xⁿ-1)であり、R[X]/(Xⁿ-1)とR[G]はR-加群として同型である。さらに、この同型写像はR-多元環としての同型を与える。

証明　R-加群として同型であることは明らかである。a(X),b(X)∈R[X]/(Xⁿ-1)を

a(X)

a_n-1X^n-1

…

a₁X

a₀,

　a_i∈R,

　i=0,…,n-1

b(X)

b_n-1X^n-1

…

b₁X

b₀,

　b_i∈R,

　i=0,…,n-1

とすると、同型写像は

a_s

→

a(ζ^s),

　b_t

→

b(ζ^t)

というような対応により、a,b∈R[G]を定める。c(X)=a(X)b(X)∈R[X]/(Xⁿ-1)とすると

c(X)

c_n-1X^n-1

…

c₁X

c₀,

　c_i∈R

c_r

Σ
s+t≡r(mod n)

a_sb_t

となるが、この係数は同型写像により、

c(ζ^r)

n-1
Σ
i=0

a(ζ^r-i)b(ζⁱ)

に対応するが、これはc=a*bを示している。 ■

　今後、上の対応によってR[X]/(Xⁿ-1)とR[G]を同一視する場合がある。その場合、上の記号で多項式の係数a_i∈Rの添え字はnを法として考える。もし、iが0,…,n-1以外の値をとるときは、暗黙のうちにi ← i%nという変換を施すことにする。

　次節で高速Fourier変換について論ずるが、Fourier変換が高速に計算できることを利用してR[X]/(Xⁿ-1)の乗算を高速に行なうことができる。

算法1.10 (多項式の高速乗算法)
　a(X),b(X)∈R[X]/(Xⁿ-1)を

a(X)

a_n-1X^n-1

…

a₁X

a₀,

　a_i∈R,

　i=0,…,n-1

b(X)

b_n-1X^n-1

…

b₁X

b₀,

　b_i∈R,

　i=0,…,n-1

その積c(X)=a(X)b(X)∈R[X]/(Xⁿ-1)を

c(X)

c_n-1X^n-1

…

c₁X

c₀,

　c_i∈R

c_r

n-1
Σ
i=0

a_r-ib_i

と表現する。この計算を次の手順で行なう。

Step 1.(a₀,…,a_n-1),(b₀,…,b_n-1)に対して、そのFourier変換(a'₀,…,a'_n-1),(b'₀,…,b'_n-1)を計算する。
Step 2. 項毎に乗算して(c'₀,…,c'_n-1)=(a'₀b'₀,…,a'_n-1b'_n-1)とする。
Step 3.(c'₀,…,c'_n-1)に対して、その逆Fourier変換(c₀,…,c_n-1)を計算する。

補題2.1
　可換環Rが自然数Nと2Nについて、離散Fourier変換の必要条件を満たし、G_Nを1の原始N乗根ζ_Nから生成される巡回群、G_2Nを1の原始2N乗根ζ_2Nから生成される巡回群であり、さらに

ζ_2N²

ζ_N

が成り立ち、G_N⊂G_2Nとなっていると仮定する。このとき、R[G_N]の元に対するFourier変換が高々M回の加算と乗算で計算できるとすれば、R[ζ_2N]の元に対するFourier変換は高々2M+6N回の加算と乗算で計算できる。

証明　f∈R[ζ_2N]に対して、f_even,f_odd∈R[ζ_N]を

f_even(ζ_N^u)

f(ζ_2N^2u),

　u=0,…,N-1

f_odd(ζ_N^v)

f(ζ_2N^2v+1),

　v=0,…,N-1

によって定める。fのFourier変換について、次の式が成り立つ。

F(f)(ζ_2N^k)

2N-1
Σ
i=0

f(ζ_2Nⁱ)ζ_2N^ik

N-1
Σ
u=0

f(ζ_2N^2u)ζ_2N^2uk

N-1
Σ
v=0

f(ζ_2N^2v+1)ζ_2N^(2v+1)k

N-1
Σ
u=0

f_even(ζ_N^u)ζ_N^uk

N-1
Σ
v=0

f_odd(ζ_N^v)ζ_N^vkζ_2N^k

F(f_even)(ζ_N^k)

F(f_odd)(ζ_N^k)ζ_2N^k

ζ_2N^k, k=0,…,2N-1は高々2N回の乗算で計算できる。また仮定より、F(f_even)とF(f_odd)は高々2M回で計算できる。これらと上の式を利用するとF(f)は高々2M+6N回の加算と乗算で計算できることがわかる。 ■

定理2.2 (Cooley-Tukey型高速算法)
　可換環Rが自然数N=2ⁿとそのすべての約数について、離散Fourier変換の必要条件を満たし、K|NならばG_K⊂G_Nとなっていると仮定する。このとき、ζ_Nが与えられたとすると、R[G_N]の元に対するFourier変換は高々n2ⁿ⁺²=4Nlog₂N回の加算と乗算で計算できる。

証明　M(n)でN=2ⁿの場合にFourier変換の計算に要する加算と乗算の回数を表わす。nに関する帰納法で証明する。n=1のとき、

F(f)(ζ⁰)

f(ζ⁰)ζ⁰

f(ζ¹)ζ⁰

f(ζ⁰)

f(ζ¹)

F(f)(ζ¹)

f(ζ⁰)ζ⁰

f(ζ¹)ζ¹

f(ζ⁰)

f(ζ¹)ζ¹

より、M(1)=3≦1×2¹⁺²となる。M(n)≦n2ⁿ⁺²であると仮定すると補題より、

M(n+1)

≦

2M(n)

6×2ⁿ

≦

2M(n)

8×2ⁿ

(n+1)2ⁿ⁺³

となり、帰納法により証明された。 ■

離散Fourier変換

梅谷武

目　　次

離散Fourier変換

梅谷 武

目 次

梅谷武

目　　次