Skip to content

Instantly share code, notes, and snippets.

@t-nissie
Last active October 2, 2016 11:23
Show Gist options
  • Save t-nissie/831940161039db8a9da6 to your computer and use it in GitHub Desktop.
Save t-nissie/831940161039db8a9da6 to your computer and use it in GitHub Desktop.
離散フーリエ変換 (DFT) ・高速フーリエ変換 (FFT) の演習問題

Exercises for discrete Fourier transform (DFT) and fast Fourier transform (FFT)

We fourier-transform eight complex data sampled at eight points (X=0a, 1a, 2a, 3a, 4a, 5a, 6a, 7a, where a is the unit cell length). Answer following questions.

Here, $ indicates the command-line prompt.

Keywords: Born-von Karman boundary condition, first Brillouin zone, phonon, k-point

Exercises

Q1

Using the command git(1),

$ git clone https://gist.github.com/831940161039db8a9da6.git fft8exercise

you can download 6+ files of Makefile, fft8.dat, fft8.f, fft8.gp, fft8_fwd.f, fft8_inv.f in fft8exercise/.

The command make(1) comiles and executes files according to the dependences written in Makefile.

$ make clean
$ make -n

shows

gfortran -g -Wall -ffree-form  -c -o fft8.o fft8.f
gfortran -g -Wall -ffree-form  -c -o fft8_fwd.o fft8_fwd.f
gfortran -g -Wall -ffree-form  -c -o fft8_inv.o fft8_inv.f
gfortran -o fft8 -g -Wall -ffree-form fft8.o fft8_fwd.o fft8_inv.o
./fft8 < fft8.dat > fft8.coefficients
gnuplot fft8.gp

Describe the meanings of each lines and roles of 6 files.

Q2

Describe each lines in main program fft8.f.

You can

$ make

fft8.coefficients and fft8.eps. Then,

$ gv fft8.eps &
$ lpr fft8.eps
$ epstopdf fft8.eps

you can preview or print out the figure of fft8.eps. You can also convert fft8.eps into fft8.pdf (Fig.1).

Describe each lines in fft8.gp. Why c5 is not the coefficient for exp(i (5/8) (2π/a) x) but for exp(-i (3/8) (2π/a) x).

samples

Fig.1: Periodic eight complex data, which is connected with a linear combination of sin and cos.

Q3

Compare the input file fft8.dat and the output file fft8.coefficients.

Q4

フーリエ係数 c0 はデータの平均値になっていることを確認せよ.また,それはなぜか.

Advanced exercise

Q5

exp(i k x) (where k/(2π/a) = -3/8, -2/8, -1/8, 0, 1/8, 2/8, 3/8, 4/8) の線形結合で作った曲線(図1)はfft8.dat中の8つのデータを再現している. しかしながら,fft8.dat中のデータの虚部は偶関数(x=0で対称)でかつx=4aで対称なのに, 曲線はそのようになっていない.改善せよ.

Q6

入力ファイルfft8.dat中のデータの虚部をすべてゼロにしてから,もういちど

$ make

とせよ.新しいfft8.coefficientsを見て,c4の虚部が0であることを確認せよ.

conjg(c(-k)) = c(k)

であることを確認せよ.データが実数の場合,上の式が成り立つことを証明せよ.

Q7

サンプリング点が9個や16個のときに同様のことができるプログラムを作れ. 高速フーリエ変換のサブルーチンは自分で作るなり,ネットでみつけてくるなり工夫せよ. 「高速フーリエ変換 (fast Fourier transform)」「FFT」「FFTW」などを キーワードとして検索すると見つかるかもしれない.

Q8

FFTの準備として sin(2πi/N) と cos(2πi/N) を 0<=i<N について計算しておく必要がある. しかし,浮動小数点演算の性質から sin(π/2)=1, cos(π/2)=0, sin(π/4)=cos(π/4) 等が必ずしも保障されない.よって、0<=i<=N/8,すなわち 0<=θ<=π/4のsinθ, cosθ と 三角関数の対称性を使って計算するほうが,直截に(straight forwardに)計算するより, 速くてよい精度が得られることを説明せよ.

離散フーリエ変換 (DFT) ・高速フーリエ変換 (FFT) の演習問題

8個の点(X=0a, 1a, 2a, 3a, 4a, 5a, 6a, 7a, where a is the unit cell length) で サンプリングした8個の複素数データ fft8.dat を高速フーリエ変換する.次の問に答えよ.

なお,$はコマンドプロンプトを表す.

Keywords: Born-von Karman boundary condition, 第一ブリルアンゾーン,フォノン,k-point

問題

Q1

git(1)というコマンドを用いて,

