Homework 8, due Wed Dec 14

Homework must be given to me in class on Dec 14 or left under MY office ( NOT Ernest's door). Any time up to 12 noon on Thu Dec 15 is OK, but after that late homework will not be accepted or graded. Ernest will not be available after Dec 9. However, I am available to answer questions about the exam Tue Dec 13 through Fri Dec 16 (the day of the exam). Drop by my office or send email for an appointment.
  1. Implement Algorithm 12.1 (p.500 of the text). If you use Matlab, note that the second argument to fft in the algorithm statement is an output argument; thus the function declaration should be function y = myfft(x, n, w). Do not use the name fft, which is a standard function in Matlab. Test the code and compare the results to a standard FFT code such as fft in Matlab before going on to the next part.

    Important note: The last paragraph on p.500 on the issue of the result coming out in the wrong order is very confusing for the following reason: the author is thinking in terms of p and s being global variables. However, if p and s are local variables, i.e. allocated and deallocated every time the recursive function is called, the output order is correct. In most programming languages, the only way you could make p and s global is by explicitly passing these as additional parameters. While this may save on execution time, it makes the code far more confusing, so I recommend not doing this, unless you are very clear about what you are doing and are trying to make the code more efficient.

  2. Computer Problem 12.2, p.508, answering all parts (a),(b),(c),(d). For part (a), no FFT is required; you can solve the system with \. The point of parts (c) and (d) is to emphasize what may or may not be obvious: the FFT provides a far more efficient solution than \ (or even matrix multiply) for a problem like this, although it makes little difference when there are only 12 variables.
  3. Compare the efficiency of your code and the standard code on large randomly generated problems (for example, n=220). The book comments that the recursive implementation may not be an efficient choice, but another important, maybe more important, issue in Matlab is avoiding the explicit for loops. If you can, replace the loops by vector operations. Note that vectors can be indexed by other vectors. See Moler's book (freely available online, see course web page) for tips on Matlab programming. There is no problem using loops or recursion in a compiled language like C. How much slower is your code compared to the standard code for n=220?

You don't need this, but here is some info on the meaning of ascension and declination that I found on the web. The unit "minute" is a 60th of a degree, not a unit of time.

The measure in degrees of the position of a celestial object north or south of the celestial equator. If an object is on the celestial equator, it has a declination of 0 degrees, and if it is on the north or south celestial pole, it has a declination of +90 degrees or .90 degrees. Declination is analogous to latitude on the Earth, which measures terrestrial positions north or south of the equator. right ascension and declination together comprise a coordinate system that allows astronomers to locate objects in the sky.