News 

Dec 16. Final exams and final grades can be obtained from Nora in 4130 beginning Friday 12/17 1pm. If you have questions on the grading of your exam, please indicate the issues on the cover of the exam and leave with Nora. You can do this anytime up until the start of classes next term. Be sure to carefully consider the solution guide first.

Dec 15. Final exam solution guide is available. Instructions for exam pick-up and final grades tomorrow.

Dec 10.  A6 solutions available. Graded assignments available in 4130. (See Nora).

Dec 8 Forgot to post A5 solutions--here they are.

Dec 5  Carla's Office hours

Dec 3. Feel free to increase k (the number of iterations) in the P3and4 script.

Dec 3. You can drop A6 off in Upson 4130. We start grading Tuesday at 4.

Dec 3. Upcoming office Hours...

Dec 3. Final exam is Tuesday, December 14, Noon-2:30, Phillips 403. The exam is closed book. The syllabus for the exam is defined by the concepts that you need to understand in order to do the assignments and the midterm. The problems of the day touch on key ideas as well.

Nov 29 Final exam and solution from the S02 version of the course are available.

Nov 29 Example 1 in the P1 test script has a typo. We want the bottom 2-by-2 to have complex eigenvalues. So set it to [3 4 ; -10 1] instead of [3 4 ; -1 10]. The test script has been so altered.

Nov 29 In P1, it is possible to solve this problem in O(n^2) flops by turning the various matrix problems that arise in the problem to quasi-upper triangular matrix problems. Permutations do the trick. This means that should you use "\", it becomes O(n^2). This means that when you go after the smallest singular value, you could (in principle) use O(n^2) condition estimation techniques. However, you can invoke svd. 

Nov 29 The script P3and4 is available. This problem is worth 6 points. Four points will revolve around your implementation of GoogleMatrix and how it performs on the small examples in the test script. Remember that Ap*vector is O(N), so make sure you assess your implementation at that level. Note that an N-by-3 QR factorization is essentially O(N) since N>>>>3. Regarding the generation of a random starting matrix for the orthogonal iteration process, [Q0,R] =qr(randn(N,3),0) does just fine.

For the remaining two points, tell me two interesting things about the Ap matrix and back them up with suitable numerical experiments. Sample "interesting" things include

• How does Lambda2 behave as N gets very large for particular choices of the probability p and the q-factor used to generate the random G.
• How does the page rank of the top ten pages change if suddenly some large fraction of all the webpages point to the highest rank page?
• How does the choice of the probability p affect Lambda2?
• How can we construct an example where the condition of Lambda2 gets arbitrarily large?

You can make up your own "interesting" observations--but they must be "cleared" by me. As far as the numerical examples/simulations that you use to illustrate your facts--keep them simple and short. Graphical output is fine. Be clear (and brief) in your write-up

Nov 26. Test scripts for P1, P2  together with the function MakeG are available. The final test script for P3and4 will be posted on Monday.

Nov 26. In GoogleMatrix, you should use 3-column orthogonal iteration. The 2-column version would have problems if the second and third eigenvalues are complex. 

Nov 23. Typo in P1. The matrix M is (2n-4)-by-(2n-4).

Nov 23. Assignment A6 is available. Test scripts soon.

Nov 15. Regarding the use of fzero in P3, there may be a problem with what version of Matlab you are using. The following shuold work with older versions:

root = fzero(@MyFun,[L,R],[],d,v,alpha)

will find a root of a function named MyFun assuming that [L,R] is a bracketing interval and MyFun is a function that you have defined with the syntax MyFun(lambda,d,v,alpha).

Nov 10. Assignment 5 test scripts are available. And here are some hints/corrections:

Nov 9. Assignment 4 solution guide is available.

Nov 8. Assignment 5 handout is available. Scripts will be ready by Wednesday.

Nov 4. Regarding Assignment 4, in P! you are free to use the Matlab functions planerot, qrdelete, and qrinsert if you think they can be used to solve efficiently the problem. Likewise, in P2, use SVD and QR.

Nov 2 The midterm solutions are available. You can pick them up from Carla this afternoon, 2-4. I will bring the rest to class tomorrow. Feel free to have me look over your exam if you have a question.

Oct 28 A4 test scripts are available. So is the corrected handout.

Oct 22 Final clarifications for the midterm:

