 Fast Fourier Transformation, Danielson-Lanczos Algorithm

| April 20, 2015

Order Details;

1. The coursework should be written used C99 Version and the results should be put into a word file
2. Answer all the questions on the question sheet (I will send to you later) except for those specifically states I need to do that on school’s computer
3. Put all the functions and mains into separate .c file (i.e each .c file contains only one function)
4. copy and paste the c code into a separate word file.

of your code for x = CN y for each value of N? How does this figure compare with the speed achieved by a Matrix-Vector multiplication Code from your last project? Plot the speed of your code in Megaflops vs Log2 N. 6. Add extra C Code to your FastDFS(… and FastDFT( … functions to deal with the cases N = 3, 6, 12, 24, 48,…. . Modify your complex double* MakeWPowers(int N) function (if necessary !) to generate the data for (WN) when N is of the form N = 3 * 2m Calculate F+ c3, F* c3, F+ r3, F* r3 . What are the floating point operations counts for the cases N = 3, 6, 12, 24, 48,…., 3*219 What the best values of A+,*3 and B+,*3 if equation (4) describes F+,* C/R Plot the 4 F+,*N values divided by N to get the average number of Floating Point operations per point vs log2[N] for the two series N = (1 & 3) * 2m . 7. Since (WN) 0 = 1 and (WN) N/2 = -1 , the floating point operations count for implementing equation (3) can be reduced to N-2 complex multiplications and N complex additions. The case x = C4 y can be performed directly using only 16 real additions (with careful coding). How do these efficiencies reduce the total floating point operation counts from N = 2 up to N = 220 and change A2 and B2 ? Can you reduce the operation counts for x = C3 y with careful coding? How does this affect the floating point operations counts for the cases N = 3, 6, 12, 24, 48,…., 3*219 (show tables !). Plot the speed in megaflops vs log2[N] for your improved code for all of these cases. Add the points for the ‘improved algorithms’ to your plot for Q6 to make another plot. M 3/4/5 SC – Exercise #3 – — Dan Moore — Due: 22h 1 May 2015 Exercise #3-I 4 10 March 2014 The discrete Fast Fourier Transform and Series of size 2 N may be used directly to perform a Fast Discrete Sine transform of vector S size N-1 by: a. Let Real Part(xj) = 0 for 0 < j < 2N ; b. Let Imag. Part (xj) = [S]j 1 < j < N-1 ; (Set Imag. Part (x0) = Imag. Part (xN) = 0!) c. Let Imag. Part (x2N-j) = – [S]j 0 < j < N d. Run your FastDFT function: y = CN -1 x e. Let [T]j = Real Part(yj) , 0 < j < N It should be the case that the vector T = 2 SN S . Use your code from Exercise #2 to demonstrate this [and debug your Fast Sine transform function]. 8. Write a void FastSINE(double *x, double *y,int N) function to implement the algorithm described above. Compare it for accuracy and speed with your best Matrix Mulitply function from Exercise #2 for the values N = 16, 24, 32, 48, … until you run out of time or storage. [Stop whenever either approach takes more than 100 second to perform SN S.] Do not include the time to calculate the matrix SN when comparing the direct Matrix-Vector multiply with your FastSINE() function. For what vale of N is your FastSINE() function faster than the direct Matrix-Vector multiply? For what values of N is it 4 times faster? 10 times faster? (If any?). 9. Use your your FastSINE() function in your code to solve the Poisson’s equation set out in Exercise 2. What are the new limits for the size of the 1-D and 2-D problem you can solve using the FFT approach? Mastery: (Worth up to 5% extra for M3SC): Add extra C Code to your FastDFS(… and FastDFT( … functions to deal with the cases N = 5, 10, 20, 40, 80 ,…., . Modify your double* MakeWPowers(int N) function (if necessary !) to generate the data for (WN) when N is of the form N = 5 * 2m . Calculate F+ c5, F* c5, F+ r5, F* r5 . What are the floating point operations counts for the cases N = 5, 10, 20, 40, 80,…., 5*218 What the best values of A+,*3 and B+,*3 and A+,*5 and B+,*5 if equation (4) describes F+,* C/R Plot the 4 F+,*N values divided by N to get the average number of Floating Point operations per point vs log2[N] for the three series N = (1, 3 & 5) * 2m . Compare and discuss. Time your 2-D and 3-D Poisson Solvers for the new values of N = 5, 10, 20, 40, 80,…., What are the largest 2-D and 3-D cases you can run on the PCs in the MLC and still get a solution in 100 seconds? 