$ git clone https://gist.github.com/831940161039db8a9da6.git fft8exercise

とすると,fft8exercise/ディレクトリ以下に Makefile, fft8.dat, fft8.f, fft8.gp, fft8_fwd.f, fft8_inv.f の6つのファイル他が ダウンロードされる.

make(1)Makefileに書かれた依存関係にしたがって,ファイルをコンパイルしたり,実行したりする.

$ make clean
$ make -n

とすると

gfortran -g -Wall -ffree-form  -c -o fft8.o fft8.f
gfortran -g -Wall -ffree-form  -c -o fft8_fwd.o fft8_fwd.f
gfortran -g -Wall -ffree-form  -c -o fft8_inv.o fft8_inv.f
gfortran -o fft8 -g -Wall -ffree-form fft8.o fft8_fwd.o fft8_inv.o
./fft8 < fft8.dat > fft8.coefficients
gnuplot fft8.gp

と表示される.それぞれの行の意味と6つのファイルの役割を簡単に説明せよ.

Q2

メインプログラムfft8.fの各行の役割を簡単に説明せよ.

$ make

とするとfft8.coefficientsfft8.epsができる.

$ gv fft8.eps &
$ lpr fft8.eps
$ epstopdf fft8.eps

とするとfft8.epsを画面に表示したり,印刷したり,PDFファイルfft8.pdfに変換できたりする(図1).

fft8.gpの各行の役割を簡単に説明せよ. なぜ c5 は exp(i (5/8) (2π/a) x) の 係数でなく exp(-i (3/8) (2π/a) x) の係数になっているのか.

samples

図1.周期的な8点の複素数データと,フーリエ係数を使ってそれらをcos,sinの線形結合で結んだもの.

Q3

入力ファイルfft8.datとフーリエ係数などの入っている出力ファイル fft8.coefficientsを比較せよ.

Q4

フーリエ係数 c0 はデータの平均値になっていることを確認せよ.また,それはなぜか.

発展問題

Q5

exp(i k x) (where k/(2π/a) = -3/8, -2/8, -1/8, 0, 1/8, 2/8, 3/8, 4/8) の線形結合で作った曲線(図1)はfft8.dat中の8つのデータを再現している. しかしながら,fft8.dat中のデータの虚部は偶関数(x=0で対称)でかつx=4aで対称なのに, 曲線はそのようになっていない.改善せよ.

Q6

入力ファイルfft8.dat中のデータの虚部をすべてゼロにしてから,もういちど

$ make

とせよ.新しいfft8.coefficientsを見て,c4の虚部が0であることを確認せよ.

conjg(c(-k)) = c(k)

であることを確認せよ.データが実数の場合,上の式が成り立つことを証明せよ.

Q7

サンプリング点が9個や16個のときに同様のことができるプログラムを作れ. 高速フーリエ変換のサブルーチンは自分で作るなり,ネットでみつけてくるなり工夫せよ. 「高速フーリエ変換 (fast Fourier transform)」「FFT」「FFTW」などを キーワードとして検索すると見つかるかもしれない.

Q8

FFTの準備として sin(2πi/N) と cos(2πi/N) を 0<=i<N について計算しておく必要がある. しかし,浮動小数点演算の性質から sin(π/2)=1, cos(π/2)=0, sin(π/4)=cos(π/4) 等が必ずしも保障されない.よって、0<=i<=N/8,すなわち 0<=θ<=π/4のsinθ, cosθ と 三角関数の対称性を使って計算するほうが,直截に(straight forwardに)計算するより, 速くてよい精度が得られることを説明せよ.