Problem 1. Roundoff error and noise mean that when we go to compute rank via SVD or QR with column pivoting we'll conclude that the matrix has full rank. Thus, when one is in a (near) rank deficient situation it is handy to "relax" the definition of zero when looking at  critical matrix values. Thus, we may set all computed singular values to zero that are <= tol and proceed under the assumption that A has rank p where p is the number of computed singular values that are greater than tol. In this problem we declare a matrix to have rank equal to its delta-rank. With this assumption the true minimum value is obtained. But appreciate that WE NEVER KNOW the true minimum sum of squares because WE NEVER KNOW the true rank!

Problem 2. Your solution is to be flop efficient. Vectorize subject to that constraint. You are free to use LU and backslash. And backslash is flop-efficient when the matrix of coefficients is triangular. Do not make any assumptions about the relative sizes of n, k and j.

Problem 3. For j=1:n-1, it must be the case that T(r + q(j)*I(1:j,j)) is singular. If you have choices for q(j), it does not matter which you select.

Problem 4. Reminder about  the typo: L(k+1:n,k) = C(2:n-k+1,1)/C(1,1). Again, you solution should be vectorized subject to the constraint that it is flop-efficient

Oct 20  Solutions to Assignment 3 are available.

Oct 18. Here are the specifications for the functions that you are to submit for the Midterm. MatrixLS has been clarified a bit to make clear that you are to minimize norm(A*X*B'-C,'fro') assuming that A and B have rank rA and rB. Borderline has been simplified--you only need to return the lower triangular portion of T. If you do the original problem (returning the full T-matrix), it'll be a 5-point bonus (out of 100 total for the exam).

Oct 15 Here is the Take-Home Midterm.

Oct 13. If you'd like to see what a take-home midterm might look like, click here.

Oct 8  In P3, you may assume that W = -Z involves no flops where Z is a matrix. For one extra bonus point, drop this assumption and still produce an implementation that requires n^3/3 flops.

Oct 5 In the following, should be   P = I(pVec,:), not I(:,pVec). It is simpler this way.

     function [L,mu,pVec] = SkewBunchParlett(A)
   % A is an n-by-n symmetric matrix with n = 2m.
   % mu is a column m-vector, L is unit lower triangular, and pVec is a permutation of 1:n
   % so that if P = I(:,pVec) then PAP' = LDL' is the Skew Bunch-Parlett factorization
   % where D = diag(D1,...,Dm), with Dk = [0 mu(k); -mu(k) 0] for k=1:m.
 

Oct 5. Typo in spec for HermFactor. The subdiagonal of A is g + i*h, not c + i*e.

Oct 4. A2 grading guide is available.

Oct 1. Test scripts for Assignment 3 are available.

Oct 1. There was a typo in the Assignment 3 handout. In P3, the third displayed equation has some signs wrong. The first factor should be -C*inv(E) in the (2,1) block. And the middle factor should be B + C*inv(E)*C' in the (2,2) block. The online version of the handout has this correction.

Oct 1. After looking at some regrade submissions for earlier assignments, we no longer will adjust grades for "stupid mistakes", e.g., "I forgot a tranpose".

Oct 1. The Assignment 3 handout is available.

Sept 27  To save paper, just turn in Figures 5 and 6 from the output for P4. That'll be enough to check for correctness.

Sept 27 More comments on A2. P1. Make sure your computation of B_opt is efficient. P4. Do not set-up a 2n-by-2n block diagonal system to solve the n problems "all at once" using backslash. Even if you invoke sparse, the solution procedure will not involve length-n vector operations. Also, you do not have to worry about  the ray being parallel (or even nearly parallel) to any of the polygon edges.

Sept 27 The test script for P4 has a stray assignment: m = n/2. Delete this.

Sept 24 Assignment 2 write-up is available. Sorry for the delay.

Sept 22  Assignment 1 is graded

Sept 20 In case you are making end-of-term travel plans. we'll have a closed book final on Tuesday, Dec 14, 12-2:30 pm.

Sept 17 The test scripts for Assignment 2 are available.

Sept 8. In the Assignment 1 handout, every "n" should be an "m" in the third bullet of Problem 4.

Sept 3. The test scripts for Assignment 1 are available. Also, there will be class on Labor Day.

 Top

General Information

Syllabus

 Top

Assignments and Solutions

Top

Exams and Solutions

 Top