13小结 本章主要讨论一维FFT和DWT的简单串、并行算法,二维FFT和DWT在光学、地震 以及图象信号处理等方面起着重要的作用。限于篇幅,此处不再予以讨论。同样,FFT和 DWT的并行算法的更为详尽描述可参见文献[2]和文献[3],专门介绍快速傅氏变换和卷积算 法的著作可参见[4]。另外,二维小波变换的并行计算及相关算法可参见文献[5],LogP模型 可参考文献[3] 参考文献 [1]王能超著.数值算法设计.华中理工大学出版社,19889 [2].陈国良编著.并行计算——结构·算法·编程.高等教育出版社,199910 [3].陈国良编著.并行算法设计与分析(修订版).高等教育出版社,200.11 [4]. Nussbaumer H J Fast Fourier Transform and Convolution Algorithms.2nded. Springer Verlag. 1982 [S].陈崚.二维正交子波变换的LSI并行计算.电子学报,1995,23(02):95-97 附录FFT并行算法的MP源程序 1.源程序ftc #include <stdio. h> #include <stdlib.h> <double>*f, int begi #include"mpi.h void print( const complex<double>+f, #define MAX PROCESSOR NUM 12 #define MAX N void read Double Complex(FILE *f, #define Pl 3.141592653 complex<double> &z) #define V TAg int main(int argc, char *argv) Q TAG complex<double> p[MAX NI, q[MAX NI R TAG #define S TAG complex<double> w[2"MAX N] #define S TAG2 complex<double> temp void evaluate(complex<double* f, int begin Pos int endPos, const complex<double>*x, int rank size. Int rightPos, int totallLength); Int w1.3 小结 本章主要讨论一维 FFT 和 DWT 的简单串、并行算法，二维 FFT 和 DWT 在光学、地震 以及图象信号处理等方面起着重要的作用。限于篇幅，此处不再予以讨论。同样，FFT 和 DWT 的并行算法的更为详尽描述可参见文献[2]和文献[3],专门介绍快速傅氏变换和卷积算 法的著作可参见[4]。另外，二维小波变换的并行计算及相关算法可参见文献[5]，LogP 模型 可参考文献[3]。 参考文献 [1]. 王能超 著．数值算法设计．华中理工大学出版社,1988.9 [2]. 陈国良 编著．并行计算——结构·算法·编程．高等教育出版社,1999.10 [3]. 陈国良 编著．并行算法设计与分析（修订版）．高等教育出版社，2002.11 [4]. Nussbaumer H J. Fast Fourier Transform and Convolution Algorithms.2nded. Springer￾Verlag,1982 [5]. 陈崚．二维正交子波变换的 VLSI 并行计算．电子学报,1995,23(02):95-97 附录 FFT 并行算法的 MPI 源程序 1. 源程序 fft.c #include <stdio.h> #include <stdlib.h> #include <complex.h> #include <math.h> #include "mpi.h" #define MAX_PROCESSOR_NUM 12 #define MAX_N 50 #define PI 3.141592653 #define EPS 10E-8 #define V_TAG 99 #define P_TAG 100 #define Q_TAG 101 #define R_TAG 102 #define S_TAG 103 #define S_TAG2 104 void evaluate(complex<double>* f, int beginPos, int endPos, const complex<double>* x, complex<double> *y, int leftPos, int rightPos, int totalLength); void shuffle(complex<double>* f, int beginPos, int endPos); void print(const complex<double>* f, int fLength); void readDoubleComplex(FILE *f, complex<double> &z); int main(int argc, char *argv[]) { complex<double> p[MAX_N], q[MAX_N], s[2*MAX_N], r[2*MAX_N]; complex<double> w[2*MAX_N]; complex<double> temp; int variableNum; MPI_Status status; int rank, size; int i, j, k, n; int wLength;