-- https://en.wikipedia.org/w/index.php?title=
-- Discrete_Fourier_transform&action=edit§ion=3
--
X ==> EXPR COMPLEX INT
Type: Void
fricas
a:=convert(zerosOf(z^4-1).2)$ROU(4,X)
Type: RootOfUnity
?(4,
Expression(Complex(Integer)))
fricas
F ==> DFT(X,4,inv a) -- Note: inv(a) gives another result than a !!!
Type: Void
fricas
m:=dftMatrix()$F
Type: Matrix(Expression(Complex(Integer)))
fricas
v:=vector [1::X,2-%i,-%i,-1+2*%i]
Type: Vector(Expression(Complex(Integer)))
fricas
w:=dft(v)$F
Type: Vector(Expression(Complex(Integer)))
fricas
test(w=m*v)
Type: Boolean
fricas
test(idft(w)$F=v)
Type: Boolean
fricas
determinant(m/2)
Type: Expression(Complex(Integer))
fricas
-- Examples
-----------
R:=IntegerMod 5
Type: Type
fricas
a:=2::R
fricas
n:=4
fricas
DFTZ5==>DFT(R,n,a)
Type: Void
fricas
dftMatrix()$DFTZ5
Type: Matrix(IntegerMod
?(5))
fricas
dftInvMatrix()$DFTZ5
Type: Matrix(IntegerMod
?(5))
fricas
dft([1,2,3,4])$DFTZ5
Type: Vector(IntegerMod
?(5))
fricas
idft([0,4,3,2])$DFTZ5
Type: Vector(IntegerMod
?(5))
fricas
-- R:=Expression Complex Integer
-- n:=3
-- a:=exp(-2*%i*%pi/n)
-- ... no!
M:=udftMatrix()$UDFT(5)
Type: Matrix(Expression(Complex(Integer)))
fricas
d:=determinant(M)
Type: Expression(Complex(Integer))
fricas
test(d=1) -- test false does not necessarily mean d<>1
Type: Boolean
fricas
test(d^2=1) -- true
Type: Boolean
fricas
r:=retract(d) --
fricas
test(r=1) -- true :)
Type: Boolean
fricas
)set mess time on
N:=20 -- 20 is quick, 50 ~12sec, 100 ?long
fricas
Time: 0 sec
M:=udftMatrix()$UDFT(N)
Type: Matrix(Expression(Complex(Integer)))
fricas
Time: 0.12 (EV) + 0.01 (OT) = 0.13 sec
IM:=udftInvMatrix()$UDFT(N)
Type: Matrix(Expression(Complex(Integer)))
fricas
Time: 0.06 (EV) = 0.06 sec
w:=M*vector([i for i in 1..N])
Type: Vector(Expression(Complex(Integer)))
fricas
Time: 0.01 (IN) + 0.02 (EV) = 0.03 sec
IM*w
Type: Vector(Expression(Complex(Integer)))
fricas
Time: 0.03 (EV) = 0.03 sec
E:=M*IM -- needs some time!
Type: Matrix(Expression(Complex(Integer)))
fricas
Time: 0.46 (EV) = 0.46 sec
trace(E) -- N
fricas
Time: 0 sec
--)synonym lispversion )lisp (lisp-implementation-version)
map(x+->x::Complex Float,m)
Type: Matrix(Complex(Float))
fricas
Time: 0.01 (EV) = 0.01 sec
fN:=complexNumeric(exp(-2*%pi*%i/N))
Type: Complex(Float)
fricas
Time: 0.02 (OT) = 0.02 sec
MF:=map(x+->subst(x,%z5=fN),M)
Type: Matrix(Expression(Complex(Float)))
fricas
Time: 0.68 (IN) + 0.02 (EV) + 0.07 (OT) = 0.77 sec
trace(MF) -- 1+i
Type: Complex(Float)
fricas
Time: 0.01 (IN) = 0.01 sec
determinant(MF) -- -i
Type: Expression(Complex(Float))
fricas
Time: 0.02 (EV) = 0.02 sec