FFT的公式是什么和算法是怎样实现
二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：
先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：
for (int i=0; i<M; i++)
FFT_1D(ROW[i]，N);
for (int j=0; j<N; j++)
FFT_1D(COL[j]，M);
其中，ROW[i]表示矩阵的第i行。注意这只是一个简单的记法，并不能完全照抄。还需要通过一些语句来生成各行的数据。同理，COL[i]是对矩阵的第i列的一种简单表示方法。
所以，关键是一维FFT算法的实现。下面讨论一维FFT的算法原理。
【1D-FFT的算法实现】
设序列h(n)长度为N，将其按下标的奇偶性分成两组，即he和ho序列，它们的长度都是N/2。这样，可以将h(n)的FFT计算公式改写如下 ：
(A)
由于
所以，(A)式可以改写成下面的形式：
按照FFT的定义，上面的式子实际上是：
其中，k的取值范围是 0~N-1。
我们注意到He(k)和Ho(k)是N/2点的DFT，其周期是N/2。因此，H(k)DFT的前N/2点和后N/2点都可以用He(k)和Ho(k)来表示
FFT的算法
FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform），它根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。从DFT运算开始，说明FFT的基本原理。DFT的运算为：式中 由这种方法计算DFT对于 的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需4N*4N次实数相乘和（4N-2)(4N-2）次实数相加。改进DFT算法，减小它的运算量，利用DFT中 的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。FFT对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*（N/2)^2=N+（N^2）/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。
谁可以帮忙用fortran语言编写一个程序？是求n元一次方程组的解！或者是求100!的精确解！谢谢
! 求290以下正整数的阶乘的精确解
IMPLICIT NONE
INTEGER::J(100)=0,N,I,K
N=-1
DO WHILE(N>290.OR.N<0)
WRITE(*,*) '请输入一个小于290的正整数：'
READ(*,*) N
ENDDO
J(100)=1
IF(N>=2)CALL JS()
WRITE(*,*) N,'的阶乘等于：'
DO I=1,100-1; IF(J(I)>0)THEN; K=I; WRITE(*,'(I10\)') J(I); EXIT; ENDIF; ENDDO
DO I=K+1,100; WRITE(*,'(I6.6\)') J(I); ENDDO
WRITE(*,*)
CONTAINS
SUBROUTINE JS()
DO K=2,N
J=J*k
DO I=100,2,-1
IF(J(I)>999999)THEN
J(I-1)=J(I-1)+J(I)/10**6
J(I)=MOD(J(I),10**6)
ENDIF
ENDDO
ENDDO
END SUBROUTINE JS
END
试用高斯消元法编制Fortran程序计算n元一次方程组的解，并用一个三元一次方程组检验程序？
program gauss
implicit real(kind=8)(a-z)
integer,parameter:: N=3
integer::i,j
real(kind=8) ::A(N,N),b(N),x(N)
open(unit=11,file='fin.txt')
open(unit=12,file='fout.txt')
read(11,*)
!读入A矩阵
read(11,*)((A(i,j),j=1,N),i=1,n)
!读入B向量
read(11,*) (b(j),j=1,n)
call solve(A,b,x,N)
write(12,999)x
999 format(T5,'高斯消去法计算结果',/,T4,'x=',4(/F12.8))
end program gauss
!子程序---------------
subroutine solve(A,b,x,N)
implicit real*8(a-z)
integer::i,k,N
real(kind=8) ::A(N,N),b(N),x(N)
real(kind=8) ::Aup(N,N),bup(N)
!Ab为增广矩阵 [Ab]
real(kind=8) ::Ab(N,N+1)
Ab(1:N,1:N)=A
Ab(:,N+1)=b
! 这段是 高斯消去法的核心部分
do k=1,N-1
do i=k+1,N
temp=Ab(i,k)/Ab(k,k)
Ab(i,:)=Ab(i,:)-temp*Ab(k,:)
end do
end do
Aup(:,:)=Ab(1:N,1:N)
bup(:)=Ab(:,N+1)
!调用用上三角方程组的回带方法
call uptri(Aup,bup,x,n)
end subroutine solve
subroutine uptri(A,b,x,N)
implicit real*8(a-z)
integer::i,j,N
real(kind=8) ::A(N,N),b(N),x(N)
x(N)=b(N)/A(N,N)
!回带部分
do i=n-1,1,-1
x(i)=b(i)
do j=i+1,N
x(i)=x(i)-a(i,j)*x(j)
end do
x(i)=x(i)/A(i,i)
end do
end subroutine uptri
输入数据放在fin.txt 记得开头加！A.B
输出数据自动存放在fout.txt