( 0.1, 0.0 )
( 0.4, 0.0 )
( 0.3, 0.0 )
( -0.2, 0.0 )
( -0.3, -0.4 )
( 0.0, 0.0 )
( 0.1, 0.0 )
( 0.2, 0.0 )
! fft8.f -*-f90-*-
! Time-stamp: <2009-10-30 09:54:29 takeshi>
! Author: Takeshi NISHIMATSU
!!
program fft8
implicit none
complex*16 :: c(0:7)
integer :: i
read(5,*) (c(i),i=0,7)
call fft8_fwd(c)
c = c/8
do i=0,7
write(6,'("c",i1," = {",f13.9,",",f13.9,"}")') i, c(i)
end do
call fft8_inv(c)
write(6,'("# ",2f14.9)') (c(i),i=0,7)
end program fft8
#!/usr/bin/env gnuplot
# Time-stamp: <2015-11-23 21:41:06 takeshi>
# Author: Takeshi NISHIMATSU
##
# Calculate Fourier coefficients, then read the coefficients.
#!./fft8 < fft8.dat > fft8.coefficients
call 'fft8.coefficients'
set terminal postscript landscape enhanced color 'Times-Roman' 24
set encoding iso_8859_1
set output 'fft8.eps'
set title 'Example of Fourier transform with periodic 8 data'
set xrange [-4:12]
set xtics 4
set xlabel '{/Times-Italic x}/{/Times-Italic a}'
set yrange [-0.5:0.5]
set ytics 0.1
set format y '%.1f'
set grid
set key at 2.1,-0.35
N=8
plot 'fft8.dat' using ($0-N):2 t 'real({/Times-Italic c}({/Times-Italic X}))'\
w p lt 1 lw 4 pt 1 ps 2,\
'fft8.dat' using ($0 ):2 t '' w p lt 1 lw 4 pt 1 ps 2,\
'fft8.dat' using ($0+N):2 t '' w p lt 1 lw 4 pt 1 ps 2,\
'fft8.dat' using ($0-N):3 t 'imag({/Times-Italic c}({/Times-Italic X}))'\
w p lt 3 lw 4 pt 2 ps 2,\
'fft8.dat' using ($0 ):3 t '' w p lt 3 lw 4 pt 2 ps 2,\
'fft8.dat' using ($0+N):3 t '' w p lt 3 lw 4 pt 2 ps 2,\
real(c5*exp(-{0,1}*2*pi*3*x/N) + \
c6*exp(-{0,1}*2*pi*2*x/N) + \
c7*exp(-{0,1}*2*pi*1*x/N) + \
c0*exp( {0,1}*2*pi*0*x/N) + \
c1*exp( {0,1}*2*pi*1*x/N) + \
c2*exp( {0,1}*2*pi*2*x/N) + \
c3*exp( {0,1}*2*pi*3*x/N) + \
c4*exp( {0,1}*2*pi*4*x/N)) t '' lt 1 lw 2,\
imag(c5*exp(-{0,1}*2*pi*3*x/N) + \
c6*exp(-{0,1}*2*pi*2*x/N) + \
c7*exp(-{0,1}*2*pi*1*x/N) + \
c0*exp( {0,1}*2*pi*0*x/N) + \
c1*exp( {0,1}*2*pi*1*x/N) + \
c2*exp( {0,1}*2*pi*2*x/N) + \
c3*exp( {0,1}*2*pi*3*x/N) + \
c4*exp( {0,1}*2*pi*4*x/N)) t '' lt 3 lw 2
# Hint c4/2*exp(-{0,1}*2*pi*4*x/N) + \
#Local variables:
# compile-command: "make fft8.eps"
#End:
subroutine fft8_fwd(c)
implicit none
complex*16, intent(inout) :: c(0:*)
complex*16 tmp
tmp = c(1)
c(1) = c(4)
c(4) = tmp
tmp = c(3)
c(3) = c(6)
c(6) = tmp
tmp = (1.0d0,0.0d0) * c(1)
c(1) = c(0) - tmp
c(0) = c(0) + tmp
tmp = (1.0d0,0.0d0) * c(3)
c(3) = c(2) - tmp
c(2) = c(2) + tmp
tmp = (1.0d0,0.0d0) * c(5)
c(5) = c(4) - tmp
c(4) = c(4) + tmp
tmp = (1.0d0,0.0d0) * c(7)
c(7) = c(6) - tmp
c(6) = c(6) + tmp
tmp = (1.0d0,0.0d0) * c(2)
c(2) = c(0) - tmp
c(0) = c(0) + tmp
tmp = (1.0d0,0.0d0) * c(6)
c(6) = c(4) - tmp
c(4) = c(4) + tmp
tmp = (0.0d0,-1.0d0) * c(3)
c(3) = c(1) - tmp
c(1) = c(1) + tmp
tmp = (0.0d0,-1.0d0) * c(7)
c(7) = c(5) - tmp
c(5) = c(5) + tmp
tmp = (1.0d0,0.0d0) * c(4)
c(4) = c(0) - tmp
c(0) = c(0) + tmp
tmp = (0.707106781186548d0,-0.707106781186548d0) * c(5)
c(5) = c(1) - tmp
c(1) = c(1) + tmp
tmp = (0.0d0,-1.0d0) * c(6)
c(6) = c(2) - tmp
c(2) = c(2) + tmp
tmp = (-0.707106781186548d0,-0.707106781186548d0) * c(7)
c(7) = c(3) - tmp
c(3) = c(3) + tmp
end subroutine fft8_fwd
subroutine fft8_inv(c)
implicit none
complex*16, intent(inout) :: c(0:*)
complex*16 tmp
tmp = c(1)
c(1) = c(4)
c(4) = tmp
tmp = c(3)
c(3) = c(6)
c(6) = tmp
tmp = (1.0d0,0.0d0) * c(1)
c(1) = c(0) - tmp
c(0) = c(0) + tmp
tmp = (1.0d0,0.0d0) * c(3)
c(3) = c(2) - tmp
c(2) = c(2) + tmp
tmp = (1.0d0,0.0d0) * c(5)
c(5) = c(4) - tmp
c(4) = c(4) + tmp
tmp = (1.0d0,0.0d0) * c(7)
c(7) = c(6) - tmp
c(6) = c(6) + tmp
tmp = (1.0d0,0.0d0) * c(2)
c(2) = c(0) - tmp
c(0) = c(0) + tmp
tmp = (1.0d0,0.0d0) * c(6)
c(6) = c(4) - tmp
c(4) = c(4) + tmp
tmp = (0.0d0,1.0d0) * c(3)
c(3) = c(1) - tmp
c(1) = c(1) + tmp
tmp = (0.0d0,1.0d0) * c(7)
c(7) = c(5) - tmp
c(5) = c(5) + tmp
tmp = (1.0d0,0.0d0) * c(4)
c(4) = c(0) - tmp
c(0) = c(0) + tmp
tmp = (0.707106781186548d0,0.707106781186548d0) * c(5)
c(5) = c(1) - tmp
c(1) = c(1) + tmp
tmp = (0.0d0,1.0d0) * c(6)
c(6) = c(2) - tmp
c(2) = c(2) + tmp
tmp = (-0.707106781186548d0,0.707106781186548d0) * c(7)
c(7) = c(3) - tmp
c(3) = c(3) + tmp
end subroutine fft8_inv
# -*-Makefile-*- for fft8
# Time-stamp: <2015-11-23 20:24:18 takeshi>
##
FC = gfortran
FFLAGS = -g -Wall -ffree-form
fft8.eps: fft8.gp fft8.coefficients
gnuplot $<
fft8.coefficients: fft8 fft8.dat
./fft8 < fft8.dat > $@
fft8: fft8.o fft8_fwd.o fft8_inv.o
$(FC) -o $@ $(FFLAGS) $^
clean:
rm -f fft8 *.o core fft8.coefficients *.eps
Practice in Fourier transform Q1. Put 6 files in your current working directory: $ mkdir fft8 $ cd fft8/ $ cp -v /home/t-nissie/f/FFT8/FFT8-0.2/* . `/home/t-nissie/f/FFT8/FFT8-0.2/Makefile' -> `./Makefile' `/home/t-nissie/f/FFT8/FFT8-0.2/fft8.dat' -> `./fft8.dat' `/home/t-nissie/f/FFT8/FFT8-0.2/fft8.f' -> `./fft8.f' `/home/t-nissie/f/FFT8/FFT8-0.2/fft8.gp' -> `./fft8.gp' `/home/t-nissie/f/FFT8/FFT8-0.2/fft8_fwd.f' -> `./fft8_fwd.f' `/home/t-nissie/f/FFT8/FFT8-0.2/fft8_inv.f' -> `./fft8_inv.f' Then, check the Makefile: $ make clean $ make -n gfortran -g -Wall -ffree-form -c -o fft8.o fft8.f gfortran -g -Wall -ffree-form -c -o fft8_fwd.o fft8_fwd.f gfortran -g -Wall -ffree-form -c -o fft8_inv.o fft8_inv.f gfortran -o fft8 -g -Wall -ffree-form fft8.o fft8_fwd.o fft8_inv.o ./fft8 < fft8.dat > fft8.coefficients gnuplot fft8.gp Explain meanings of each line and roles of each files. Q2. Explain meanings of each line of main program fft8.f. With $ make you will get fft8.coefficients and fft8.eps. You can preview and print fft8.eps with $ gv fft8.eps $ lpr fft8.eps respectively. Tune the parameters in fft8.gp for pretty printing. Then, print fft8.eps. Q3. Compare the input file fft8.dat and the output file fft8.coefficients which contains Fourier coefficients. Q4. c(0) must be the average of real part of data. Why? *Advanced problems* Q5. At first glance, two curves of real and imaginary parts of the linear combination of exp(i 2pi k x), k = -3, -2, -1, 0, 1, 2, 3, 4, exactly reproduce data points in fft8.dat. However, the curve of imaginary part is not a even function, while the imaginary part in fft8.dat is a even function. Improve fft8.gp. Q6. (snip) Q7. Make similar program which can treat 16 data points. Subroutines of Fourier transform can be found in the Net. Use Google with keywords of "fast Fourier transform", "FFT", "Fortran", "FFTW", etc... Or you can make the subroutines by yourselves.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment