Homework 4.

Assigned: Mon Oct 4. Due: Thursday Oct 14 at midnight.

You will need to do parts 2 and 3 of this assignment using your SUN Unix account: if you still don't have one, request one ASAP (from petagna@cs if you are registered in G22.2420 and the math department if you are registered in G63.G22.2420).

  1. Write a Matlab function house which implements Householder reduction of an m by n matrix A, returning two matrices V and R, where V stores the vectors implicitly representing Q (Alg 10.1 in the text). Write another Matlab function getQ , which generates the m by n matrix Q (the "reduced" Q factor) from V, using Alg 10.3. Compare the resulting norm(Q'*Q - I) with what you get from clgs and mgs1 (or mgs2), on the Legendre polynomial example.

  2. Translate both of these functions to C (or possibly Fortran 90). Use the BLAS (unless you are using Fortran 90). Also write MEX interfaces so they can both be called from Matlab. You may want to use different names from the Matlab versions to avoid confusion. I recommend that you use C unless you have a strong commitment to Fortran.

    More information on C and the MEX interface, as well as more info on the BLAS, LAPACK, Fortran and Java

  3. Carry out a timing and accuracy comparison of

    The Legendre polynomials make a good test case. Make sure you use a large enough n and m to make the comparsion meaningful (at least m=500, and go higher until it starts to take too long to wait), but but start with smaller values until you are sure everything is working. Plot your results on nicely labelled plots over a range of test sizes, using different plotting symbols for different codes (type "help plot"). Measure the times using cputime . (Elapsed time measures obtained by "etime" or "tic; ... toc" are affected by how much work other users are doing on the same machine). Measure accuracy with norm(Q'*Q - I) and norm(A - Q*R). Make some written comments which draw conclusions from the results.

    If you want to use Java instead of C or Fortran, which has the attraction of avoiding the MEX interface altogether, you may do so, but you are on your own as far as the details go. In order to use the BLAS, you would need either to to call the C or Fortran compiled versions using the Java Native Interface or download Java versions of the BLAS from the web.

    Some of you may find this homework very difficult. The key is to carefully look at the files available on the web and, once you understand them, make the necessary changes. Don't try to code from scratch! If you are lost, don't hesitate to contact me and discuss things - the sooner, the better. Don't panic, eventually you will get it!

    I will be out of town again Wed-Fri this week, but available this Tuesday and all of next week.