MPI通过矩阵乘实现傅立叶变换

串行计算时，fft比传统矩阵乘的傅立叶变换有极大优势。但是，在并行条件下，迭代的fft需要大量的网内通信，overhead不是很好，而且并行度最高就是n，并不理想。相比于这个，传统的矩阵乘法的计算过程没有线程间通信，会有很大的效率提升。而且，如果计算每一行的乘法时使用openmp进一步增加并行度也是可行的，通信也不会有显著的增加。

#include "mpi.h"#include <stdio.h>#include <stdlib.h>#include <math.h>typedef struct {double real;double img;} com;double PI;void add(com a,com b,com* r);void mul(com a,com b,com* r);static inline com getW(int self,int i,int size);com *W;int main(int argc,char *argv[]) {PI=atan(1)*4;int self,size;//process id and total number of processesMPI_Init(&argc,&argv);MPI_Comm_rank(MPI_COMM_WORLD,&self);MPI_Comm_size(MPI_COMM_WORLD,&size);W=(com *)malloc(size*sizeof(com));for(int i=0;i<size;++i) {W[i].real=0;W[i].img=0;}W[0].real=1;com a[size];for(int i=0;i<size;++i) {//initialize test dataa[i].real=i+1;a[i].img=0;}com b;//resultfor(int i=0;i<size;++i) {mul(a[i],getW(self,i,size),&a[i]);add(b,a[i],&b);}printf("b%d:%.4f %.4f",self,b.real,b.img);free(W);MPI_Finalize();return 0;}void add(com a,com b,com *c)   {c->real=a.real+b.real;   c->img=a.img+b.img;   }       void mul(com a,com b,com *c)   {   c->real=a.real*b.real-a.img*b.img;   c->img=a.real*b.img+a.img*b.real;   }com getW(int self,int i,int size) {int t=self*i%size;if(W[t].real==W[t].img&&W[t].real==0) {W[t].real=cos(2*PI*t/size);W[t].img=sin(2*PI*t/size);}return W[t];}